We continue set of articles about interesting technology areas and solutions we have implemented or encountered in our projects.
This article briefly describes our experience in development interesting component for multiple markers/objects on google maps in web application.
Our solution
For one of our projects we required to show more than 20,000 elements at the same time on google maps in web browsers. Objects coordinates are taken from our server-side service and we should have dynamic filtering of this data on client side. Straight-forward javascript approach with placing Google Maps API markers didn’t work well as the page worked extremely slow and that was unacceptable.
There are several approaches how to solve this problem:
- Grid-Based Clustering — it works by dividing the map into squares of a certain size (the size changes at each zoom) and then grouping the markers into each grid square.
- Distance-based clustering — it is similar to grid-based clustering, except instead of creating clusters of fixed square bounds, clusters are created based on the distance between the marker and a cluster centroid. Cluster centroids are generally specified algorithmically through iteration of the existing marker locations.
- Viewport marker management — restricting the markers rendered on the map into only those that exist within the viewable area.
- Server-side clustering — when client side of the Map knows only about groups of objects but not each object separately, e.g. using GeoHash.
- Server-side overlay — custom overlay that displays markers with minimal functionality. This approach may garner performance improvements over standard markers provided by the API.
- Platform specific solutions — Google Maps for Android already has Clustering API functions.
After reviewing and testing available solutions (see links below) and considering writing our own version, we have decided that Marker Clusterer, which implements client side grid based clustering, satisfies us the most at the moment.
Interesting Challenges
- We have found that any solution that is based on client-side rendering doesn’t work well with large number of markers (e.g. when approaching 10,000) and at later stages of the project we might switch to our own optimized version based on server side clustering/filtering similar to geohash.
Definitions
Geohash is a latitude/longitude geocode system invented by Gustavo Niemeyer when writing the web service at geohash.org, and put into the public domain. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape.
