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