Établir la moyenne d'un ensemble de points sur une carte Google dans un ensemble plus petit

Question

J'affiche une petite carte Google sur une page Web à l'aide de l'API Google Maps statique.

J'ai un ensemble de 15 coordonnées, que je voudrais représenter comme points sur la carte. En raison de la carte assez petite (184 x 90 pixels) et de la limite supérieure de 2 000 caractères sur une URL Google Maps, je ne peux pas représenter chaque point sur la carte. Donc à la place je voudrais générer une petite liste de coordonnées qui représente une moyenne de la grande liste. Donc, au lieu d'avoir 15 ensembles, je finirais avec 5 ensembles, dont les positions approchent les positions des 15. Disons qu'il y a 3 points qui sont plus proches les uns des autres que de tout autre point sur le carte, ces points seront réduits en 1 point.

Donc je suppose que je cherche un algorithme qui peut faire cela.

Ne pas demander à qui que ce soit d'épeler chaque étape, mais peut-être me diriger vers un principe mathématique ou une fonction générale pour ce genre de chose?

Je suis sûr qu'une fonction similaire est utilisée dans, disons, un logiciel graphique, lors de la pixellisation d'une image.

(Si je résous cela, je serai sûr de poster mes résultats.)

Answer 1

Je recommande K-means clustering lorsque vous avez besoin de regrouper des objets N dans un nombre connu K < N de groupes, ce qui semble être votre cas . Notez qu'un cluster peut se retrouver avec un seul point aberrant et un autre avec 5 points très proches les uns des autres: c'est OK, il ressemblera plus à votre jeu original que si vous avez forcé exactement 3 points dans chaque cluster! -)

Answer 2

En général, je pense que la zone que vous devez rechercher est "Vector Quantization". J'ai un vieux titre de livre Vector Quantization and Compression de signal par Allen Gersho et Robert M. Gray qui fournit un tas d'exemples. De mémoire, l'itération de Lloyd était un bon algorithme pour ce genre de choses. Il peut prendre l'ensemble d'entrée et le réduire à un ensemble de points de taille fixe. Fondamentalement, uniformément ou au hasard répartir vos points autour de l'espace. Mappez chacune de vos entrées au point quantifié le plus proche. Calculez ensuite l'erreur (par exemple, la somme des distances ou Root-Mean-Squared). Ensuite, pour chaque point de sortie, placez-le au centre de l'ensemble qui correspond à celui-ci. Cela va déplacer le point et peut-être même changer l'ensemble qui lui correspond. Effectuez cette itération jusqu'à ce qu'aucune modification ne soit détectée d'une itération à l'autre.

Espérons que cela aide.

Answer 3

Si vous êtes recherche pour de telles fonctions/classes, jetez un oeil à MarkerClusterer et MarkerManager classes utilitaires. MarkerClusterer correspond étroitement à la fonctionnalité décrite, comme vu dans this demo.