0
$\begingroup$

I would like to find a rule to determine the order of the points of arbitrary 2d splines, which should be invariant with respect to rotation (as far as possible).

Examples of arbitrary splines

To illustrate the problem, let us imagine a stick figure.

Stick Figure

No matter how the arms are positioned and no matter how the stick figure is rotated, we can always decide which hand is the left hand and which hand is the right hand. If we now add the rule that the left hand should always be labeled 1 and the right hand should always be labeled 2, then we have a consistent ordering which is not altered by rotation of the stick figure.

Unfortunately, unlike our stick figure, splines do not have a head, which greatly helps us decide on the order of the hands in case of the stick figure. Therefore, we have to come up with our own reference points.

So the question partly boils down to: What are suitable reference points?

One point that comes to mind, is the middle point of the spline, i.e. the point that cuts the spline in two equally long pieces (comparable to the point of the stick figure that connects the arms).

However, the second point (the head) is more difficult. Any point that would not be rotated along with the spline during a rotation is not suitable. One possibility would be the center of the bounding box of the spline.

I think that this setup would allow a rotationally invariant ordering of the points. However, especially for straight splines, the two reference points are very close to each other, which would make the order of the points very susceptible to slight changes of the curvature of the spline. I.e. the order would be flipped if we bent a straight spline slightly in one direction or the other.

So ultimately the question is: Could there be a better second reference point than the center of the bounding box?

Remark: I am not sure, whether this is the right community for this question or if this question even has a valid answer. Also, I am not sure, which tags to use. Therefore, any advice on more suitable communities and/or tags are very welcome.

$\endgroup$
2
  • $\begingroup$ I don't think I understand. If the spline is represented in a standard representation such as B-spline, then the parameterization defines the invariant order of the points on the spline. If it is not parameterized, then how is it represented? $\endgroup$ Apr 10, 2020 at 10:34
  • $\begingroup$ @IddoHanniel Thanks for taking your time. I'll try to clarify: A parameterized version of a spline has a certain order. However, there is no reason not to flip the order of the points, i.e. reverse the direction of the spline. The spline would still be principally the same. However, it is important for me, to have a consistent order of points. A simple rule might be: the end-point with the smallest y-coordinate is always the first point of the spline. However, if the spline is rotated, there will be an angle, where the order is flipped. I'd like to find a rule which avoids that. $\endgroup$
    – Nos
    Apr 10, 2020 at 13:23

1 Answer 1

0
$\begingroup$

First, if there is a rotational symmetry in the curve, for example a line segment or an S-shape, then you cannot achieve your goal since the 180-degree rotated curve is exactly identical to the original.

So, assuming the curve does not have rotational symmetry, what you are asking is an intrinsic property (see e.g., here) of the curve that will be invariant under rotations.

The first intrinsic property that comes to mind is the curvature profile of the curve, which is invariant to translation and rotation, and completely describes the shape of the curve.

A practical implementation can be to take the endpoint with the smaller signed curvature as the start/end point of the ordering. In the degenerate case where both endpoints have the same curvature, you can sample the curvature at a $\delta$-arc-length from both sides and take the one with smaller curvature of these. Since the curve hasn't got a rotational symmetry and the curvature profile completely describes the curve shape, at some point there will be a difference in the curvature.

Arc length is also an example of an intrinsic property, which is why the mid-length point you suggested can also be a good starting point, for example as an origin of a coordinate system that has the tangent as its x-axis (and the normal as its y-axis). However, the direction of this x-axis is not defined, which is why you needed another point.

Choosing the middle point of the bounding box of the curve, as you suggested, can work if the bounding box is aligned with the above intrinsic coordinate system. This will work in most cases except for the degenerate cases you mentioned where the mid-length point is on (or very close) to the origin.

It should be noted that the center of an axis-aligned bounding box, which is not oriented according to the above intrinsic coordinate system, is not an intrinsic property, since it moves relative to the curve shape as the curve rotates.

There can be curves for which the bounding box mid-point actually crosses the curve as it rotates, which is exactly what you want to avoid. The example figures below shows such a curve (in the figure it is a polygonal line, but a similar curved spline can be constructed), with its axis-aligned bounding box and its mid-point, under two rotational configurations. One can see that as the curve rotates the mid-point moves from one side of the curve to the other.

enter image description here enter image description here

$\endgroup$
1
  • $\begingroup$ Thanks a lot! I think I can work something out with these suggestions. $\endgroup$
    – Nos
    Apr 13, 2020 at 15:06

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.