Clustering Algorithm for Mapping Application

Question

I'm looking into clustering points on a map (lat/longs). Are there any recommendations as to a suitable algorithm that is fast and scalable?

Answer 1

Are you clustering based on the physical locations given by the latitude and longitude?

Answer 2

Could you perhaps post some code showing what you want to accomplish? I am confused as to what exactly you mean by "clustering". Are you plotting them on a map of the world?

Answer 3

Google Maps Hacks has a hack, "Hack 69. Cluster Markers at High Zoom Levels", on that.

Also, see Wikipedia on clustering algorithms.

Answer 4

@Gilligan: Yes - I have a series of lat / lngs, and a map viewport. I'm trying to cluster the points that are close together in order to remove clutter.

I already have a solution to the problem (see here), only I am wondering if there is any formal algorithm that solves the problem efficiently.

Answer 5

For a virtual earth application I've used the clustering described here. It's lightning fast and easily extensible.

Answer 6

there is a webservice called geocubes.com. it makes server side clustering. i think it depends on how many points you have to cluster, if you should use a server side solution

Answer 7

You could look at indexing all your points using a QuadTile scheme, and then based upon the scale the further down the quad-splits you go. All similarly located points will then be near each other in your index, allowing the clustering to happen efficiently.

QuadTiles are an example of Morton Codes, and there is a python example linked from that wikipedia article that may help.