Curve orientation
This article may be confusing or unclear to readers. In particular, the title and the lead are about curves, and the body of the article is about polygonal lines. (June 2020) |
In
In the case of a planar
The
The concept of orientation of a curve is just a particular case of the notion of
Orientation of a curve is associated with parametrization of its points by a real variable. A curve may have equivalent parametrizations when there is a continuous increasing monotonic function relating the parameter of one curve to the parameter of the other. When there is a decreasing continuous function relating the parameters, then the parametric representations are opposite and the orientation of the curve is reversed.[1][2]
Orientation of a simple polygon
In two dimensions, given an ordered set of three or more connected vertices (points) (such as in connect-the-dots) which forms a simple polygon, the orientation of the resulting polygon is directly related to the sign of the angle at any vertex of the convex hull of the polygon, for example, of the angle ABC in the picture. In computations, the sign of the smaller angle formed by a pair of vectors is typically determined by the sign of the cross product of the vectors. The latter one may be calculated as the sign of the determinant of their orientation matrix. In the particular case when the two vectors are defined by two line segments with common endpoint, such as the sides BA and BC of the angle ABC in our example, the orientation matrix may be defined as follows:
A formula for its determinant may be obtained, e.g., using the method of
If the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant is non-zero if points A, B, and C are non-
Practical considerations
In practical applications, the following considerations are commonly taken into account.
One does not need to construct the convex hull of a polygon to find a suitable vertex. A common choice is the vertex of the polygon with the smallest X-coordinate. If there are several of them, the one with the smallest Y-coordinate is picked. It is guaranteed to be a vertex of the convex hull of the polygon. Alternatively, the vertex with the smallest Y-coordinate among the ones with the largest X-coordinates or the vertex with the smallest X-coordinate among the ones with the largest Y-coordinates (or any other of 8 "smallest, largest" X/Y combinations) will do as well. Once a vertex of the convex hull is chosen, one can then apply the formula using the previous and next vertices, even if those are not on the convex hull, as there can be no local concavity on this vertex.
If the orientation of a convex polygon is sought, then, of course, any vertex may be picked.
For numerical reasons, the following equivalent formula for the determinant is commonly used:
The latter formula has four multiplications less. What is more important in computer computations involved in most practical applications, such as
When it is not known in advance that the sequence of points defines a simple polygon, the following things must be kept in mind.
For a
In "mild" cases of self-intersection, with
Local concavity
Once the orientation of a polygon formed from an ordered set of vertices is known, the
If the determinant of this matrix is 0, then the sequence is collinear - neither concave nor convex. If the determinant has the same sign as that of the orientation matrix for the entire polygon, then the sequence is convex. If the signs differ, then the sequence is concave. In this example, the polygon is negatively oriented, but the determinant for the points F-G-H is positive, and so the sequence F-G-H is concave.
The following table illustrates rules for determining whether a sequence of points is convex, concave, or flat:
Negatively oriented polygon (clockwise) | Positively oriented polygon (counterclockwise) | |
---|---|---|
determinant of orientation matrix for local points is negative | convex sequence of points | concave sequence of points |
determinant of orientation matrix for local points is positive | concave sequence of points | convex sequence of points |
determinant of orientation matrix for local points is 0 | collinear sequence of points | collinear sequence of points |
See also
- Differential geometry of curves
- Directed line segment
- Orientability
- Convex hull
- Signed arc length
References
- ^ Abraham Goetz (1970) Introduction to Differential Geometry, page 28, Addison Wesley
- John Wiley & Sons
External links
- http://www.math.hmc.edu/faculty/gu/curves_and_surfaces/curves/_topology.html Archived 2004-12-23 at the Wayback Machine (page is not found on 2023.07.27)
- Curve orientation at MathWorld