How to identify and connect lines in a 3D point cloud?

I have data containing a bunch of points in 3D space. They form numerous individual lines tangled up with one another.

I want to identify the lines and the points that describe them. At the moment, my pseudocode looks like this:

1. Pick a random point
2. Find nearest point (restrict search to small local volume)
3. Keep going until next nearest point is outside search volume
4. Call this collection of points a line
5. Repeat until no more points left

I don't think this is very efficient, and it doesn't seem to do a very good job of accurately identifying loops. Are there any better methods?

Answer 1

[Matt J]

I can't see what would be inaccurate about that method, as long as the separation between the lines is large relative to the separation between points belonging to a line, and you can choose those distance thresholds sensibly.

To potentially make the implementation faster, one thing you might do is create a 3D black and white image of the point cloud (round the coordinates to integers) and then use imdilate() to connect the lines with an appropriate-sized strel. Then, use bwconncomp to label the different lines and group the points according to label.