Clustering using quadtree

Editor
Mar 21, 2014 at 11:30 AM
Hi,

I need to implement some sort of clustering for a series of points that we have, I figured that seeing as I use a quadtree to store this information in my custom provider, I should be able to leverage the quadtrees nodes as a sort of cluster.

So when I zoom the map and get a new extent, I just want to get the centroid of each top level node in the extent, and display this as the 'cluster'

Is this possible with the current NTS quadtree implementation? can you get all the top level nodes for a zoom level?

Thanks
Coordinator
Mar 28, 2014 at 7:32 AM
Edited Mar 28, 2014 at 7:32 AM
Robert, I'm not sure if that will work, as the NodeBase<T>.Visit(Envelope, IItemVisitor<T>) function is not virtual, so you cannot ignore any levels (Depth) you don't want.

I assume the performance bottleneck is the rendering of the points and not the retrieval, so maybe it is worth a try to devide your viewport in a regular grid and query for points in each grid, aggregate them to a cluster point and just render that. But it sounds like quite some work to do before rendering and I don't know if it will offer any benefit.

Frank Braunschweig has created a OpenGL layer that I'm preparing for general use, it might offer better performance for puntal layers.
Editor
Mar 28, 2014 at 9:34 AM
Hi Felix,

I have to admit that since looking into this a bit more it does look like a custom implementation might be better.

I've looked at the openlayers code for clustering and it is straightforward, but it will add a fair bit of processing time. I'm wondering if there is a way to pre-generate the clusters or something to speed up rendering. I'll probably just start with something basic and then look at making it perform better.

I would certainly be interested in looking at the OpenGL Layer, and possibly try and extend it so that it can render lines and polygons too.
Editor
Mar 28, 2014 at 11:04 AM
Also kind of related to this. Has anyone seen any cases where SRT Tree doesn't return the correct values in some case? I have seen a few cases where as I zoom out it returns the correct values upto a certain zoom level, then it doesn't return anything for a few levels, then it starts to return the correct values again.