Con un promedio de un conjunto de puntos en un mapa de Google en un conjunto más pequeño

Question

Estoy mostrando un pequeño mapa de Google en una página web utilizando la API de Google Maps estática.

Tengo un conjunto de 15 coordenadas, que me gustaría representar como puntos en el mapa.

Debido al mapa de ser bastante pequeño (184 x 90 píxeles) y el límite superior de 2000 caracteres en una URL de Google Maps, no puedo representar a todos los puntos en el mapa.

Así que en lugar me gustaría generar una pequeña lista de coordenadas que representa un promedio de la lista grande.

Así que en lugar de tener 15 conjuntos, que iba a terminar con 5 juegos, quién es aproximar las posiciones de las posiciones del 15. Digamos que hay 3 puntos que se encuentran en una proximidad más cercana a cada-otro que el de cualquier otro punto en el mapa , esos puntos se derrumbó en 1 punto.

Así que supongo que estoy buscando un algoritmo que puede hacer esto.

No pedir a nadie a explicar en detalle cada paso, pero tal vez me punto en la dirección de un principio o de propósito general de funciones matemáticas para este tipo de cosas?

Estoy seguro de que una función similar se utiliza en, por ejemplo, software de gráficos, cuando pixellating una imagen.

(Si puedo solucionar este Voy a estar seguro para publicar mis resultados.)

Answer 1

K-means clustering cuando se necesita para agrupar objetos en un N número conocido K

Answer 2

Si usted es buscar para tales funciones / clases, echar un vistazo a y href="http://gmaps-utility-library-dev.googlecode.com/svn/tags/markermanager/" rel="nofollow noreferrer"> clases de utilidad MarkerManager . MarkerClusterer coincide estrechamente la funcionalidad descrita, como se ve en esta demo .

Answer 3

En general creo que la zona en la que es necesario buscar en torno a es "Cuantificación Vectorial". Tengo un viejo título del libro Cuantificación Vectorial y Compresión de señal por Allen Gersho y Robert M. Gray, que ofrece un montón de ejemplos.

De memoria, la iteración Lloyd era un buen algoritmo para este tipo de cosas. Se puede tomar el conjunto de entrada y reducirla a un conjunto de tamaño fijo de puntos. Básicamente, uniforme o aleatoria a distribuir sus puntos alrededor del espacio. Mapear cada una de sus entradas hasta el punto más cercano cuantificado. Entonces calcular el error (por ejemplo suma de las distancias o Root-Mean-Squared). Luego, para cada punto de salida, ponerlo en el centro del conjunto que se asigna a ella. Esto moverá el punto y, posiblemente, incluso cambiar el conjunto que se asigna a ella. Realice esta forma iterativa hasta que no se detectan cambios de una iteración a la siguiente.

Espero que esto ayude.