Software Programming

Kunuk Nykjaer

Google Maps Server-side Clustering with Asp.net C#

with 34 comments


  • 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.


googlemapclustering

Google Maps Clustering Viewport:

Here is the overview of how the viewport works.
googlemaps-clustering-viewport

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.

googlemapclustering SD

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.

Advertisements

Written by kunuk Nykjaer

November 5, 2011 at 6:46 pm

34 Responses

Subscribe to comments with RSS.

  1. 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

  2. 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

  3. 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

  4. 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

  5. @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

  6. 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

  7. 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

  8. @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

  9. 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

  10. @ 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

  11. 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

  12. 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

  13. 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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: