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?

3d 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:

Images taken from mentioned-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!)

  • 1
    @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
  • 2
    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:


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! =)

  • 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
  • 2
    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
  • 2
    i already spent a day on the first link hoping it might be useful :) – vinayan Mar 20 '15 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.