Google Maps Server-side Clustering with Asp.net C#
- This project is available at Github
- Original project location is available at Google Code
For a project in my work I made a server-side clustering of data to be displayed in Google Maps.
The clustering is a grid-based clustering using geo-stationary grid-placement.
I was impressed by the performance of the solution from Maptimize
They have this example webside Crunch Panorama
I wanted to make something similar and have made an example project of server-side clustering. The demo can be seen here Google Maps Clustering. The grid has been included in the view for demonstration. Clusters that are close to each other are merged.
The search options is included by example code from Cibul Tech Blog.
Google Maps Clustering Viewport:
Here is the overview of how the viewport works.
Client-server Ajax communication demonstration:
This Google Maps clustering project uses two webservice methods: GetMarkers and GetMarkerDetail.
The GetMarkers method returns the marker and cluster information and GetMarkerDetail method returns specific information for a selected marker.
GetMarkers method:
The client sends the boundary of the screen using Norht-east and South-west latlon point and the zoom level.
Client json get markers request:
{"nelat":"62.511244050310154","nelon":"30.008460312500006",
"swlat":"47.574956142655","swlon":"-5.235680312499994","zoomlevel":"5"}
The server does the server-side clustering based on the information from the client and returns only the data that is to be displayed to the client. Here it is two markers with latlon information. When the count (the C) is larger than 1, then it is a cluster marker, else it is a details marker. The details marker has the I and T information set. The I is the id and the T is type information.
Server json show markers reply:
{"Points":[
{"Y":"56.05777","X":"9.30294","C":1624,"I":"","T":""},
{"Y":"55.09446","X":"15.11401","C":"1","I":"aa005c3b-9301-4040-bac3-3dee8cb29b48","T":"2"}
]}
The client examines the reply and removes markers that should no longer be visible and only adds new marker to the screen. The latlon and count information are used to build a key for identifying unique marker objects.
GetMarkerDetail method:
The client sends a details request for a specific marker using an id-information.
Client json get marker detail: request
{"id":"aa005c3b-9301-4040-bac3-3dee8cb29b48"}
The server replies by giving content for the specific marker.
Server json show marker detail reply:
{"Content":"CONTENT INFORMATION HERE"}
Math information
The centroid calculation is based on circular mean. This is because the longitude overlaps at -180 and 180 degrees. There are no overlapping using latitude with Google Maps (haven’t seen or noticed it).
The distances are calculated using Euclidean distance. This calculation is fast and it is good enough for clustering the points into a cluster.
You usually only need as a maximum 6 decimal precision when using latlon and Google Maps. This gives within 1 meter precision.
The grid-size is fixed and adapts to the zoom level.
By doing one step zooming in Google Maps the latlon window range is doubled or halved.
The geo-stationary grid-placement indexes are achieved using divide and modulus calculation.
Time complexity is on average(m*n) and space complexity is O(m*n)
where n is the number of points used in total and m is the number of grids returned to the client.
You are welcome to analyse it yourself and correct me. I use hashset and hashmap to minimize the time complexity. For fast enough response time (below 1 sec) the number of markers should be max 300.000.
Time complexity is ~ O(n^2) on worst case but extremely unlikely,
happens if most centroids are merged with neighbor-centroids.
The DB in this project is a simple file with list of points which is loaded in the memory. The algorithm uses linear search and can (probably) be improved using spatial data structure.
Software Programming 
Super cool, is there a place where i canfind the source code or buy an example?
thanks,
Wouter
W247 webdesign
November 12, 2011 at 5:50 pm
I was wondering when there would be a comment about getting to see the code 🙂
I have not released the code yet. It is good enough for regional areas, but not for world wide clustering yet. I haven’t fully tested in the area at 180 longitude. In other words area around New Zealand might be buggy. I might make an alpha code be available later in this year. I still want to play around with it before releasing the server-side code.
The client js code can be seen here. (the ajax code and logic for updating visible markers on the screen)
http://jory.dk/AreaGMC/Scripts/mapclustering.js
kunuk Nykjaer
November 12, 2011 at 10:07 pm
Looking forward to it
Let me know of i can help or contribute in one way or another
Regards
W
W247 webdesign
November 13, 2011 at 1:02 am
the link to your JS is broken… would have liked to have a look in there 🙂
Simon Ball
December 2, 2011 at 5:44 pm
It should be fixed now
kunuk Nykjaer
December 4, 2011 at 6:40 pm
The project is now available at http://code.google.com/p/google-maps-server-side-clustering-dotnet/
kunuk Nykjaer
December 10, 2011 at 10:45 am
Hi,
Awesome work!! I’ve been trying to do something like this for ages.
A question….I would like the map ‘onload’ to set the default bounds to be that of all markers, by that I mean zoom in as far as you can before markers are out of view. I have various combinations of the following:
var latlngbounds = new google.maps.LatLngBounds();
latlng.each(function(n){
latlngbounds.extend(n);
});
map.setCenter(latlngbounds.getCenter());
map.fitBounds(latlngbounds);
This doesn’t work. It zooms in way too far so that no markers are visible until you zoom out again.
Have you got any suggestions?
Many thanks, Mike Reed
Mike
February 23, 2012 at 6:34 pm
For Google maps api help
I think you should try to ask at http://stackoverflow.com/questions/tagged/google-maps-api-3
If I can’t make it work with Google maps api I usually make the logic server-side 🙂
and return the zoom, position, etc.. using ajax
kunuk Nykjaer
March 10, 2012 at 6:50 pm
[…] https://kunuk.wordpress.com/2011/11/05/google-map-server-side-clustering-with-asp-net/ […]
what is the best way to store a lot of markers in database? | appsgoogleplus.com
April 13, 2012 at 5:14 pm
Excellent work! Would you have any suggestions on how to make the library more extensible in terms of defining ones own ‘P’ class.
Your GridCluster constructor takes a Collection of ‘P’ objects and getCluster() returns a collection of ‘P’ s. This is somewhat limiting as a developer may want to have additional logic or extra fields on top of what is defined in ‘P’.
Initially I tried subclassing P but quickly realised this wouldnt work due to (co/contra)variance issues with generic Lists, although generic interfaces are now supported in c#4. So my quick fix was to modify Gridcluster (and its base)to take an IEnumerable instead of List and call toList when assigning the dataset. This worked quite well and even preserved the sub class data when serializing back to JSON.
Lastly, the javascript ‘marker clusterer’ library gives a handy utility function to get the contained markers in a cluster. I’d like to replicate this (by returning a list of id’s or lat/lng’s or something) but I’m unsure of where to start. I understand it’d be somewhat ridiculous to pass this data back along the wire when there are a significant number of points contained in a cluster. But I do have a scenario where there are 2 or 3 points at max zoom that are still clustered(e.g. in the exact same location) and I’d like to get there associated data on click of the cluster. I’d love to hear any suggestions you have. Thanks again for the good work.
Stephens Jones
April 15, 2012 at 11:05 pm
As i was dealing with 18k+ points, i used a stored procedure to return clusters and markers in one table, which my webservice converted to a json to pass to the ajax, and jqueried the display to act differently o click of marker or cluster icon…
and i had same problem of small groups of markers on exact same spot..I made min cluster size a parameter of my stored procedure, and then used a table of offset factors, got the dimensions in lat and lng and modified any points below min cluster of matching latlng to be offset slightly and displayed as markers. Had a slight downside that some of my markers for homes got shunted into the sea….
Simon Si Ball
April 16, 2012 at 12:07 am
I’d thought of offsetting the markers myself but figured it was a messy option both visually and technically. The js marker cluster library worked perfectly as I wired up a client ‘onclick’ to a cluster icon to check if the map was at max zoom and if so, make a service request passing the id’s of the markers that were contained in the cluster (cluster.getMarkers()) and display a list popup (custom gmap overlay) instead of the standard popup. So what i need to figure out now is how to replicate that in kunuk’s library.
Stephens Jones
April 16, 2012 at 12:32 pm
Thanks for you input. I might look into the code and improve it.
I made it possible to configure the minimum-size of a cluster.
It should be in the SVN in the project. Can’t remember when I added it. Not sure if it is included in version 2.
http://code.google.com/p/google-maps-server-side-clustering-dotnet/wiki/FAQ
Q. How do I set the minimum count of points level before a cluster is made?
A. Increase or decrease the value in Kunukn.GooglemapsClustering.Clustering.Config.MinClusterSize
e.g. you can control not to cluster if cluster-mark only contains few items.
There is also the possibility to stop clustering from zoom level x.
Q. When does the clustering stops?
A. You can define at which zoom-level the clustering should stop. In the file mapclustering.js in the settings set a value for zoomlevelClusterStop.
kunuk Nykjaer
April 16, 2012 at 9:25 pm
nice work! have you tested your clusterer with 1000’s of markers. interested on its performance. I tried the basic clusterer.js on win xp decent spec machine with 1million markers and it was a bit slow to render the map, so i went with sql returning a table of clusters+ ,markers. mine is only at 18k growing about 2k a month though.
Simon Si Ball
April 16, 2012 at 10:41 pm
Hi, Thanks for the reply. The min size of cluster wasn’t what I was looking for.
What I meant was, could each ‘centroid’ store a list of contained ‘Points’ and pass that back in the client json. This would be handy for Points that can’t be un-clustered (e.g. they have the exact same lat/lng ).
Anyway, I got it to work by adding a property (List containedIds) to the ‘P’ class and populating it in ClusterAlgorithmBase.GetClusterResult() just before populating the centroid count property.
So now at maxzoom when two or more points are at the exact same location and still clustered, I can wire up a client click handler that can use the id’s to query the data source and display a list of whatever entities are at that location.
By the way i set a flag not to populate the centroids contained points if there are over 20 (or whatever is configured) to keep json traffic down.
Hope you get what I mean. Just thought it’d be a nice addition.
This is an great project and thanks again for your work.
Stephens Jones
April 16, 2012 at 10:51 pm
@Simon, do you mean you are clustering at the database level?
Stephens Jones
April 16, 2012 at 11:03 pm
Yes. My SQL stored procedure accepts @bounds, @minclustersize and @gridx & @gridy, and then breaks the big boundary into a sequence of grid squares. These are then passed as mini-boundaries to a separate stored procedure which returns markers for each square… if the number of markers is greater than the @mincluster param, then the markers are summarised into a cluster, and some stats properties returned, otherwise they are returned as markers, but first are checked for identical latlongs, which are then offset when found so that the markers are not all on the same spot on the final map.
Simon Si Ball
April 22, 2012 at 9:09 pm
hi.thanks for your perfect blog.
how can i use this software as offline?
i want use this software for showing markers in the map with in where that i do not allowes to use internet for connecting to google map .
can i cache google map and use cached maps ?
hamid
April 19, 2013 at 12:43 pm
I have no experience with Google maps offline, maybe ask at stackoverflow? e.g. http://stackoverflow.com/questions/6109369/how-to-cache-google-map-tiles-for-offline-usage
kunuk Nykjaer
April 22, 2013 at 10:14 am
How do you Calacute Gridx and Gridy on client side based on zoom level?
Sam Pa
September 10, 2014 at 12:52 am
In the latest code I have refactored gridx and gridy to be defined server-side in the file GmcGlobalKeySettings.config
kunuk Nykjaer
September 12, 2014 at 1:10 pm
how do you know what to set it to? in your code you set to 6,5 resp? what should set it to?
Sam Pa
September 19, 2014 at 1:22 am
@Sam Pa
You set to the values to what you want. The grid will be more dense and there will be more clusters for higher gridx, gridy values.
If you are curious how the calculation works on server-side look for in code.
public static double[] GetDelta(int gridx, int gridy, int zoomlevel){...
}
kunuk Nykjaer
September 19, 2014 at 4:41 pm
OK. Got it. Thank you for your help. This article really helped a lot.
Sam Pa
September 22, 2014 at 7:05 pm
Hi, I am having an issue about markers not clustered together even if they are very close(zoom level=11). Possible reason I think is gridCluster id (idx;idy) is differenet for each of them. can you please tell me how to fix it?
Thanks
Sam Pa
October 14, 2014 at 10:06 pm
Do you have the lat lon values for the markers?
kunuk Nykjaer
October 15, 2014 at 10:08 pm
so the thing is, at zoom level 13, I have a cluster with count = 650 and when I click on it I expect it to show sub clusters (of smaller sizes) at zoom level 11 . instead of that it justs show all 650 markes with no clustering because gridCluster Id (idx;idy) generated for each of them is different so all are shown as individual markers instead of sub clusters of size 100,150, etc..
There are lots of them but just a sample out of it. (they are shown on top of each other)
1) Grid Markers Size: 178 Grid Center Latitude(Y): 32.755294870786514, Grid Center Longitude(x): -117.16955705617978
2) Grid Markers Size: 128 Grid Center Latitude(Y): 32.71078509375, Grid Center Longitude(x): -117.16110703906253
3) Grid Markers Size: 127 Grid Center Latitude(Y): 32.72378554330709, Grid Center Longitude(x): -117.17462272440947
I was trying to fix it by limiting idx and idy to 2 digits so they are clustered but no luck.
I want to work as the example you have mentioned above.
Thank you.
Sam Pa
October 16, 2014 at 12:03 am
@ Sam Pa I tried with this data
# lon; lat; id; type
-117.16955705617978;32.755294870786514;1;1
-117.16110703906253;32.71078509375;2;2
-117.17462272440947;32.72378554330709;3;3
I couldn’t see anything wrong. (master branch from github)
You could try to lower the MergeWithin from the GmcGlobalKeySettings.config file to e.g. 2, to make neighbors to merge more often.
I could look more into it is you paste the marker data in e.g. pastebin.com with the config data from GmcGlobalKeySettings.config
kunuk Nykjaer
October 16, 2014 at 9:00 pm
My Config settings
————————-
outer grid extend = 0
grid x = 7
grid y=6
merge Within = 1.9
Restricting idx and idy of cluster to 2 digits will solve the problem?
Reason is cluster id is different for each marker so they can not be clustered.
for eg: idx;idy would be 900;12345 and 903;12349
basically they are very near but in merging cluster we only check the neighbor cluster with (cluster id + 1) and so they don’t merge
Sam Pa
October 23, 2014 at 1:14 am
@Sam Pa
Try set to MergeWithin” value=”0,05″ (or 0.05) dependent on locale culture.
Then with breakpoint in method MergeClustersGridHelper in the class GridCluster
Make sure that the GmcSettings.Get.MergeWithin value is very low decimal value as expected.
You should see in the Google Maps that it merges the clusters on the map very aggressively.
If this doesn’t work as you expect then I need some test data. I tested with the markers from the github code.
I don’t think restricting idx and idy of cluster to 2 digits is a solution. They are index numbers which can have large values.
kunuk Nykjaer
October 23, 2014 at 10:46 pm
I changed above settings and tried with some other data and all seem to work fine. Thank you for your help.
Sam Pa
November 5, 2014 at 12:25 am
i need map like this link http://www.zoocasa.com/en/search/properties?center=49.276054%2C-123.123904&zoom=12&utf8=%E2%9C%93&search_type=listings&location=Vancouver%2C+BC&utf8=%E2%9C%93&search%5Bsort%5D=created_at+DESC&search%5Bprice_min%5D=0&search%5Bprice_max%5D=&search%5Bbedrooms%5D=0%2B&search%5Bbathrooms%5D=1%2B&search%5Bhouse%5D=1&search%5Bstyle%5D%5Bhouse_detached%5D=1&search%5Bstyle%5D%5Bhouse_attached%5D=1&search%5Bstyle%5D%5Bhouse_new_development%5D=1&search%5Bstyle%5D%5Bhouse_other%5D=1&search%5Bparking%5D=any&search%5Bcondo%5D=1&search%5Bstyle%5D%5Bcondo_highrise%5D=1&search%5Bstyle%5D%5Bcondo_lowrise%5D=1&search%5Bstyle%5D%5Bcondo_new_development%5D=1&search%5Bstyle%5D%5Bcondo_other%5D=1&search%5Bparking_spaces%5D=0%2B&search%5Blocker%5D=any&search%5Bmaintenance_fee%5D=&utf8=%E2%9C%93&search%5Bcompliance_boards%5D=brc_reb4_van for that what should i do for this ?
vikrant
February 6, 2015 at 1:23 pm
Hi,
How can I find out the distance in meters of single cell, So I can say that the points are getting clustered within this distance.
Regards,
P
Prashant
March 28, 2016 at 7:55 am
Hi,
Is it possible to convert DeltaX and DeltaY values into meters or any other measurement unit?
While margining clusters In MergeClustersGridHelper() method, algorithm uses “minDistX / minDistY” values. I want to map this values to measurement unit like meter of kilometer.
It would be great, if you can provide any formula for conversion.
Regards,
Prashant
Prashant
March 28, 2016 at 3:31 pm
[…] Google Maps Server-side Clustering with Asp.net C# […]
what is the best way to store a lot of markers in database? Craft JS
January 25, 2018 at 10:18 pm
[…] Google Maps Server-side Clustering with Asp.net C# […]
¿Cuál es la mejor manera de almacenar una gran cantidad de marcadores en la database? JavaScript ES
April 8, 2019 at 5:18 am
Thanks after 8 years still so useful! A nice addition would be to pre-generate grids on the db for each zoom level. So you can offload the work let’s say at night and let some service generate all the grids, OR regenerate them whenever some markers are added/deleted or position changed
Max
December 30, 2020 at 4:08 pm