HOME

TheInfoList



OR:

The shoelace formula, shoelace algorithm, or shoelace method (also known as Gauss's area formula and the surveyor's formula) is a mathematical
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to determine the
area Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while '' surface area'' refers to the area of an ope ...
of 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 ...
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,Hans Pretzsch,
Forest Dynamics, Growth and Yield: From Measurement to Model
', Springer, 2009, , p. 232.
among other areas. The formula was described by Albrecht Ludwig Friedrich Meister (1724–1788) in 1769 and is based on the trapezoid formula which was described by
Carl Friedrich Gauss Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
and C.G.J. Jacobi. The triangle form of the area formula can be considered to be a special case of Green's theorem. The area formula can also be applied to self-overlapping polygons since the meaning of area is still clear even though self-overlapping polygons are not generally
simple Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by Johnn ...
. Furthermore, a self-overlapping polygon can have multiple "interpretations" but the Shoelace formula can be used to show that the polygon's area is the same regardless of the interpretation.


The polygon area formulas

''Given:'' A planar
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 ...
with a ''positively oriented'' (counter clock wise) sequence of points P_i=(x_i,y_i), i=1,\dots,n in a Cartesian coordinate system.
For the simplicity of the formulas below it is convenient to set P_0 = P_n, P_ = P_1. ''The formulas:''
The area of the given polygon can be expressed by a variety of formulas, which are connected by simple operations (see below):
If the polygon is ''negatively oriented'', then the result A of the formulas is negative. In any case , A, is the sought area of the polygon.


Trapezoid formula

The trapezoid formula sums up a sequence of oriented areas A_i=\tfrac 1 2(y_i + y_)(x_i - x_) of
trapezoid A quadrilateral with at least one pair of parallel sides is called a trapezoid () in American and Canadian English. In British and other forms of English, it is called a trapezium (). A trapezoid is necessarily a convex quadrilateral in Eu ...
s with P_iP_ as one of its four edges (see below): \begin A &= \frac 1 2 \sum_^n (y_i + y_)(x_i - x_)\\ &=\frac 1 2 \Big((y_1+y_2)(x_1-x_2)+ \cdots +(y_n+y_1)(x_n-x_1)\Big) \end


Triangle formula

The triangle formula sums up the oriented areas A_i of triangles OP_iP_: \begin A &= \frac 1 2 \sum_^n (x_iy_-x_y_i) =\frac 1 2\sum_^\begin x_i & x_ \\ y_i & y_ \end =\frac 1 2\sum_^\begin x_i & y_i \\ x_ & y_ \end\\ &=\frac 1 2 \Big(x_1 y_2- x_2 y_1 +x_2 y_3- x_3 y_2+\cdots +x_ny_1-x_1y_n\Big) \end


Shoelace formula

The determinant formulas are the base of the popular ''shoelace formula'', which is a scheme, that optimizes the calculation of the sum of the 2×2-Determinants by hand: \begin2A&=\underbrace\\ &= \begin x_1 & x_2 &x_3 \cdots &x_n&x_1\\ y_1 & y_2 &y_3 \cdots &y_n&y_1 \end& \text \\ &= \begin x_1 & y_1\\ x_2 & y_2\\ \vdots & \vdots \\ x_n& y_n\\ x_1&y_1 \end & \text \end


Other formulas

\begin A &=\frac 1 2 \sum_^n y_i(x_-x_)\\ & =\frac 1 2 \Big(y_1(x_n-x_2)+y_2(x_1-x_3)+ \cdots+y_n(x_-x_1)\Big) \end A=\frac 1 2 \sum_^n x_i(y_ - y_) A particularly concise statement of the formula can be given in terms of the
exterior algebra In mathematics, the exterior algebra, or Grassmann algebra, named after Hermann Grassmann, is an algebra that uses the exterior product or wedge product as its multiplication. In mathematics, the exterior product or wedge product of vectors is a ...
. If v_1, \dots, v_n are the consecutive vertices of the polygon (regarded as vectors in the Cartesian plane) then A = \frac \cdot \left, \sum_^ v_i \wedge v_ \.


