For some volume reconstruction algorithm I'm working on, I need to detect an arbitrary number of circular patterns in 3d point data (coming from a LIDAR device). The patterns can be arbitrarily oriented in space, and be assumed to lie (although not perfectly) in thin 2d planes. Here is an example with two circles in the same plane (although remember this is a 3d space):
I tried many approaches.. the simplest (but the one working best so far) is clustering based on disjoint sets of the nearest neighbor graph. This works reasonably well when the patterns are far apart, but less so with circles like the ones in the example, really close to each other.
I tried K-means, but it doesn't do well: I suspect the circular point arrangement might not be well suited for it. Plus I have the additional problem of not knowing in advance the value of K.
I tried more complicated approaches, based on the detection of cycles in the nearest neighbor graph, but what I got was either too fragile or computationally expensive.
I also read about a lot of related topics (Hough transform, etc) but nothing seems to apply perfectly in this specific context. Any idea or inspiration would be appreciated.