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? 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. – Joseph Mar 23 '15 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. – whuber Mar 23 '15 at 14:27

This question has been already answered. Here is the same question:

curve-fitting-3d-data-set

If you are looking for ready to use tools and codes, there are many numerical methods to solve this problem, like greedy approach which is implemented in R packages, downloadble from GAM.

If you are looking for pure algorithms to implement it yourself, I suggest you to ask it in math community (http://math.stackexchange.com)

Furthermore this wiki page is related to your question (http://en.wikipedia.org/wiki/Curve_fitting)

EDIT: Well, looks like it is wrong answer, the fitting line is straight! =)

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

• can you provide an example? – nickves Mar 18 '15 at 6:23
• What do mean? URLs are in the answer. – Mr. Che Mar 18 '15 at 6:32
• I hate to downvote answers, because I always appreciate the effort and goodwill they reflect, but I am annoyed to discover--after looking at all three references--that not one of them actually answers the question. They dance around simple variations of it, such as fitting a straight line or an ellipsoid to the points. – whuber Mar 19 '15 at 20:31
• i already spent a day on the first link hoping it might be useful :) – vinayan Mar 20 '15 at 3:58