Example

For the area of the pentagon with \begin &P_1=(1,6),P_2=(3,1), P_3=(7,2),\\ &P_4=(4,4), P_5=(8,5) \end one gets \begin 2A &= \begin 1 & 3 \\ 6 & 1 \end + \begin 3 & 7 \\ 1 & 2 \end + \begin 7 & 4 \\ 2 & 4 \end + \begin 4 & 8 \\ 4 & 5 \end + \begin 8 & 1 \\ 5 & 6 \end \\ & =1-18\;+6-7\;+28-8\;+20-32\;+48-5=33 \\ A&= 16.5 \end The advantage of the shoelace form: Only 6 columns have to be written for calculating the 5 determinants with 10 columns.


Deriving the formulas


Trapezoid formula

The edge P_i, P_ determines the trapezoid (x_i,y_i), (x_,y_), (x_i,0), (x_,0) with its oriented area :A_i=\tfrac 1 2(y_i + y_)(x_i - x_) In case of x_i the number A_i is negative, otherwise positive or A_i=0 if x_i=x_. In the diagram the orientation of an edge is shown by an arrow. The color shows the sign of A_i: red means A_i < 0, green indicates A_i > 0. In the first case the trapezoid is called ''negative'' in the second case ''positive''. The negative trapezoids delete those parts of positive trapezoids, which are outside the polygon. In case of a
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 polytop ...
polygon (in the diagram the upper example) this is obvious: The polygon area is the sum of the areas of the positive trapezoids (green edges) minus the areas of the negative trapezoids (red edges). In the non convex case one has to consider the situation more carefully (see diagram). In any case the result is A = \sum_^nA_i =\frac 1 2 \sum_^n (y_i + y_)(x_i - x_)


Triangle form, determinant form

Eliminating the brackets and using \sum_^n x_iy_i=\sum_^n x_y_ (see convention P_=P_1 above), one gets the ''determinant form'' of the area formula: A =\frac 1 2 \sum_^n (x_i y_-x_y_i) =\frac 1 2\sum_^\begin x_i & x_ \\ y_i & y_ \end Because one half of the i-th determinant is the oriented area of the triangle O,P_i,P_ this version of the area formula is called ''triangle form''.


Other formulas

With \sum_^n x_iy_=\sum_^n x_y_i\ (see convention P_0 = P_n, P_ = P_1 above) one gets 2A=\sum_^n (x_iy_-x_y_i) =\sum_^n x_iy_ - \sum_^n x_y_i =\sum_^n x_y_i - \sum_^n x_y_i Combining both sums and excluding y_i leads to A=\frac 1 2 \sum_^n y_i(x_-x_) With the identity \sum_^n x_y_i=\sum_^n x_iy_ one gets A=\frac 1 2 \sum_^n x_i(y_-y_) Alternatively, this is a special case of Green's theorem with one function set to 0 and the other set to x, such that the area is the integral of xdy along the boundary.


Manipulations of a polygon

