11
$\begingroup$

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)
Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – joojaa
    Commented Feb 23, 2016 at 16:17
  • $\begingroup$ @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. $\endgroup$
    – andrea.al
    Commented Feb 23, 2016 at 16:41
  • $\begingroup$ 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.) $\endgroup$
    – Martin Ender
    Commented Feb 23, 2016 at 16:49
  • $\begingroup$ @MartinBüttner Yes, I do have access to the parametric form of the curve, if it's needed. $\endgroup$
    – andrea.al
    Commented Feb 23, 2016 at 16:51
  • 1
    $\begingroup$ Please show a typical point set ! $\endgroup$
    – user1703
    Commented Feb 24, 2016 at 9:26

3 Answers 3

Reset to default
7
$\begingroup$

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:

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.
  • 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$).

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.