В настоящее время я разрабатываю вид виджетов, отображающих местоположения в виде маркеров на карте. Количество маркеров варьируется от нескольких сотен до тысяч маркеров (10000 очков). Прямо сейчас я использую MarkerClusterer для google maps v3 1.0 и google maps javascript api v3 (premier), и он работает довольно прилично, так как позволяет сказать сотню маркеров. Из-за того, что количество маркеров увеличится, мне нужен новый способ кластеризации маркеров. Из того, что я прочитал, единственный способ сохранить производительность – это перемещение кластеризации с клиентской стороны на серверную. Кто-нибудь знает хорошую библиотеку PHP5, которая может сделать это для меня?
Atm Я копаю глубже в слои механизмов google-карт. Может быть, есть также несколько ведущих PHP-библиотек, которые я мог бы начать проверять? Я также столкнулся с FusionTables, но так как мне нужна кластеризация, я думаю, что это может быть неправильное решение.
Заранее спасибо!
Я не знаю библиотеку на стороне сервера, которая будет работать для вас. Однако я могу дать вам несколько указаний о том, как реализовать их самостоятельно.
Основной подход к кластеризации – просто вычислить расстояние между вашими маркерами, и когда два из них достаточно близки, вы замените их одним маркером, расположенным в середине точки между ними.
Вместо того, чтобы просто ограничивать то, насколько близки друг к другу маркеры, вы также можете (или вместо этого) выбрать ограничение количества кластеров / маркеров, которые вы хотите в результате.
Для этого вы можете рассчитать расстояние между всеми парами маркеров, отсортировать их, а затем слиться с вершины, пока у вас не будет столько маркеров / кластеров, сколько хотите.
Чтобы уточнить позиционирование в середине позиции при формировании кластера, вы можете принять во внимание количество фактических маркеров, представленных каждым из двух, которые должны быть объединены. Подумайте об этом количестве в виде веса и линии между двумя маркерами в виде шкалы. Затем вместо того, чтобы всегда выбирать среднюю точку, выберите точку, которая будет балансировать масштаб .
Я бы предположил, что эта простая форма кластеризации достаточно хороша, если у вас ограниченное количество маркеров. Если ваш набор данных (# маркеров и их позиция) является примерно статическим, вы можете рассчитать кластеризацию на сервере один раз в то время, кешировать его и клиентов сервера непосредственно из кеша.
Однако, если вам необходимо поддерживать сценарии с большим масштабом, потенциально с маркерами по всему миру, вам понадобится более сложный подход.
Указанный кластерный алгоритм не масштабируется. Фактически, его вычислительная стоимость обычно экспоненциально возрастает с количеством маркеров.
Чтобы исправить это, вы можете разделить мир на разделы и рассчитать кластеризацию и обслуживать клиентов из каждого раздела. Это действительно поддержит масштабирование, поскольку рабочая нагрузка может быть разделена и выполнена несколькими (примерно) независимыми серверами.
Тогда возникает вопрос, как найти хорошую схему разбиения. Вы также можете рассмотреть возможность предоставления различной кластеризации маркеров на разных уровнях масштабирования, и ваша схема разбиения должна включать это, а также для масштабирования.
Google разделит карту на плитки с координатами x, y и z, где x и y – горизонтальное и вертикальное положение плитки, начиная с северо-западного угла карты и где z – уровень масштабирования.
При минимальном уровне масштабирования (ноль) вся карта состоит из одной плитки. (все плитки имеют 256×256 пикселей). На следующем уровне масштабирования эта плитка делится на четыре подтипа. Это продолжается, так что в режиме масштабирования 2 каждый из этих четырех фрагментов был разделен на четыре подтипа, что дает нам в общей сложности 16 плиток. Уровень 3 уровня имеет 64 плитки, уровень 4 имеет 256 плиток и т. Д. (Количество плиток на любом уровне масштабирования может быть выражено как 4^z .)
Используя эту схему разбиения, вы можете рассчитать кластеризацию на каждый фрагмент, начиная с самого низкого уровня масштабирования (самая высокая координата z), пузырясь вверх, пока не достигнете вершины.
Набор маркеров для кластеризации для одной плитки – это объединение всех маркеров (некоторые из которых могут представлять собой кластеры) из четырех подтипов.
Это дает вам ограниченную вычислительную стоимость, а также дает отличный способ разбить данные, которые будут отправлены клиенту. Вместо того, чтобы запрашивать все маркеры для заданного уровня масштабирования (который не будет масштабироваться), клиенты могут запросить маркеры на основе поэтапного разбиения по мере их загрузки на карту.
Однако в этом подходе есть недостаток: рассмотрите две соседние плитки, одну влево и одну вправо. Если левая плитка содержит маркер / кластер на своей правой стороне, а правая плитка содержит маркер / кластер на своей левой стороне, то эти два маркера / кластера должны быть объединены, но не будут, так как мы выполняем кластеризацию механизм для каждой плитки индивидуально.
Чтобы исправить это, вы можете послепродавать плитки после их кластеризации, чтобы объединить маркеры / кластеры, которые лежали на каждом из четырех краев, с учетом каждого из восьми соседних плит для данной плитки. Этот механизм после слияния будет работать, только если мы можем предположить, что ни один кластер не является достаточно большим, чтобы влиять на окружающие маркеры, которые не находятся в одном и том же субтире. Это, однако, разумное предположение.
В качестве окончательного примечания: при расширенном подходе у вас будут клиенты, делающие несколько небольших запросов. Эти запросы будут иметь локальность (т. Е. Плитки не запрашиваются случайным образом, но вместо этого к ним обычно обращаются плитки, географически близкие друг к другу).
Чтобы улучшить производительность поиска и запросов, вам будет полезно использовать ключи поиска (представляющие фрагменты), которые также обладают этим свойством локальности (поскольку это будет хранить данные для смежных элементов в смежных блоках данных на диске, что улучшает время чтения и использование кеша).
Вы можете сформировать такой ключ, используя схему разбиения плитки / субтитра. Пусть верхняя плитка (единственная, охватывающая всю карту) имеет пустую строку в качестве ключа. Затем пусть каждый из своих подтипов имеет ключи A, B, C и D. Следующий уровень будет иметь ключи AA, AB, AC, AD, BA, BC, …, DC, DD.
Примените это рекурсивно, и в итоге вы получите ключ разделения, который идентифицирует ваши фрагменты, позволяет быстро преобразовать x, y, z-координаты и обладать свойством локальности. Эта схема наименования ключей иногда называется Квад-ключом, вытекающей из того факта, что схема разбиения образует Quad Tree . Свойство locality такое же, как и при использовании кривой Z-порядка для отображения 2D-значения в 1D-значение.
Пожалуйста, дайте мне знать, если вам нужна дополнительная информация.
В этой статье приведены некоторые примеры PHP для кластеризации маркеров:
http://www.appelsiini.net/2008/11/introduction-to-marker-clustering-with-google-maps
Вы можете попробовать бесплатное приложение для кластеризации. Он способен больше контактов, чем клиентские карты google api. Он предлагает kmeans кластеризацию на основе сетки.