# Finding the Center Line from a set of 3D Points

I have a set of 3D points. They follow a curved pattern with a rather constant diameter as shown below. What would be the algorithm to trace the approximate center line of these points?

• Polynomial 3rd degree, Excel? Commented Mar 15, 2015 at 19:40
• What sort of tools are you using or do you have available? Matlab? Excel? R? Python? Commented Mar 19, 2015 at 19:37
• @ScottNewson - definitely not Matlab.I am open to any programming language. Commented Mar 23, 2015 at 4:24
– Matt
Commented Jul 1, 2017 at 19:37

There is a paper called "Curved Reconstruction from Unorganized Points" by In-Kwon Lee which looks into constructing lines/curves from a set of points without any ordering by exploiting the moving least-squares method. Although it focues on 2D applications, it mentions the possibility of extending this to higher dimensions. The following image is taken from the paper:

In 'Chapter 4 - 3D Extension', it describes how the method cannot be applied directly to 3 dimentions but it is possible to compute a 3D quadratic regression curve by:

• Grouping neighbouring points using the moving least-squares method
• Computing a regression plane K : z = Ax + By + C by minimizing a quadratic
• Projecting those neighbouring points to plane K and solving the 2D moving least-squares problem.

Hope this helps! (Quite an interesting paper!)

• @whuber - Thanks for checking. I edited my post as I coincidentally found a paper which may describe a possible method. Commented Mar 23, 2015 at 12:26
• Nice find! The EMST is a good choice on which to base a solution. (+1) The procedure in that paper might be improved via robust smoothing methods such as Loess or various forms of penalized spline fits. Commented Mar 23, 2015 at 14:27