A(P_1, \dots, P_n) indicates the oriented area of the simple polygon P_1, \dots, P_n with n\ge 4 (see above). A is positive/negative if the orientation of the polygon is positive/negative. From the triangle form of the area formula or the diagram below one observes for 1: A(P_1, \dots, P_n) = A(P_1, \dots, P_, P_, \dots, P_n) +A(P_, P_k, P_) In case of k=1\; \text\; n one should first shift the indices. Hence: #Moving P_k affects only A(P_,P_k,P_) and leaves A(P_1,...,P_,P_, ...,P_n) unchanged. There is no change of the area if P_k is moved parallel to \overline. #Purging P_k changes the total area by A(P_,P_k,P_), which can be positive or negative. #Inserting point Q between P_k,P_ changes the total area by A(P_k,Q,P_), which can be positive or negative. Example: :P_1=(3,1),P_2=(7,2),P_3=(4,4), : P_4=(8,6),P_5=(1,7),\ Q=(4,3) With the above notation of the shoelace scheme one gets for the oriented area of the *''blue'' polygon: A(P_1,P_2,P_3,P_4,P_5)=\tfrac 1 2 \begin 3 & 7 & 4 & 8 & 1 & 3\\ 1 & 2 & 4 & 6 & 7 & 1 \end= 15.5 *''green'' triangle: A(P_2, P_3, P_4)=\tfrac 1 2 \begin 7 & 4 & 8 & 7\\ 2 & 4 & 6 & 2 \end = -7 *''red'' triangle: A(P_1,Q,P_2)=\tfrac 1 2 \begin 3 & 4 & 7 & 3\\ 1 & 3 & 2 & 1 \end = -3.5 *blue polygon ''minus'' point P_3: A(P_1, P_2, P_4, P_5)=\tfrac 1 2 \begin 3 & 7 & 8 & 1 & 3\\ 1& 2 & 6 & 7 & 1 \end= 27.5 *blue polygon ''plus'' point Q between P_1,P_2: A(P_1, Q, P_2, P_3, P_4, P_5)=\tfrac 1 2 \begin 3 & 4 & 7 & 4& 8 & 1 &3\\ 1 & 3 & 2 & 4& 6 & 7 &1 \end = 17 One checks, that the following equations hold: A(P_1, P_2, P_3, P_4, P_5) = A(P_1, P_2, P_4, P_5) + A(P_2, P_3, P_4) = 20.5 A(P_1, P_2, P_3, P_4, P_5) + A(P_1, Q, P_2) = A(P_1, Q, P_2, P_3, P_4, P_5) = 17


Generalization

In higher dimensions the area of a polygon can be calculated from its vertices using the
exterior algebra In mathematics, the exterior algebra, or Grassmann algebra, named after Hermann Grassmann, is an algebra that uses the exterior product or wedge product as its multiplication. In mathematics, the exterior product or wedge product of vectors is a ...
form of the Shoelace formula (e.g. in 3d, the sum of successive cross products): A = \frac\left\, \sum_^ v_i \wedge v_ \right\, (when the vertices are not
coplanar In geometry, a set of points in space are coplanar if there exists a geometric plane that contains them all. For example, three points are always coplanar, and if the points are distinct and non-collinear, the plane they determine is unique. How ...
this computes the
vector area In 3-dimensional geometry and vector calculus, an area vector is a vector combining an area quantity with a direction, thus representing an ''oriented area'' in three dimensions. Every bounded surface in three dimensions can be associated with ...
enclosed by the loop, i.e. the projected area or "shadow" in the plane in which it is greatest). This formulation can also be generalized to calculate the volume of an n-dimensional
polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
from the coordinates of its vertices, or more accurately, from its
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 Euclidea ...
mesh. For example, the volume of a 3-dimensional
polyhedron In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on ...
can be found by triangulating its surface mesh and summing the signed volumes of the
tetrahedra In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), 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 o ...
formed by each surface triangle and the origin: V = \frac \left\, \sum_ v_a \wedge v_b \wedge v_c \right\, where the sum is over the faces and care has to be taken to order the vertices consistently (all clockwise or anticlockwise viewed from outside the polyhedron). Alternatively, an expression in terms of the face areas and surface normals may be derived using the divergence theorem (see Polyhedron § Volume).


See also

*
Planimeter A planimeter, also known as a platometer, is a measuring instrument used to determine the area of an arbitrary two-dimensional shape. Construction There are several kinds of planimeters, but all operate in a similar way. The precise way in whic ...
*
Polygon area 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 tog ...
*
Pick's theorem In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in 1 ...
*
Heron's formula In geometry, Heron's formula (or Hero's formula) gives the area of a triangle in terms of the three side lengths , , . If s = \tfrac12(a + b + c) is the semiperimeter of the triangle, the area is, :A = \sqrt. It is named after first-century ...


External links


Mathologer video about Gauss' shoelace formula


References

{{Reflist Area Geometric algorithms Surveying