Orientation (topology)
From Wikipedia, the free encyclopedia
In topology, orientation is the direction in which a simple closed curve made up of three or more vertices is traversed. 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.
[edit] Determining orientation for a simple closed polygon
In two dimensions, given an ordered set of connected 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 flat, we construct the matrix
If the determinant of this matrix is 0, then the sequence is flat - 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 | flat sequence of points | flat sequence of points |
