I want to cluster a point cloud in a 3D space (maybe with 200k points). For this I'm locking for a botom up approach.
My goal is, that I can change the granularity of the clustering with a interaction in a user interface and get a fast feedback in visualization.
My first idea is to use a hierarchical cluster algorithm, like average-link. So I can navigate in the depth of the tree if I change the granularity and get a fast feedback. But it take a long time to create such a tree, isn't it O(n^2)?
My next idea is to use a density clustering like OPTICS. But after I change the granularity (here count of clusters), I must recluster all points. This can take a long time to get a feedback?
I also think about a simple kd-tree. This approach is very fast and create a hierarchical tree (like average-link). The problem is, that the kd-tree is only a approximation and I don't know how good the results are..
Has anybody ideas or experiances to clustering points to a cloud? Thank you