Curve orientation

Last updated August 27, 2023

In mathematics, an orientation of a curve is the choice of one of the two possible directions for travelling on the curve. For example, for Cartesian coordinates, the $x$ -axis is traditionally oriented toward the right, and the $y$ -axis is upward oriented.

In the case of 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), the curve is said to be positively oriented or counterclockwise oriented, if one always has the curve interior to the left (and consequently, the curve exterior to the right), when traveling on it. Otherwise, that is if left and right are exchanged, the curve is negatively oriented or clockwise oriented. This definition relies on the fact that every simple closed curve admits a well-defined interior, which follows from the Jordan curve theorem.

The inner loop of a beltway road in a country where people drive on the right side of the road is an example of a negatively oriented (clockwise) curve. In trigonometry, the unit circle is traditionally oriented counterclockwise.

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

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

Selecting reference points. Determining orientation.png — Selecting reference points.

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:

\mathbf {O} ={\begin{bmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{bmatrix}}.

A formula for its determinant may be obtained, e.g., using the method of cofactor expansion:

{\begin{aligned}\det(O)&=1{\begin{vmatrix}x_{B}&y_{B}\\x_{C}&y_{C}\end{vmatrix}}-1{\begin{vmatrix}x_{A}&y_{A}\\x_{C}&y_{C}\end{vmatrix}}+1{\begin{vmatrix}x_{A}&y_{A}\\x_{B}&y_{B}\end{vmatrix}}\\[4pt]&=x_{B}y_{C}-y_{B}x_{C}-x_{A}y_{C}+y_{A}x_{C}+x_{A}y_{B}-y_{A}x_{B}\\[4pt]&=(x_{B}y_{C}+x_{A}y_{B}+y_{A}x_{C})-(y_{A}x_{B}+y_{B}x_{C}+x_{A}y_{C}).\end{aligned}}

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-collinear. In the above example, with points ordered A, B, C, etc., the determinant is negative, and therefore the polygon is clockwise.

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:

\det(O)=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})

The latter formula has four multiplications less. What is more important in computer computations involved in most practical applications, such as computer graphics or CAD, the absolute values of the multipliers are usually smaller (e.g., when A, B, C are within the same quadrant), thus giving a smaller numerical error or, in the extreme cases, avoiding the arithmetic overflow.

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 self-intersecting polygon (complex polygon) (or for any self-intersecting curve) there is no natural notion of the "interior", hence the orientation is not defined. At the same time, in geometry and computer graphics there are a number of concepts to replace the notion of the "interior" for closed non-simple curves; see, e.g., "flood fill" and "winding number".

In "mild" cases of self-intersection, with degenerate vertices when three consecutive points are allowed be on the same straight line and form a zero-degree angle, the concept of "interior" still makes sense, but an extra care must be taken in selection of the tested angle. In the given example, imagine point A to lie on segment BC. In this situation the angle ABC and its determinant will be 0, hence useless. A solution is to test consecutive corners along the polygon (BCD, DEF,...) until a non-zero determinant is found (unless all points lie on the same straight line). (Notice that the points C, D, E are on the same line and form a 180-degree angle with zero determinant.)

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

\mathbf {O} ={\begin{bmatrix}1&x_{F}&y_{F}\\1&x_{G}&y_{G}\\1&x_{H}&y_{H}\end{bmatrix}}.

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

Related Research Articles

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants (the preceding property is a corollary of this one). The determinant of a matrix $A$ is denoted $det(A)$ , $det A$ , or $| A |$ .

In mathematics and computational geometry, a Delaunay triangulation for a given set $P$ of discrete points in a general position is a triangulation $DT(P)$ such that no point in $P$ is inside the circumcircle of any triangle in $DT(P)$ . Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

In geometry, a polygon is a plane figure made up of line segments connected to form a closed polygonal chain.

<span class="mw-page-title-main">Tetrahedron</span> Polyhedron with 4 faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the ordinary convex polyhedra.

In Euclidean geometry, an affine transformation or affinity is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.

<span class="mw-page-title-main">Graham scan</span> Algorithm for computing convex hulls in a set of points

Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary efficiently.

<span class="mw-page-title-main">Convex polygon</span> Polygon that is the boundary of a convex set

In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, they are piecewise-linear Jordan curves consisting of finitely many line segments. They include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $-dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.$

In computer graphics, back-face culling determines whether a polygon of a graphical object is drawn. It is a step in the graphical pipeline that tests whether the points in the polygon appear in clockwise or counter-clockwise order when projected onto the screen. If the user has specified that front-facing polygons have a clockwise winding, but the polygon projected on the screen has a counter-clockwise winding then it has been rotated to face away from the camera and will not be drawn.

In geometry, the circumscribed circle or circumcircle of a triangle is a circle that passes through all three vertices. The center of this circle is called the circumcenter of the triangle, and its radius is called the circumradius. The circumcenter is the point of intersection between the three perpendicular bisectors of the triangle's sides, and is a triangle center.

In geometry, collinearity of a set of points is the property of their lying on a single line. A set of points with this property is said to be collinear. In greater generality, the term has been used for aligned objects, that is, things being "in a line" or "in a row".

<span class="mw-page-title-main">Orthogonal convex hull</span> Minimal superset that intersects each axis-parallel line in an interval

In geometry, a set $K \subset R d$ is defined to be orthogonally convex if, for every line $L$ that is parallel to one of standard basis vectors, the intersection of $K$ with $L$ is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.

A rectilinear polygon is a polygon all of whose sides meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

In geometry, a vertex is a point where two or more curves, lines, or edges meet. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, etc. of the box.

<span class="mw-page-title-main">Shoelace formula</span> Mathematical algorithm

The shoelace formula, shoelace algorithm, or shoelace method is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane. It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like threading shoelaces. It has applications in surveying and forestry, among other areas.

In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints. In geometry, a line segment is often denoted using a line above the symbols for the two endpoints.

References

↑ Abraham Goetz (1970) Introduction to Differential Geometry, page 28, Addison Wesley
↑ Chuan-Chih Hsiung (1981) A First Course in Differential Geometry, page 84, John Wiley & Sons

External links

http://www.math.hmc.edu/faculty/gu/curves_and_surfaces/curves/_topology.html (page is not found on 2023.07.27)
Curve orientation at MathWorld

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Abraham Goetz (1970) Introduction to Differential Geometry, page 28, Addison Wesley

[2] Chuan-Chih Hsiung (1981) A First Course in Differential Geometry, page 84, John Wiley & Sons

[1]

[2]