Carte Algorithme De Clustering
Mon code actuel est assez rapide, mais j'ai besoin de le faire encore plus vite afin que nous puissions accueillir encore plus de marqueurs. Des suggestions?
Notes:
- Le code s'exécute le plus rapide lors de l'instruction SQL est commandé par le nom de la marque - qui lui-même fait un très partielle de la tâche de clustering marqueurs (les noms de marqueurs dans le même emplacement sont souvent, mais pas toujours la même).
- Je ne peux pas pré-cluster les marqueurs, car ils peuvent être dynamiquement recherchés et filtrés.
- J'ai essayé de la grille de regroupement, mais les résultats ne sont souvent pas très agréable.
- Je sais que les clusters sont légèrement inclinés sur une projection de Mercator.
- Je ne suis pas intéressé par un commercial service de cluster.
Le code:
$singleMarkers = array();
$clusterMarkers = array();
while (count($markers)) {
$marker = array_pop($markers);
$cluster = array();
//Compare marker against all remaining markers.
foreach ($markers as $key => $compareMarker) {
//This function returns the distance between two markers, at a defined zoom level.
$pixels = pixelDistance($marker['lat'], $marker['lng'], $compareMarker['lat'], $compareMarker['lng'], $zoomLevel);
//If two markers are closer than defined distance, remove compareMarker from array and add to cluster.
if ($pixels < $distance) {
unset($markers[$key]);
$cluster[] = $compareMarker;
}
}
//If a marker was added to cluster, also add the marker we were comparing to.
if (count($cluster) > 0) {
$cluster[] = $marker;
$clusterMarkers[] = $cluster;
} else {
$singleMarkers[] = $marker;
}
}
function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) {
$x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels.
$y1 = $lat1*10000000;
$x2 = $lon2*10000000;
$y2 = $lat2*10000000;
return sqrt(pow(($x1-$x2),2) + pow(($y1-$y2),2)) >> (21 - $zoom); //21 is the max zoom level
}
Mise à JOUR
Voici le code actuel:
$singleMarkers = array();
$clusterMarkers = array();
//Minimum distance between markers to be included in a cluster, at diff. zoom levels
$DISTANCE = (10000000 >> $ZOOM) / 100000;
//Loop until all markers have been compared.
while (count($markers)) {
$marker = array_pop($markers);
$cluster = array();
//Compare against all markers which are left.
foreach ($markers as $key => $target) {
$pixels = abs($marker['lat']-$target['lat']) + abs($marker['lng']-$target['lng']);
//If the two markers are closer than given distance remove target marker from array and add it to cluster.
if ($pixels < $DISTANCE) {
unset($markers[$key]);
$cluster[] = $target;
}
}
//If a marker has been added to cluster, add also the one we were comparing to.
if (count($cluster) > 0) {
$cluster[] = $marker;
$clusterMarkers[] = $cluster;
} else {
$singleMarkers[] = $marker;
}
}
Vous devez vous connecter pour publier un commentaire.
Avez-vous réellement besoin de calculer la La distance euclidienne? Si vous êtes juste de comparer l'ampleur relative des distances, vous pouvez probablement vous en sortir avec l'aide de la Distance Manhattan, qui vous permettra d'économiser deux appels à
pow()
et un àsqrt()
:Vous ne savez pas si vous avez besoin de la
>> (21 - $zoom)
peu dans vos calculs, alors je l'ai laissé dans. Mais à moins que vous avez réellement besoin d'utiliser le calcul des valeurs de distance de ailleurs, vous pouvez probablement vous en sortir avec juste l'aide de la latitude/longitude directement (pas besoin de multiplier par quoi que ce soit) et en prenant de la distance Manhattan, en supposant que vous avez pré-calculer$distance
à s'adapter à cette mesure, qui sera beaucoup moins cher dans le calcul des termes que le fait de contraindre toutes les distances pour s'adapter avec les unités et l'ampleur de$distance
.EDIT: Quand je faisais des recherches sur ce problème l'année dernière, j'ai trouvé quelques trucs utiles sur Wikipedia - oui, il peut arriver 😉
Je peux également vous recommande fortement le livre La Programmation De L'Intelligence Collective: La Construction Intelligente Des Applications Web 2.0 qui va dans le regroupement en grande profondeur, que s'applique non seulement à des données géographiques, mais également à d'autres domaines de l'analyse des données.
Étendre sur ce que Jean dit, je pense que vous devriez essayer d'inlining cette fonction. Les appels de fonction en PHP sont très lent, de sorte que vous devriez obtenir une bonne accélération à partir de cela.
Voici donc ce que j'ai fait - j'ai ajouté deux colonnes supplémentaires pour les marqueurs(point) de la table avec la projection de mercator valeurs converties pour la latitude et la longitude à l'aide des fonctions suivantes:
De cette façon que j'ai pu obtenir placées avec précision les clusters. Je suis encore en train de travailler sur la façon d'éviter d'utiliser array_pop et le vélo à travers tous les temps. Jusqu'à présent, son assez efficace avec des sous-1000 marqueurs. Je vais poster les résultats pour +5K et +10K marqueurs plus tard.
En évitant les pixelDistance de la fonction et de l'avoir inline augmente les performances de près de la moitié!
Il semble que l'accélération de la pixelDistance() la fonction pourrait faire partie de la solution, puisqu'il fonctionne à l'intérieur de la boucle. C'est un bon endroit pour regarder en premier, mais vous n'avez pas inclure ce code, donc je ne peux pas en être sûr.
Je peux voir les deux autres améliorations possibles ici:
Pouvez-vous juste de la boucle au moyen de marqueurs
avec une boucle for au lieu de sauter
hors de la matrice? Le tableau popping est complètement inutile - vous devriez vraiment être à l'aide de tableaux comme des files d'attente si vous êtes ajout et suppression d'éléments dans les mêmes temps (que vous ne l'êtes pas, vous êtes juste de les traiter puis de les jeter)
Vous devriez essayer de calcul de la
comte (le) de la tableaux de à la
début, puis augmenter manuellement
ou de la diminution de $variable nombre.
Recalculer la taille d'un tableau
chaque tour de boucle, c'est du gaspillage.
Voici quelques idées que vous pouvez mettre en œuvre dans le cas où la performance est d'une grande question:
les données: vous avez des données 2d de long/lat,
peut-être que vous pouvez essayer de le projeter
en bas à 1D en utilisant quelque chose comme
Multidimensional Scaling (MDS) qui
essaie de réduire le nombre de
dimensions tout en préservant la
les distances dans l'espace d'origine, donc la fonction de distance ne avoir à traiter avec une fonctionnalité au lieu de deux. Une alternative est d'utiliser L'analyse en composantes principales (PCA)
la distance de chaque marqueur peut être
l'amélioration de l'aide KD-trees.
Deux de ces techniques sont appliquées dans un paramètre en mode hors connexion, ils sont généralement calculé une fois et ensuite utilisé à de nombreuses reprises..
Une simple optimisation serait de profiter de sqrt(x) < sqrt(y) est vrai ssi x < y, de sorte que vous pouvez omettre la racine carrée de la pixelDistance et calculer $le carré de la distance à l'extérieur de la boucle. Vous pouvez également calculer le 21 - $zoomLevel en dehors de la boucle, vous aurez à le multiplier par 2 si vous utilisez la comparaison de la valeur carrée. Une autre petite optimisation serait d'enregistrer 2 multiplie par faire $x1-$x2 avant mise à l'échelle par 10000000. Et pour un tout petit peu plus, le stockage de la delta en var et en le multipliant par lui-même est probablement plus rapide que la fonction pow. Et de plus, vous pouvez insérer le pixeldistance fonction. Ce type d'optimisation ne le rendement d'un facteur constant de l'accélération.
Pour une plus grande accélération, vous aurez besoin d'une sorte d'accélération de discbased. Facile serait de bin marqueurs de distance en carrés de tailles. Ensuite, vous pouvez exécuter sur les bacs de rechercher des marqueurs de cluster avec seulement dans la même poubelle et 3 autres, choisi en fonction de la côté de du centre de la cuve le marqueur de tombe. Cela se traduira dans le temps linéaire de clustering qui va battre tout les optimisations de l'algorithme quadratique pour les plus grands jeux de résultats.
Si vous le pouvez, de sorte que vos marqueurs en fonction de la longitude sur la recherche initiale; puis, dès qu'un marqueur est plus qu'un marqueur de la largeur de la prochaine marqueur dans la liste triée, vous savez certainement que les autres marqueurs ne se chevauchent pas, de sorte que vous pouvez ensuite casser la boucle foreach et vous épargner une tonne de temps de traitement. J'ai mis en œuvre ce sur mon propre site et il fonctionne très efficacement.
J'ai quelques code source en Python ici.