Клуб API Карт

Распределение меток при масштабировании

nolan23
16 февраля 2010, 00:02

Долгое время являюсь пользователем карт, прикрутил уже не к одному проекту, но до сих пор не смог решить оч. важную проблему. А именно - фильтрацию точек на карте при уменьшении зума.

то есть, например, в Москве у меня 200-300 точек. стоит начать уменьшать зум, как метки начинают наезжать друг на друга - некрасиво.

Заметил, как это решено в фотках - изумительно! Фильтрация меток, ни одна друг на друга не наезжает, все аккуратно и красиво.

В связи с этим - вопрос: как это реализовано? понятно, что на серверной стороне. Но хотя бы дайте ключик к идее!

Mysql умеет просчитывать окружности и не допускать их пересечения? или, может, сервер пересчитывает все (или часть)масштабов - от 1 до 10 (например) и ставит флаги тем меткам, которые будут отображаются при соответствующем масштабе?

В общем - дайте идею, плиз

12 комментариев
Подписаться на комментарии к посту

то есть алгоритм следующий:

1. Каждой точке добавляем поле zoom

2. При добавлении точки используем цикл по zoom от 0 до 14

for (i=0; i

{

- вычисляем прямоугольник метки исходя из размера метки в мировых координатах и смещения от центральной точки (или точки привязки метки). то есть получаем прямоугольник, ограничивающий метку и соседние метки в мировых координатах с соотв. зумом

- делаем запрос в базу данных с проверкой - есть ли в получившемся прямоугольнике метки

- если есть: продолжаем цикл, если нет добавляем метку с zoom = i и выходим из цикла.

}

при выводе на карту - выбираем метки по bounding rect карты и у которых поле zoom

похоже?

Это один из вариантов QT-алгоритма. Главный его недостаток - высокая сложность (соответственно, большое число запросов к базе).
рандомно выбираем N обьектов из базы из расматриваемой области(тайла).
проверяем их взаимное пересечение( кластера и другие хэш таблицы в этом помогут)
Рисуем! Работает!

Вариант два - для каждого зума расчитываем сколько у одной фотки соседей( точнее тут нам интересно узнать скольким другим она не даст появиться фактом своего существования)
Далее два пути - аск, или декс.
Смотря какую плотность на карте надо обеспечить

Хотя конечно лучший вариант в забивании кучи данных в дерево и последующий транверс по нему

похоже, действительно придется делать дерево.

самый простой вариант - это просто присвоить метках минимальный зум, но тогда вверху (при меньшем зуме) всегда будут самые старые метки...

если делать деревом, тогда новую метку можно будет добавлять в верхний слой (зум), а остальные пересчитывать - не сильно затратно для 2-3 сотен меток на тайтле...

Тут же всплывает другая проблема - фильтрация меток. то есть после получения дерева меток, отфильровать метки по какому-либо признаку уже не получится - появятся пустые места, и часть не будет показана...

перфиктоцианиз - вреден
стремление к прекрасному часто это прекрасное убивает, как минимум потому что его не получается достичь в отведеные рамки.
лично меня пара лет в гейдмеве научила любить и уважать фейки - когда свиду вроде бы все правильно, и этого уже достаточно

вообще - разумное зерно тут есть. даже более чем!

тогда снимается огромная куча проблем - и с фильтрацией, и с показом новых точек.

то есть просто выбираем, скажем 50-60 НОВЫХ точек для показываемого участка карты - и не паримся!

спасибо, брад!

в общем, в резалте сделал следующее:

повесил на BoundsChange ajax.

из минусов

- обсчет при каждом движении карты

- фейк, конечно))) обсчитываются 1000 точек (можно больше, если серв позволяет. у меня на 2 ядрах обсчет занимает 0,3сек)

- размер метки в геогр. кооординатах подобран эмипирически ))))

- иногда случаются наложения меток (вероятно, из-за неточного алгоритма)

из плюсов:

- тайтлы все равно грузятся какое-то время, поэтому подгрузка меток - не так уж и критична

- возможна любая фильтрация меток


соответственно вот скрипт сервера:

// координаты и зум
$lnglat1 = isset($_GET['lnglat1']) ? $_GET['lnglat1'] : '0,0';
$lnglat2 = isset($_GET['lnglat2']) ? $_GET['lnglat2'] : '180,180';
$zoom = isset($_GET['zoom']) ? $_GET['zoom'] : 10;
list($lng1, $lat1) = explode(',', $lnglat1);
list($lng2, $lat2) = explode(',', $lnglat2);

