title: Map Clustering Algorithm
body: <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 =&gt; $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 &lt; $distance) {
              unset($markers[$key]);
              $cluster[] = $compareMarker;
          }
      }
  
      // If a marker was added to cluster, also add the marker we were comparing to.
      if (count($cluster) &gt; 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)) &gt;&gt; (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 &gt;&gt; $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 =&gt; $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 &lt; $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) &gt; 0) {
          $cluster[] = $marker;
          $clusterMarkers[] = $cluster;
      } else {
          $singleMarkers[] = $marker;
      }
  }
  </code></pre>