Finding the Center Line from a set of 3D Points

Question

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

What sort of tools are you using or do you have available? Matlab? Excel? R? Python? — Scott Newson, Mar 19 '15 at 19:37
@ScottNewson - definitely not Matlab.I am open to any programming language. — vinayan, Mar 23 '15 at 04:24
This question/answer could help you, https://stackoverflow.com/questions/29208554/calculate-centerline-in-3d-structure — Matt, Jul 01 '17 at 19:37

Joseph · Answer 1 · 2015-03-23T12:25:19.970

7

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

edited Mar 23 '15 at 12:25

answered Mar 20 '15 at 11:46

Joseph

75,746
7
171
282

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

score 3 · Answer 2 · edited May 23 '17 at 12:39

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)

Finding the Center Line from a set of 3D Points

2 Answers2

Linked