// в зависимости от показываемой области формируем запрос
if ($lng1 > $lng2)
{
if (($lng1 > 0) && ($lng2 > 0))
{
$sql_lng = "AND ((GDE_LNG BETWEEN $lng1 AND 180) OR (GDE_LNG BETWEEN -180 AND 0) OR (GDE_LNG BETWEEN 0 AND $lng2))";
} elseif (($lng1 > 0) && ($lng2 < 0)) {
$sql_lng = "AND ((GDE_LNG BETWEEN $lng1 AND 180) OR (GDE_LNG BETWEEN -180 AND $lng2))";
}
}
else
{
$sql_lng = "AND (GDE_LNG BETWEEN $lng1 AND $lng2)";
};

// магия - коэффициенты для разных зумов. По идее - это размер метки в 27 пикс в километрах. 13 и 14- размер = 0  - показываем все метки
$zoom_dist_array = array ('0'=>500, '1'=>768, '2'=>384, '3'=>200, '4'=>96, '5'=>48, '6'=>24, '7'=>12, '8'=>6, '9'=>3, '10'=>1.6, '11'=>0.8, '12'=>0.4, '13'=>0, '14'=>0);
$zoom_dist = $zoom_dist_array[$zoom];
// размер маркера (метки) на карте и офсет точки
$icon_size = (object) array('width'=>27, 'height'=>27);
$offset = (object) array('left'=>-9, 'top'=>-25);
// массивы для проверки наложения меток
$map_lng = array();
$map_lng[0] = array($lng1, $lng2);
$map_lat = array();
$map_lat[0] = array($lat1, $lat2);
$output_points = array();
$count = 0;

$icon_offset = (object) array('x'=> ($offset->left / $icon_size->width), 'y'=> ( - $offset->top / $icon_size->height));
//$icon_offset = (object) array('x'=>0, 'y'=>0);

// вытаскиваем из базы 1000 последних точек, лежащих в видимой области на карте
$sql = "SELECT * FROM gde_latlng WHERE GDE_VEHICLE=$vehicle $sql_lng AND (GDE_LAT BETWEEN $lat1 AND $lat2) LIMIT 1000";
$result = mysql_query($sql);
if ($result)
{


while ($row = mysql_fetch_assoc($result))
{
$count ++;
$lat = (float) $row['GDE_LAT'];
$lng = (float) $row['GDE_LNG'];
// высчитываем геогр. координаты прямоугольника от метки
$left = $lng - $zoom_dist * (1+ $icon_offset->x) / (111.1 * cos(M_PI_4)) * cos(M_PI_4);
$top = $lat - $zoom_dist * (1 - $icon_offset->y) / 111.1 * sin(M_PI_4);
$right = $lng + $zoom_dist * (1 - $icon_offset->x) / (111.1 * cos(M_PI_4)) * cos(M_PI_4);
$bottom = $lat + $zoom_dist * (1 + $icon_offset->y) / 111.1 * sin(M_PI_4);

$intersect= false;

// проверям на наложение меток
foreach($output_points as $point)
{
if ( ( ($left > $point['left'] && $left < $point['right']) && ($top > $point['top'] && $top < $point['bottom']) ) ||
( ($right > $point['left'] && $right < $point['right']) && ($top > $point['top'] && $top < $point['bottom']) ) ||
( ($right > $point['left'] && $right < $point['right']) && ($bottom > $point['top'] && $bottom < $point['bottom']) ) ||
( ($left > $point['left'] && $left < $point['right']) && ($bottom > $point['top'] && $bottom < $point['bottom']))
) {
$intersect = true;
break;
};
};

// если нет наложения меток - добавляем в аутпут
if (!$intersect)
{
$output_points[] = array_merge($row, array('left'=>$left, 'top'=>$top, 'right'=>$right, 'bottom'=>$bottom));
};
};
echo '['." ";
$i = 0;

// кодируем json и отдаем клиенту
foreach($output_points as $row)
{
echo (($i > 0) ? ',' : '');
$row = array_map(ToWindows1251,$row);
echo json_encode($row);
$i ++;
};
echo ']';
};
function ToWindows1251($n) {
return iconv("windows-1251", "UTF-8", $n);
}

можно для каждой точки задать минимальный и максимальный зум типа objManager.add(placemark,10,14)

да, но тогда придется на самый крупный масштаб грузить все метки.

а у меня их планируется до 10000 шт. :-\

Я решил это путем группировки.

Грубо говоря нужно отображенную часть карты виртуально разделить на ячейки, путём нехитрых вычислений получим 2 делителя, для широты и долготы.

Далее в запросе группируем по широте и долготе, деленными на свои делители, с некоторым округелением. Округление важно, т.к. оно напрямую влияет на количество групп. Я сделал просто, умножаю делители и координаты на миллион, дробную часть обрезаю после деления. Получаются целые числа. 

Регулируя размер ячеек можно регулировать, сколько точек окажется в группе.

На карте отображается только одна произвольная точка из группы, причем в своих реальных координатах, а не усредненных, как это делается в нативных кластерах АПИ.