Data reduction of 3D points

Question

[This is my first post to CrossValidated, I hope I'm not off-topic]

I have data consisting of ~10^6 points in 3D space. We want to try out some surface fitting algorithms that cannot handle this high number of points. So I would like to to use some means of data reductions (maybe ~1:100 needed) - clustering seems appropriate to me here. The data contains a lot of almost identical points.

Does anyone know a reasonable simple algorithms with an available implementation? Implementation in python, octave or matlab is preferred. I could roll my own, but I think this should have been solved before.

Answer 1

What did you try?

Assuming that this is physical data, have a look at DBSCAN (see Wikipedia). There are plenty of implementations around. Some are not correct, some are really slow (Weka), some have index support for acceleration and support lots of extensions (ELKI).

Anyway, you can probably easily set MinPts and Epsilon.

You might even want to use a pre-clustering instead, such as Canopy Clustering. It is like DBSCAN, but it doesn't connect the groups it discovered. It will just compute this "cover" of the data set.

In fact, a balanced index structure could probably also help you. Have a look at M-trees. If you discard the leaf level, and use the representative points on the level above, you should get a reduction of about 1:k when k is the average page fill.