<p>You have an instance of a problem called <em>curve reconstruction from unorganized points</em>. Now that you know what to search for you'll find several methods, such as the crust, NN-crust, etc. Here are a few links:</p>

<ul>
<li><p><a href="http://sarielhp.org/research/CG/applets/Crust/Crust.html">The Crust Curve Reconstruction Applet</a></p></li>
<li><p><a href="http://web.cse.ohio-state.edu/~tamaldey/curverecon.htm">Curve Reconstruction</a> by Tamal Dey</p></li>
<li><p><a href="https://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521863704">Curve and Surface Reconstruction: Algorithms with Mathematical Analysis</a>, book by Tamal K. Dey, Cambridge University Press, 2006</p></li>
</ul>

<p>Since you're dealing with curves and the samples are dense, I suggest you compute an Euclidean minimal spanning tree.</p>

CC BY-SA 3.0
2016-02-23T17:59:07.243Z
2016-02-23T17:59:07.243Z
lhf
<p>After some clarifications, there is probably a much better approach that doesn't even require knowing the parametric form of the curve, and also avoids the potentially problematic numeric minimisation step. </p>

<p>If the curve does not intersect itself and the points are sufficiently densely packed on the curve (and by that I mean they have to be closer than any two points on the curve that <em>don't</em> belong to the same segment, e.g. by the curve wrapping around on itself), then you can easily determine the previous and next point to each sample:</p>

<ul>
<li>Determine the two nearest neighbours to each point. <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors" rel="nofollow">That's an $O(n \log n)$ operation</a>.</li>
<li>You'll have to do some special treatment for the endpoints. Their two nearest neighbours will be the next <em>two</em> points along the curve instead of one on each side. You can either detect these heuristically if the ratio  of the distances to the two neighbours differs by more than some threshold (1.5 say, depends on the smoothness of your curve and how densely the points are packed). Or you can treat your nearest-neighbour data as a graph, in which you'll find that the endpoints' two neighbours point at each other (which shouldn't happen anywhere else in the graph).</li>
<li>Now you can simply pick one end point, and walk along the nearest neighbours (always choosing the one you didn't arrive from) to traverse the points along the curve.</li>
</ul>

<p>Especially if you can make the points very dense this should be the most reliable option unless the curve self-intersects. Even in that case, this approach might be salvageable provided the self-intersection is at a sufficiently large angle the curve smooth enough (in that case you can choose the correct neighbours based on some constraint that successive steps cannot make an angle greater than some threshold $\theta$).</p>

CC BY-SA 3.0
2016-02-23T16:48:34.430Z
2016-02-23T16:48:34.430Z
Martin Ender
<p>Since you've only got floating-point representations of the points, there is no guarantee that these still lie exactly on the curve, due to rounding errors. So I think the only generic approach is to approximate where on the curve they were, by finding the closest point on the curve to your sample $(X,Y,Z)$. E.g. if your parametric curve is $(x(t), y(t), z(t))$ then you could try to minimise</p>

<p>$$
(X-x(t))^2+(Y-y(t))^2+(Z-z(t))^2
$$</p>

<p>with respect to $t$. If you know what type of curve you're dealing with there might be nice analytic solutions to this, otherwise you'll have to resort to some numerical algorithm. Since your points should be very close to the curve, this method should be reliable (provided the minimisation algorithm is), unless you have a sample exactly where the curve (almost) crosses itself. In that case you're probably out of luck anyway, though.</p>

<p>Once you have that $t$ for each of your points, you can simply sort them by $t$. Of course, if you have any control over how you receive the points you might be able to sidestep all of this trouble by returning $t$ along with the point's coordinates right away while generating them.</p>

CC BY-SA 3.0
2016-02-23T16:09:39.853Z
2016-02-23T16:09:39.853Z
Martin Ender
<p>I have a set of 3D points (which I recover from a library that performs the tessellation of a solid body) that belong to a curve (i.e., an edge of the solid). That means that the curve surely passes by each of these points.</p>

<p>Nevertheless, the point set is unordered so I need to sort them in order to be able to draw this curve correctly.</p>

<p>Is there any known approach for these type of problem?</p>

<p>Some additional information:</p>

<ul>
<li>The curves are parametric in general (splines/bezier, circle slices.. ). </li>
<li>The points are given as floating point coordinates.</li>
<li>The points are packed very densely (but they can be as dense as I want it to be). To give you an idea, for a curve which occupies 19 units in x, 10 units in x and 5 units in z, I quote a sequence of points in a segment of curve: (20.7622, 25.8676, 0) (20.6573, 25.856, 0) (20.5529, 25.8444, 0) (20.4489, 25.8329, 0) (20.3454, 25.8213, 0)</li>
</ul>

CC BY-SA 3.0
2016-02-23T16:17:59.463Z
Even if we know the order theres till a infinite number of curves that fit trough the points. Even if we add additional constraints, then the open ends are problematic as their tangent orientation can be arbitrary. A [picture here](http://i.imgur.com/nlWqkRT.png)
joojaa
CC BY-SA 3.0
2016-02-23T16:41:32.440Z
@joojaa Yes, you are right. But since the packing of points is very dense, I don't expect it to be exact. If I do get to have the right order, I was planning to connect the sequence of points as a polyline.
andrea.al
CC BY-SA 3.0
2016-02-23T16:49:33.153Z
In the code that needs to order the points, are you even aware of the parametric form of the curve? (If not, I'll delete my first answer, because it requires you to know the parametric form.)
Martin Ender
CC BY-SA 3.0
2016-02-23T16:51:17.707Z
@MartinBüttner Yes, I do have access to the parametric form of the curve, if it's needed.
andrea.al
CC BY-SA 3.0
2016-02-23T17:29:49.320Z
@andrea.al i do secondary curve fitting for cad data all the time and I was not entirely happy with the results every second time. Thats why I have started to inject normal's to the starting points for the fitting. Problem is that curves tend to lose it in certain situations.
joojaa
<geometry><mesh><curve>
Ordering a set of unorganized points along a curve
andrea.al
# Ordering a set of unorganized points along a curve

(Asked by: username_0 on 2016-02-23)

I have a set of 3D points (which I recover from a library that performs the tessellation of a solid body) that belong to a curve (i.e., an edge of the solid). That means that the curve surely passes by each of these points.

Nevertheless, the point set is unordered so I need to sort them in order to be able to draw this curve correctly.

Is there any known approach for these type of problem?

Some additional information:

* The curves are parametric in general (splines/bezier, circle slices.. ).
* The points are given as floating point coordinates.
* The points are packed very densely (but they can be as dense as I want it to be). To give you an idea, for a curve which occupies 19 units in x, 10 units in x and 5 units in z, I quote a sequence of points in a segment of curve: (20.7622, 25.8676, 0) (20.6573, 25.856, 0) (20.5529, 25.8444, 0) (20.4489, 25.8329, 0) (20.3454, 25.8213, 0)

**Tags:** geometry, mesh, curve

> **Comments:**
> **username_1**: Even if we know the order theres till a infinite number of curves that fit trough the points. Even if we add additional constraints, then the open ends are problematic as their tangent orientation can be arbitrary. A [picture here](http://i.imgur.com/nlWqkRT.png)  
> **username_0**: @username_1 Yes, you are right. But since the packing of points is very dense, I don't expect it to be exact. If I do get to have the right order, I was planning to connect the sequence of points as a polyline.  
> **username_2**: In the code that needs to order the points, are you even aware of the parametric form of the curve? (If not, I'll delete my first answer, because it requires you to know the parametric form.)  
> **username_0**: @MartinBüttner Yes, I do have access to the parametric form of the curve, if it's needed.  
> **username_1**: @username_0 i do secondary curve fitting for cad data all the time and I was not entirely happy with the results every second time. Thats why I have started to inject normal's to the starting points for the fitting. Problem is that curves tend to lose it in certain situations.  

---

## 3 answers

### Answer by username_3 on 2016-02-23. Score: 7

You have an instance of a problem called *curve reconstruction from unorganized points*. Now that you know what to search for you'll find several methods, such as the crust, NN-crust, etc. Here are a few links:

* [The Crust Curve Reconstruction Applet](http://sarielhp.org/research/CG/applets/Crust/Crust.html)
* [Curve Reconstruction](http://web.cse.ohio-state.edu/~tamaldey/curverecon.htm) by Tamal Dey
* [Curve and Surface Reconstruction: Algorithms with Mathematical Analysis](https://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521863704), book by Tamal K. Dey, Cambridge University Press, 2006

Since you're dealing with curves and the samples are dense, I suggest you compute an Euclidean minimal spanning tree.


---

### Answer by username_2 on 2016-02-23. Score: 4

After some clarifications, there is probably a much better approach that doesn't even require knowing the parametric form of the curve, and also avoids the potentially problematic numeric minimisation step.

If the curve does not intersect itself and the points are sufficiently densely packed on the curve (and by that I mean they have to be closer than any two points on the curve that *don't* belong to the same segment, e.g. by the curve wrapping around on itself), then you can easily determine the previous and next point to each sample:

* Determine the two nearest neighbours to each point. [That's an $O(n \log n)$ operation](https://en.wikipedia.org/wiki/Nearest_neighbor_search#All_nearest_neighbors).
* You'll have to do some special treatment for the endpoints. Their two nearest neighbours will be the next *two* points along the curve instead of one on each side. You can either detect these heuristically if the ratio of the distances to the two neighbours differs by more than some threshold (1.5 say, depends on the smoothness of your curve and how densely the points are packed). Or you can treat your nearest-neighbour data as a graph, in which you'll find that the endpoints' two neighbours point at each other (which shouldn't happen anywhere else in the graph).
* Now you can simply pick one end point, and walk along the nearest neighbours (always choosing the one you didn't arrive from) to traverse the points along the curve.

Especially if you can make the points very dense this should be the most reliable option unless the curve self-intersects. Even in that case, this approach might be salvageable provided the self-intersection is at a sufficiently large angle the curve smooth enough (in that case you can choose the correct neighbours based on some constraint that successive steps cannot make an angle greater than some threshold $\theta$).


---

### Answer by username_2 on 2016-02-23. Score: 3

Since you've only got floating-point representations of the points, there is no guarantee that these still lie exactly on the curve, due to rounding errors. So I think the only generic approach is to approximate where on the curve they were, by finding the closest point on the curve to your sample $(X,Y,Z)$. E.g. if your parametric curve is $(x(t), y(t), z(t))$ then you could try to minimise

$$
(X-x(t))^2+(Y-y(t))^2+(Z-z(t))^2
$$

with respect to $t$. If you know what type of curve you're dealing with there might be nice analytic solutions to this, otherwise you'll have to resort to some numerical algorithm. Since your points should be very close to the curve, this method should be reliable (provided the minimisation algorithm is), unless you have a sample exactly where the curve (almost) crosses itself. In that case you're probably out of luck anyway, though.

Once you have that $t$ for each of your points, you can simply sort them by $t$. Of course, if you have any control over how you receive the points you might be able to sidestep all of this trouble by returning $t$ along with the point's coordinates right away while generating them.


---

