Curve orientation
From Wikipedia, the free encyclopedia
In mathematics, a positively oriented curve is a planar simple closed curve (that is, a curve in the plane whose starting point is also the end point and which has no other self-intersections) such that when traveling on it one always has the curve interior to the left (and consequently, the curve exterior to the right). If in the above definition one interchanges left and right, one obtains a negatively oriented curve.
Crucial to this definition is the fact that every simple closed curve admits a well-defined interior; that follows from the Jordan curve theorem.
All closed curves can be classified as negatively oriented (clockwise), positively oriented (counterclockwise), or non-orientable. The inner loop of a beltway road in the United States (or other countries where people drive on the right side of the road) would be an example of a negatively oriented (clockwise) curve. A circle oriented counterclockwise is an example of a positively oriented curve. The same circle oriented clockwise would be a negatively oriented curve.
The concept of orientation of a curve is just a particular case of the notion of orientation of a manifold (that is, besides orientation of a curve one may also speak of orientation of a surface, hypersurface, etc.). Here, the interior and the exterior of a curve both inherit the usual orientation of the plane. The positive orientation on the curve is then the orientation it inherits as the boundary of its interior; the negative orientation is inherited from the exterior.
Contents |
[edit] Determining orientation for a simple closed planar polygon[1]
In two dimensions, given an ordered set of three or more connected vertices (points) (such as in connect-the-dots), it is possible to calculate the orientation of the resulting polygon using the determinant of an orientation matrix. To do this, an endpoint on the convex hull of the polygon is selected as a reference point. An endpoint that lies on the bounding box of the polygon is also acceptable, since any endpoints on the bounding box will also lie on the convex hull. In this example, point B is chosen as the reference point. Then, two points which are non-collinear with the reference point, one before the reference point in the sequence and one after (A and C, respectively) are chosen and used to construct the orientation matrix
The orientation of the polygon is then calculated by finding the determinant of this matrix. This can be done most easily using the method of cofactor expansion:
If the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant should never be 0 if points A, B, and C are chosen so that they are non-collinear. In the above example, with points ordered A, B, C, etc., the determinant is negative, and therefore the polygon is clockwise.
[edit] Local concavity
Once the orientation of a polygon formed from an ordered set of vertices is known, the concavity of a local region of the polygon can be determined using a second orientation matrix. This matrix is composed of three consecutive vertices which are being examined for concavity. For example, in the polygon pictured above, if we wanted to know whether the sequence of points F-G-H is concave, convex, or collinear (flat), we construct the matrix
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 |
