HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 -axis is traditionally oriented toward the right, and the -axis is upward oriented. In the case of a planar
simple closed curve In topology, the Jordan curve theorem asserts that every ''Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an "exterior" region containing all of the nearby and far away exterior ...
(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 In topology, the Jordan curve theorem asserts that every '' Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an " exterior" region containing all of the nearby and far away exteri ...
. The
inner loop Inner loop may refer to: * Inner loop in computer programs * Inner Loop (Phoenix), a section of Interstate 10 in downtown Phoenix, Arizona, United States * Inner Loop (Rochester), an expressway around downtown Rochester, New York, United States * I ...
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 Two-dimensional rotation can occur in two possible directions. Clockwise motion (abbreviated CW) proceeds in the same direction as a clock's hands: from the top to the right, then down and then to the left, and back up to the top. The opposite ...
) curve. In
trigonometry Trigonometry () is a branch of mathematics that studies relationships between side lengths and angles of triangles. The field emerged in the Hellenistic world during the 3rd century BC from applications of geometry to astronomical studies. T ...
, the
unit circle In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucl ...
is traditionally oriented
counterclockwise Two-dimensional rotation can occur in two possible directions. Clockwise motion (abbreviated CW) proceeds in the same direction as a clock's hands: from the top to the right, then down and then to the left, and back up to the top. The opposite ...
. The concept of ''orientation'' of a curve is just a particular case of the notion of
orientation Orientation may refer to: Positioning in physical space * Map orientation, the relationship between directions on a map and compass directions * Orientation (housing), the position of a building with respect to the sun, a concept in building de ...
of a
manifold In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a n ...
(that is, besides orientation of a curve one may also speak of orientation of a
surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...
,
hypersurface In geometry, a hypersurface is a generalization of the concepts of hyperplane, plane curve, and surface. A hypersurface is a manifold or an algebraic variety of dimension , which is embedded in an ambient space of dimension , generally a Euclidean ...
, etc.).


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 Connect the dots (also known as connect-the-dots, dot to dot, or join the dots) is a form of puzzle containing a sequence of numbered dots. When a line is drawn connecting the dots the outline of an object is revealed. The puzzles frequently c ...
) which forms a
simple polygon In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If ...
, the orientation of the resulting
polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
is directly related to the sign of the angle at any
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet * Vertex (computer graphics), a data structure that describes the positio ...
of the
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
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 In mathematics, the cross product or vector product (occasionally directed area product, to emphasize its geometric significance) is a binary operation on two vectors in a three-dimensional oriented Euclidean vector space (named here E), and is ...
of the vectors. The latter one may be calculated as the sign of the
determinant 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 ...
of their orientation matrix. In the particular case when the two vectors are defined by two
line segment 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 ...
s 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 = \begin 1 & x_A & y_A \\ 1 & x_B & y_B \\ 1 & x_C & y_C \end. A formula for its determinant may be obtained, e.g., using the method of
cofactor expansion In linear algebra, the Laplace expansion, named after Pierre-Simon Laplace, also called cofactor expansion, is an expression of the determinant of an matrix as a weighted sum of minors, which are the determinants of some submatrices of . Spec ...
: : \begin \det(O) &= 1 \begin x_B & y_B \\ x_C & y_C\end -1 \begin x_A & y_A \\ x_C & y_C \end +1 \begin x_A & y_A \\ x_B & y_B \end \\ pt&= x_B y_C - y_B x_C - x_A y_C + y_A x_C + x_A y_B - y_A x_B \\ pt&= (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 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 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 (sometimes spelled as colinear). In greater generality, the term has been used for aligned ...
. 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 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 ...
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 Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
or
CAD Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve co ...
, 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 In software engineering and mathematics, numerical error is the error in the numerical computations. Types It can be the combined effect of two kinds of error in a calculation. * the first is caused by the finite precision of computations involv ...
or, in the extreme cases, avoiding the
arithmetic overflow Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers—addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th cen ...
. 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 The term ''complex polygon'' can mean two different things: * In geometry, a polygon in the unitary plane, which has two complex dimensions. * In computer graphics, a polygon whose boundary is not simple. Geometry In geometry, a complex polygo ...
) (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 Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
and
computer graphics Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
there are a number of concepts to replace the notion of the "interior" for closed non-simple curves; see, e.g., "
flood fill Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill c ...
" and "
winding number In mathematics, the winding number or winding index of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point, i.e., the curve's number of turn ...
". In "mild" cases of self-intersection, with
degenerate Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * Degenerate (album), ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party i ...
vertices when three consecutive points are allowed be on the same
straight line In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are One-dimensional space, one-dimensional objects, though they may exist in Two-dimensional Euclidean space, two, Three-dimensional space, three, ...
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 In geometry, a line is an infinitely long object with no width, depth, or curvature. Thus, lines are One-dimensional space, one-dimensional objects, though they may exist in Two-dimensional Euclidean space, two, Three-dimensional space, three, ...
). (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 In calculus, the second derivative, or the second order derivative, of a function is the derivative of the derivative of . Roughly speaking, the second derivative measures how the rate of change of a quantity is itself changing; for example, ...
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 Concave or concavity may refer to: Science and technology * Concave lens * Concave mirror Mathematics * Concave function, the negative of a convex function * Concave polygon, a polygon which is not convex * Concave set * The concavity In ca ...
,
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytope ...
, or collinear (flat), we construct the matrix :\mathbf = \begin 1 & x_ & y_ \\ 1 & x_ & y_ \\ 1 & x_ & y_\end. 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:


See also

*
Differential geometry of curves Differential geometry of curves is the branch of geometry that deals with smooth curves in the plane and the Euclidean space by methods of differential and integral calculus. Many specific curves have been thoroughly investigated using the ...
*
Orientability In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "counterclockwise". A space is ...
*
Convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
* Signed arc length


References


External links

* http://www.math.hmc.edu/faculty/gu/curves_and_surfaces/curves/_topology.html
Curve orientation
at
MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Dig ...
{{DEFAULTSORT:Curve Orientation Curves Orientation (geometry) Polygons