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

Question

Я отображаю небольшую карту Google на веб-странице с помощью Статического API Карт Google.

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

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

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

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

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

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

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

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

Answer 1

Я рекомендую K-означает кластеризацию , когда вам нужно кластеризовать N объектов в известное число K

Answer 2

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

Answer 3

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

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

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