StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMap Clustering Algorithm
text
Body
copied!<p>My current code is pretty quick, but I need to make it even faster so we can accommodate even more markers. Any suggestions?</p> <p>Notes:</p> <ul> <li>The code runs fastest when the SQL statement is ordered by marker name - which itself does a very partial job of clustering the markers (the names of markers in the same location are often, but not always similar).</li> <li>I can't pre-cluster the markers, because they can be dynamically searched and filtered.</li> <li>I've tried grid-based clustering - but the results often aren't very nice.</li> <li>I know that the clusters are slightly skewed on a Mercator projection.</li> <li>I'm not interested in a commercial clustering service.</li> </ul> <p>The code:</p> <pre><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 } </code></pre> <hr> <p><strong>UPDATE</strong></p> <p>Here's the current code:</p> <pre><code>$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; } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload