Я не знаю библиотеки на стороне сервера, которая сделает эту работу за вас. Однако я могу дать вам несколько советов о том, как реализовать его самостоятельно.
Основной подход к кластеризации заключается в простом вычислении расстояния между вашими маркерами, и когда два из них достаточно близки , вы заменяете их одним маркером, расположенным в средней точке между двумя.
Вместо того, чтобы просто ограничивать насколько близко друг к другу могут быть маркеры, вы также можете (или вместо этого) выбрать ограничение количества кластеров / маркеров, которые вы хотите получить в результате.
Для этого вы можете рассчитать расстояние между всеми парами маркеров, отсортировать их, а затем сливаться сверху, пока у вас будет только столько маркеров / кластеров, сколько вы хотите.
Чтобы уточнить расположение средней точки при формировании кластера, вы можете принять во внимание количество фактических маркеров, представленных каждым из двух объединяемых элементов. Думайте об этом числе как о весе, а границу между двумя маркерами как о шкале. Затем вместо того, чтобы всегда выбирать среднюю точку, выберите точку, которая будет уравновешивать шкалу .
Я предполагаю, что эта простая форма кластеризации достаточно хороша, если у вас ограниченное количество маркеров. Если ваш набор данных (количество маркеров и их положение) примерно статичен, вы можете время от времени вычислять кластеризацию на сервере, кэшировать его, а клиентов сервера - непосредственно из кэша.
Однако, если вам нужно поддерживать крупномасштабные сценарии, потенциально с маркерами по всему миру, вам понадобится более сложный подход.
Указанный кластерный алгоритм не масштабируется. Фактически его вычислительные затраты обычно растут в геометрической прогрессии с увеличением количества маркеров.
Чтобы исправить это, вы можете разделить мир на разделы и рассчитать кластеризацию и обслуживать клиентов из каждого раздела. Это действительно поддержит масштабирование, поскольку рабочая нагрузка может быть разделена и выполняться несколькими (примерно) независимыми серверами.
Вопрос в том, как найти хорошую схему разбиения. Возможно, вы также захотите предусмотреть разную кластеризацию маркеров на разных уровнях масштабирования, и ваша схема разбиения должна также включать это, чтобы обеспечить масштабирование.
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 и имеет свойство locality.Эту схему именования ключей иногда называют Quad Key , вытекающую из того факта, что схема разбиения образует Quad Tree .Свойство locality такое же, как и при использовании кривой Z-порядка для отображения 2D-значения в 1D-значение.
Пожалуйста, дайте мне знать, если вам нужна дополнительная информация.