Média de um conjunto de pontos em um mapa do Google em um conjunto menor

Question

Estou exibindo um pequeno mapa do Google em uma página da web usando a API estática do Google Maps.

Eu tenho um conjunto de 15 coordenadas, que eu gostaria de representar como pontos no mapa.

Devido ao fato de o mapa ser razoavelmente pequeno (184 x 90 pixels) e o limite superior de 2000 caracteres em um URL do Google Maps, não posso representar todos os pontos do mapa.

Então, em vez disso, eu gostaria de gerar uma pequena lista de coordenadas que represente uma média da grande lista.

Então, em vez de ter 15 conjuntos, eu acabaria com 5 conjuntos, cujas posições se aproximam das posições dos 15. Dizem que existem 3 pontos que estão mais próximos de cada um do que qualquer outro ponto no mapa, esses pontos será desmoronado em 1 ponto.

Então, acho que estou procurando um algoritmo que possa fazer isso.

Não pedindo a ninguém para explicar cada passo, mas talvez me indique na direção de um princípio matemático ou função de uso geral para esse tipo de coisa?

Tenho certeza de que uma função semelhante é usada em software gráfico, digamos, ao pixelling uma imagem.

(Se eu resolver isso, postarei meus resultados.)

Answer 1

Eu recomendo Cluster de k-means Quando você precisa agrupar os objetos n em um número conhecido k <n de clusters, que parecem ser o seu caso. Observe que um cluster pode acabar com um único ponto externo e outro com 5 pontos muito próximos um do outro: tudo bem, ele parecerá mais próximo do seu conjunto original do que se você forçar exatamente 3 pontos a cada cluster!-)

Answer 2

Se você é procurando Para essas funções/classes, dê uma olhada MarkerClusterer e MarkerManager Classes de utilidade. Markerclusterrer corresponde de perto à funcionalidade descrita, como visto em esta demonstração.

Answer 3

Em geral, acho que a área em que você precisa pesquisar é "quantização de vetores". Eu tenho uma quantização antiga de vetor de título de livro e compressão de sinalização de Allen Gersho e Robert M. Gray, que fornecem vários exemplos.

Da memória, a iteração de Lloyd foi um bom algoritmo para esse tipo de coisa. Ele pode levar o conjunto de entrada e reduzi -lo a um conjunto de pontos de tamanho fixo. Basicamente, distribui uniformemente ou aleatoriamente seus pontos pelo espaço. Mapeie cada uma das suas entradas para o ponto quantizado mais próximo. Em seguida, calcule o erro (por exemplo, a soma das distâncias ou o quadrado da raiz). Em seguida, para cada ponto de saída, defina -o no centro do conjunto que mapeia. Isso moverá o ponto e possivelmente até mudará o conjunto que mapeia para ele. Execute isso iterativamente até que nenhuma alteração seja detectada de uma iteração para a seguinte.

Espero que isto ajude.