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;
    }
}
InformationsquelleAutor Chris B | 2009-09-16