I have a collection of 3D discrete curves $\{C_i\}$, each with a different number of points $N_i$: $$ C_i = [p^i_0, p^i_1, ..., p^i_{N_i}] \text{ with } p^i_k=[x^i_k, y^i_k, z^i_k] \text{ i.e. } C_i \text{ a } 3 \times N_i \text{ matrix } $$ I would like to sort the points along all these curves in the same "order". More formally, considering two curves $ C_i$ and $C_j$ having the same number $N$ of points (even if this is not the case, this can be obtained by interpolation), they will have the same order if: $$ \sum_{k=1}^{N} ||p^i_k - p^j_k||^2 < \sum_{k=1}^{N} ||p^i_{N-k} - p^j_k||^2 $$ (and reciprocally will have a different order if the first sum is greater than the second "reverse sum")

enter image description here

The image illustrates one of the sum. For the "reverse sum", you have to imagine adding the distance between the first point of the red line and the last point of the blue line, the second point of the red line and the last but one point of the blue line, etc.

Informally, finding the order of a curve $C_i$ is like choosing which point between $p^i_0$ and $p^i_{N_i}$ should be the first point, for all the curves $C_i$ to have the same general "orientation".

I am looking for a method independent of all the curves data, i.e. based on a general formula to be applied to each curve individually. One can assume that all curves have the same number of points (but obviously not the same distance between points, as the curves have different length). Currently, after transforming the curves to each have $N$ points (equally separated [along a given curve]), I came up with the idea of:

  • Considering a given curve $C_i$
  • Computing the "non-reverse sum" $D_{+,x}$ between $C_i$ and the reference "$x$-curve" of the points $[1, 2, ..., N]$ along the $x$-axis, i.e. $$D_{+,x} = \sum_{k=1}^{N} ||p^i_k - x^i_k||^2$$ where $x^i_k$ is the point with coordinates $(k, 0, 0)$.
  • Similarly computing the "non-reverse sum" $D_{+,y}$ between $C_i$ and the reference "$y$-curve", and $D_{+,z}$ between $C_i$ and the reference "$z$-curve"(the rationale being that a curve orthogonal to the $x$-axis, will have the same sum and "reverse sum", so using the $x$-axis alone is not enough)
  • Computing $D_+ = D_{+,x} + D_{+,y} + D_{+,z}$, the sum of these three "non-reverse sums"
  • Computing all the "reverse sums" (e.g $D_{-,x} = \sum_{k=1}^{N} ||p^i_{N-k} - x^i_k||^2$ for the $x$-axis) and adding them together: $D_- = D_{-,x} + D_{-,y} + D_{-,z}$
  • Choosing the order (between $p^i_k$ and $p^i_{N-k}$) providing the smallest sum (i.e. if $D_-$ is smallest, then the order of the original points will be flipped)

I feel this heuristic computation is missing the big picture. For example I can feel that my calculations are related to testing if for spherical coordinates $(r, \theta, \phi)$ the derivative of $r$ is positive or negative on average. This is still quite foggy in my mind and I am sure there are more brilliant/knowledgeable people here who can point to a better / more theoretically grounded algorithm.

Another issue is that this will not work for all curves, in particular those having $x$, $y$, $z$ symmetry and the same portion of points going away from the origin, than going towards the origin (as can be understood from the description above). Below is an illustration of this kind of curves (most of them can be seen to have a kind of U-shape).

enter image description here

I feel that a solution would be to combine $r$, $\theta$ and $\phi$ as in this case, even if the $r$-related sums $D_+$ and $D_-$ do not allow to identify an absolute stable sorting, $\theta$- or $\phi$-related metrics would as the curves can be seen to be clearly oriented in either increasing $\theta$ or $\phi$. So a combination of metrics based on these three spherical coordinates seem promising. This is just what I came up with so far though and can be safely totally ignored.

What is important is simply the main question: would anyone know of an existing algorithm to choose a "correct" (i.e. absolute and relatively stable) points ordering for each curve, for them to be in the same general orientation?

  • $\begingroup$ How do you define a 'discrete' curve in 3D? Is it just a curve with several chosen points? Probably, a more formal description is due. $\endgroup$ – Mikhail Tikhomirov Sep 29 '17 at 11:06
  • $\begingroup$ Sure, i will try to clarify, thank you $\endgroup$ – michael Sep 29 '17 at 14:38
  • $\begingroup$ Are you familiar with the Fréchet distance? I used the same image you are using in an earlier Fréchet distance question. $\endgroup$ – Joseph O'Rourke Sep 29 '17 at 20:19

There is quite a bit of work on what is called curve reconstruction. If there is any noise in your points coordinates, or even if the sampling is not dense in high-curvature sections, naive algorithms will fail. The paper below is perhaps more robust than you need, but is typical of algorithms that have been developed. It uses moving least squares and the Euclidean minimum spanning tree:

Lee, In-Kwon. "Curve reconstruction from unorganized points." Computer aided geometric design 17.2 (2000): 161-177. (ACM link.)


Probably the best source is Tamal Dey's book, as he develops algorithms with provable guaranteed performance:

Dey, Tamal K. Curve and surface reconstruction: Algorithms with mathematical analysis. Vol. 23. Cambridge University Press, 2006. (Author's webpage.)

  • $\begingroup$ Dear @joseph, thanks a lot for your answer, this is an interesting algorithm. However this quite different from the actual problem I was describing and my sincere apologies if I was not clear. I rewrote my original post extensively. $\endgroup$ – michael Sep 29 '17 at 15:40
  • $\begingroup$ @michael: Apologies for misinterpreting your question, and thanks for rewriting it. (But now I don't feel I understand it enough to offer a suggestion.) $\endgroup$ – Joseph O'Rourke Sep 29 '17 at 20:25

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.