Усреднение набора точек на карте Google в меньший набор

Question

Я показываю небольшую карту Google на веб-странице, используя статический API Google Maps.

У меня есть набор из 15 координат, которые я хотел бы представить в виде точек на карте.

Из-за того, что карта довольно маленькая (184 x 90 пикселей) и верхнего предела в 2000 символов в URL-адресе Google Maps, я не могу представить каждую точку на карте.

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

Таким образом, вместо 15 сетов у меня получилось бы 5 сетов, позиции которых приблизительно соответствуют позициям 15.Допустим, есть 3 точки, которые находятся в большей близости друг к другу, чем к любой другой точке на карте, эти точки будут свернуты в 1 точку.

Поэтому я предполагаю, что ищу алгоритм, который может это сделать.

Не прошу никого подробно описывать каждый шаг, но, возможно, укажите мне в направлении математического принципа или функции общего назначения для такого рода вещей?

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

(Если я решу эту проблему, я обязательно опубликую свои результаты.)

Answer 1

Я рекомендую K-означает кластеризацию когда вам нужно сгруппировать N объектов в известное число K < N кластеров, что, по-видимому, относится к вашему случаю.Обратите внимание, что в одном кластере может оказаться одна точка выброса, а в другом, скажем, 5 точек, расположенных очень близко друг к другу:ничего страшного, это будет выглядеть ближе к вашему исходному набору, чем если бы вы добавляли ровно 3 балла в каждый кластер!-)

Answer 2

Если вы поиск для таких функций / классов взгляните на Маркеркластер и MarkerManager Маркерменеджер классы полезности.MarkerClusterer полностью соответствует описанной функциональности, как показано на эта демо-версия.

Answer 3

В общем, я думаю, что область, в которой вам нужно искать, - это "Векторное квантование".У меня есть старое название книги "Векторное квантование и сжатие сигнала " Аллена Гершо и Роберта М.Серый, в котором приводится множество примеров.

Судя по памяти, итерация Ллойда была хорошим алгоритмом для такого рода вещей.Он может взять входной набор и уменьшить его до набора точек фиксированного размера.По сути, равномерно или случайным образом распределите свои точки по пространству.Сопоставьте каждый из ваших входных данных с ближайшей квантованной точкой.Затем вычислите ошибку (например,сумма расстояний или среднеквадратичное значение).Затем для каждой выходной точки установите ее в центр набора, который соответствует ей.Это переместит точку и, возможно, даже изменит набор, который ей соответствует.Выполняйте это итеративно до тех пор, пока не будут обнаружены никакие изменения от одной итерации к следующей.

Надеюсь, это поможет.