Software Programming

For a project in my work I made a server-side clustering of data to be displayed in Google Maps.
The result can be seen here.

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.

To reduce the running time, the range search could be used. Here is an example of range search in C#. But it would only help if you are zoomed in. If you are zoomed all the way out you will have to iterate all the points then you would have to rely on pre-clustering (offline clustering) for fast runtime response.

I might look into that some day and try to increase the number of markers to millions while keeping fast enough response time.

The project is available at Google Code

A simple application that displays 213 countries and islands of the world with a search option.
Works with latest version of Chrome, Firefox, Safari, Opera and Internet Explorer.

With dropdown and search option
http://world.kunuk.dk

The SVG file only
http://world.kunuk.dk/WorldCountries.svg

The app is one HTML and SVG file. The HTML uses JQuery.
The list of countries are extracted to HTML from the SVG file using javascript. The DOM of the SVG is updated from the HTML to the SVG (hope this makes sense). The country information is extracted using Ajax with JSONP format and JQuery.

I got the inspiration when I saw this game made in SVG http://files.myopera.com/orinoco/svg/WorldCountries.svg
Now you have a tool to cheat the game