Finding specific shapes in point clouds quickly

Question

I've got a point cloud, and would like to detect occurrences of certain patterns of points in my code.

Let's say I have 1000 points in 3d space, and I want to detect all instances of 3 points which form an 'L' shape where each segment of the L has a specific length. The point cloud may not have exact matches, but may be very close (i.e. in the point cloud, the length of a segment of 'L' may be slightly longer/shorter than the ideal)

My initial idea was something like this:

1. record the distance between all the points in the shape we are trying to detect
2. create an empty 'potential shape'
3. for each point in our potential shape, examine all points that are at/near the distances found in part 1)
4. If we find a point, add it to our potential shape, and repeat part 3) until we have all the points. Then check the angles between the points to verify that the shape is indeed correct. If not correct, we go on to the next point and start again

The problem is that this approach has a terrible worst case running time. Ideally, I would like to have some kind of data structure to speed up my queries for 'Find all points that are between distanceMin and distanceMax away from the given point. Can someone point me to some useful data structures that might help.

I was thinking of putting all the points in an octree to speed up access time.

Any other advice on how to improve the running time? Heuristics to speed things up?

Note: The shapes I'm trying to find are variable. They will not always be an 'L'. I tried looking at hough transforms, but they seem to be useful only for detecting specific predetermined shapes like lines/circles.

Answer 1

In PCL library there's the Sample consensus module, quoting directly from the docs:

holds SAmple Consensus (SAC) methods like RANSAC and models like planes and cylinders. These can combined freely in order to detect specific models and their paramters in point clouds.

Maybe you could create some shapes combining those primitives and search for them in the cloud?.