How to connect unordered points by nearest neighbors without forming a loop?

Development
1

I am trying to build a vtkPolyLine from a set of unordered 3D points.

My goal is to connect the points based on nearest neighbors, not based on the input index order. I need the result to be one open polyline, not a closed loop.

What I tried so far:

  • I manually computed the nearest neighbor for each point and created a vtkPolyLine from the resulting sequence.

  • This works partially, but the algorithm eventually connects back to a previously used point and forms a loop, which I do not want.

  • I also tried simply passing the unordered points to vtkPolyLine, but it does not reorder them — the line does not make sense visually.

So my questions are:

  1. Is there a VTK filter or example that orders unordered points into a nearest-neighbor open polyline?

  2. If I need to implement the ordering myself, what is the recommended approach to ensure that a point is not reused so that the path does not close into a loop?

  3. Is there a better strategy in VTK for this kind of path construction?

Any advice or example code would be greatly appreciated.

Thanks!

vtkforu
vtkforu1062×379 30.4 KB

The left one is what i have and my goal is to create a tube filter like the right one.

2

  • I manually computed the nearest neighbor for each point and created a vtkPolyLine from the resulting sequence.

  • This works partially, but the algorithm eventually connects back to a previously used point and forms a loop, which I do not want.

It seems that you have the beginnings of an algorithm- why not keep track of/count the number of connections each point has. Interior points should have 2, at the ends just 1. So when you reach the end, just prevent the last point in your set of points from connecting to another point. Note that unless the points are distributed “properly”, you have a ill-posed problem and I doubt that you will find an algorithm that will work in all cases.