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


2 Answers 2


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
    Commented Mar 23, 2015 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
    Commented Mar 23, 2015 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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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