>>> [!note] Migrated issue <!-- Drupal.org comment --> <!-- Migrated from issue #1662432. --> Reported by: [dasjo](https://www.drupal.org/user/228295) >>> <p>This is a raw idea that evolved since <a href="http://drupal.org/user/122682/">Nick_vh</a> pointed me to Geohash during Drupal Dev Days Barcelona 2012.</p> <p>There are different clustering techniques, the main i'm focusing at is geared towards distance based clustering on maps. You can think of it as an in-Drupal implementation of <a href="http://www.maptimize.com/">http://www.maptimize.com/</a></p> <h3>Background</h3> <p>Geohash is easy to understand by reading the <a href="http://en.wikipedia.org/wiki/Geohash">Geohash Wikipedia article</a> or trying an <a href="http://openlocation.org/geohash/geohash-js/">Interactive Geohash demonstration website</a>. But it is also very well described by David Smiley in his presentations on spatial search with Solr and Geohashes:</p> <ul> <li> <a href="http://www.basistech.com/pdf/events/open-source-search-conference/oss-2011-smiley-geospatial-search.pdf">http://www.basistech.com/pdf/events/open-source-search-conference/oss-2011-smiley-geospatial-search.pdf</a> </li> <li><a href="http://www.lucidimagination.com/sites/default/files/Lucene%20Rev%20Preso%20Smiley%20Spatial%20Search.pdf">http://www.lucidimagination.com/sites/default/files/Lucene%20Rev%20Preso%20Smiley%20Spatial%20Search.pdf</a></li> </ul> <p>So Geohash is a lat/lon geocode system with a hierarchical spatial structure and gradual precision degradation.<br> For example Boston would be encoded as "DRT2Y". </p> <p>The longer the prefix is that two points share, the nearer those points are. As the reverse isn't necessarily true, edges have to be considered for proximity searches (and clustering): Two points might be close to each other, but positioned next to edges of the hierarchical grid defined by the geohash algorithm.</p> <h3>Idea</h3> <ol> <li>Calculate a grid level for clustering appropriate to the current zoom level (so that when visualizing points per grid, they shouldn't overlap)</li> <li>Do a group-by query on the defined grid level</li> <li>For all points returned for a grid <ol> <li>Create a cluster (combine all points within the grid)</li> <li>Set it's new center point (centroid of the points or simpler: )</li> <li>Mark the grids that will be affected, that the cluster overlaps </li><li>If a grid has already been marked by another cluster, merge those and repeat </li></ol> </li> <li>Clustering complete</li> </ol> <p>The above algorithm is neither complete nor tested. While there are more sophisticated clustering algorithms out there, I think it might be a good fit for the use case of clustering on web maps. Using the grid-approach of geohashes allows to quickly identify clusters, which basically eliminates the need for complex distance calculations.</p> <p>The grid-size would have to be chosen according to the pixel size of cluster / marker icons, so that they don't overlap. The additional steps solve the problem of creating a static grid and overlapping points at grid edges. The clusters don't align directly to the grid but their center points are calculated dynamically by calculating the center of the bounding box around the involved points. The bounding box then is used to mark neighbor grids. Clashes should be detected and merged not in a perfect by performant way.</p> <p>I will try to visualize the described steps in the near future to better communicate the algorithm. In the meanwhile, i would like to mention an interesting post that explains a similar approach:<br> <a href="http://web.archive.org/web/20071121140547/http://trib.tv/tech/clustering-points-on-a-google-map/">Grid based viral growth argorithm (archived blog post)</a>.</p> <h3>Steps</h3> <p>In order to see this work with <strong>Drupal-tools</strong>, I think we need <a href="https://github.com/phayes/geoPHP/issues/32">Add geohash support to geoPHP</a> and potentially also <span class="drupalorg-gitlab-issue-link project-issue-status-info project-issue-status-7"><a href="https://www.drupal.org/project/geofield/issues/1662584" title="Status: Closed (fixed)">#1662584: Add geohash support?</a></span> in <a href="http://drupal.org/project/geofield">Geofield</a>.</p> <p><strong>Solr integration</strong> for Geohash should already be provided, as of the above mentioned presentations by David Smiley. Though, I haven't tested them so far. Also see the related <a href="http://wiki.apache.org/solr/SpatialSearch#SOLR-2155">Spatial Search SOLR-2155 documentation</a>.</p>