Clustering markers using quadtree

Question

I have a POSTGIS database with geography points and I want to cluster the points using quad-tree. I have a map where I have to display the markers clustered or non clustered depending on the zoom level so I can't really use k-means algorithm because I can't fix k.

How can I implement quad-tree in my application?

Please tell me if I am wrong somewhere.

What I have tried
I have tried clustering in the front-end but it doesn't help to solve my problem. With a large number of markers that doesn't work. I want to send the clusters instead of all the markers.

Answer 1

This will not be ideal, but it will produce results, and you could refine it to produce something closer to an idea result with some custom code:

• add a column to your table ALTER TABLE foo ADD COLUMN geohash varchar
• populate it with the geohash UPDATE foo SET geohash = ST_Geohash(geom)
• query for different overview levels using substrings of the geohash SELECT Count(*), st_makepoint(avg(st_x(geom)), avg(st_y(geom))) as geom FROM foo GROUP BY substring(geohash,1,5)

The density of the overview levels will vary depending on what value you use for the substring (5 in this example), with larger numbers being more dense.

Geohash embeds as much information as it can in each character, so it's not an ideal key for overviews in powers-of-two based mapping apps. If you can make the example above work, you might consider writing your own hash key using something like the Bing Maps tile system (especially if you're mapping in web mercator)