Server side clusters of coordinates based on zoom level

Question

Thanks to this answer I managed to come up with a temporary solution to my problem.

However, with a list of 6000 points that grows everyday it's becoming slower and slower.

I can't use a third party service* therefore I need to come up with my own solution.

Here are my requirements:

1. Clustering of the coordinates need to work with any zoom level of the map.

2. All clusters need to be cached

3. Ideally there won't be a need to cluster (calculate distances) on all points if a new point is added.

So far I have implemented quadtree that returns the four boundaries of my map and returns whatever coordinates are within the viewable section of the map.

What I need and I know this isn't easy is to have clusters of the points returned from the DB (postgres).

Answer 1

I don't see why you have to "cluster" on the fly. Summarize at each zoom level at a resolution you're happy with.

Have a simply structure of X, Y, # of links. When someone adds a link, you insert the real locations (Zoom level max, or whatever), then start bubbling up from there.

Eventually you'll have 10 (if you have 10 zoom levels) sets of distinct coordinates, one for each different zoom level.

The calculation is trivial, and you only have to do it once.

Answer 2

I am currently doing dynamic server-side clustering of about 2,000 markers, but it runs pretty quick up to 20,000. You can see discussion of my algorithm here:

Map Clustering Algorithm

Whenever the user moves the map I send a request with the zoom level and the boundaries of the view to the server, which clusters the viewable markers and sends it back to the client.

I don't cache the clusters because the markers can be dynamically filtered and searched - but if they were pre-clustered it would be super fast!