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")
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).
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?
