Shoelace formula

Short description: Mathematical algorithm for calculating area of a simple polygon

Shoelace scheme for determining the area of a polygon with point coordinates (x1,y1),...,(xn,yn)

The shoelace formula, also known as Gauss's area formula and the surveyor's formula,[1] is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane.[2] It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like threading shoelaces.[2] It has applications in surveying and forestry,[3] among other areas.

The formula was described by Albrecht Ludwig Friedrich Meister (1724–1788) in 1769[4] and is based on the trapezoid formula which was described by Carl Friedrich Gauss and C.G.J. Jacobi.[5] 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.[6] 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.[7]

## Contents

* 1 The polygon area formulas
* 1.1 Trapezoid formula
* 1.2 Triangle formula
* 1.3 Shoelace formula
* 1.4 Other formulas
* 1.5 Exterior algebra
* 2 Example
* 3 Deriving the formulas
* 3.1 Trapezoid formula
* 3.2 Triangle form, determinant form
* 3.3 Other formulas
* 4 Manipulations of a polygon
* 5 Generalization
* 6 See also
* 7 External links
* 8 References

## The polygon area formulas

Basic idea: Any polygon edge determines the signed area of a trapezoid. All these areas sum up to the polygon area.

Given: A planar simple polygon with a positively oriented (counterclockwise) sequence of points Pi=(xi,yi),i=1,…,n in a Cartesian coordinate system.
For the simplicity of the formulas below it is convenient to set P0=Pn,Pn+1=P1.

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.[8]

### Trapezoid formula

The trapezoid formula sums up a sequence of oriented areas Ai=12(yi+yi+1)(xi−xi+1) of trapezoids with PiPi+1 as one of its four edges (see below): A=12∑i=1n(yi+yi+1)(xi−xi+1)=12((y1+y2)(x1−x2)+⋯+(yn+y1)(xn−x1))

### Triangle formula

The triangle formula sums up the oriented areas Ai of triangles OPiPi+1:[9] A=12∑i=1n(xiyi+1−xi+1yi)=12∑i=1n|xixi+1yiyi+1|=12∑i=1n|xiyixi+1yi+1|=12(x1y2−x2y1+x2y3−x3y2+⋯+xny1−x1yn)

### Shoelace formula

Shoelace scheme, vertical form: With all the slashes drawn, the matrix loosely resembles a shoe with the laces done up, giving rise to the algorithm's name.

The triangle formula is 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: 2A=|x1x2y1y2|+|x2x3y2y3|+⋯+|xnx1yny1|=|x1x2x3⋯xnx1y1y2y3⋯yny1|

Sometimes this determinant is transposed (written vertically, in two columns), as shown in the diagram.

### Other formulas

A=12∑i=1nyi(xi−1−xi+1)=12(y1(xn−x2)+y2(x1−x3)+⋯+yn(xn−1−x1)) A=12∑i=1nxi(yi+1−yi−1)

### Exterior algebra

A particularly concise statement of the formula can be given in terms of the exterior algebra. Let 𝐯1,𝐯2,…,𝐯n be the consecutive vertices of the polygon. The Cartesian coordinate expansion of the outer product with respect to the standard ordered orthonormal plane basis (𝐱,𝐲) gives 𝐯i∧𝐯i+1=(xiyi+1−xi+1yi)𝐱∧𝐲 and the oriented area is given as follows. A=12∑i=1nvi∧vi+1=12∑i=1n(xiyi+1−xi+1yi)𝐱∧𝐲 Note that the area is given as a multiple of the unit area 𝐱∧𝐲.

Example Horizontal shoelace form for the example.

## Example

For the area of the pentagon with P1=(1,6),P2=(3,1),P3=(7,2),P4=(4,4),P5=(8,5) one gets 2A=|1361|+|3712|+|7424|+|4845|+|8156|=(1−18)+(6−7)+(28−8)+(20−32)+(48−5)=33A=16.5

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

Deriving the trapezoid formula

The edge Pi,Pi+1 determines the trapezoid (xi,yi),(xi+1,yi+1),(xi,0),(xi+1,0) with its oriented area

Ai=12(yi+yi+1)(xi−xi+1)

In case of xi<xi+1 the number Ai is negative, otherwise positive or Ai=0 if xi=xi+1. In the diagram the orientation of an edge is shown by an arrow. The color shows the sign of Ai: red means Ai<0, green indicates Ai>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 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=∑i=1nAi=12∑i=1n(yi+yi+1)(xi−xi+1)

### Triangle form, determinant form

Triangle form: The color of the edges indicate, which triangle area is positive (green) and negative (red) respectively.

Eliminating the brackets and using ∑i=1nxiyi=∑i=1nxi+1yi+1 (see convention Pn+1=P1 above), one gets the determinant form of the area formula: A=12∑i=1n(xiyi+1−xi+1yi)=12∑i=1n|xixi+1yiyi+1| Because one half of the i-th determinant is the oriented area of the triangle O,Pi,Pi+1 this version of the area formula is called triangle form.

### Other formulas

With ∑i=1nxiyi+1=∑i=1nxi−1yi (see convention P0=Pn,Pn+1=P1 above) one gets 2A=∑i=1n(xiyi+1−xi+1yi)=∑i=1nxiyi+1−∑i=1nxi+1yi=∑i=1nxi−1yi−∑i=1nxi+1yi Combining both sums and excluding yi leads to A=12∑i=1nyi(xi−1−xi+1) With the identity ∑i=1nxi+1yi=∑i=1nxiyi−1 one gets A=12∑i=1nxi(yi+1−yi−1)

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(P1,…,Pn) indicates the oriented area of the simple polygon P1,…,Pn with n≥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<k<n: A(P1,…,Pn)=A(P1,…,Pk−1,Pk+1,…,Pn)+A(Pk−1,Pk,Pk+1) In case of k=1orn one should first shift the indices.

Hence:

1. Moving Pk affects only A(Pk−1,Pk,Pk+1) and leaves A(P1,...,Pk−1,Pk+1,...,Pn) unchanged. There is no change of the area if Pk is moved parallel to Pk−1Pk+1‾.
2. Purging Pk changes the total area by A(Pk−1,Pk,Pk+1), which can be positive or negative.
3. Inserting point Q between Pk,Pk+1 changes the total area by A(Pk,Q,Pk+1), which can be positive or negative.

Example:

P1=(3,1),P2=(7,2),P3=(4,4),
P4=(8,6),P5=(1,7), Q=(4,3)
Manipulations of a polygon

With the above notation of the shoelace scheme one gets for the oriented area of the

* blue polygon: A(P1,P2,P3,P4,P5)=12|374813124671|=20.5
* green triangle: A(P2,P3,P4)=12|74872462|=−7
* red triangle: A(P1,Q,P2)=12|34731321|=−3.5
* blue polygon minus point P3: A(P1,P2,P4,P5)=12|3781312671|=27.5
* blue polygon plus point Q between P1,P2: A(P1,Q,P2,P3,P4,P5)=12|34748131324671|=17

One checks, that the following equations hold: A(P1,P2,P3,P4,P5)=A(P1,P2,P4,P5)+A(P2,P3,P4)=20.5 A(P1,P2,P3,P4,P5)+A(P1,Q,P2)=A(P1,Q,P2,P3,P4,P5)=17

## Generalization

In higher dimensions the area of a polygon can be calculated from its vertices using the exterior algebra form of the Shoelace formula (e.g. in 3d, the sum of successive cross products):A=12‖∑i=1nvi∧vi+1‖(when the vertices are not coplanar this computes the vector area 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 from the coordinates of its vertices, or more accurately, from its hypersurface mesh.[10] For example, the volume of a 3-dimensional polyhedron can be found by triangulating its surface mesh and summing the signed volumes of the tetrahedra formed by each surface triangle and the origin:V=16‖∑Fva∧vb∧vc‖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).

Proof

Apply the divergence theorem to the vector field 𝐯(x,y,z)=(x,y,z) and the polyhedron P with boundary ∂P consisting of triangular faces Fi:

∇⋅𝐯=∂𝐯∂x+∂𝐯∂y+∂𝐯∂z=3 So 13∫P∇⋅𝐯dV=V(P)

For each triangular face F with vertices v1,v2,v3, denote the outward normal vector by 𝐧, denote the area by A.

𝐧A=(v3−v2)∧(v1−v2) is the normal vector of F with magnitude A.

The flux of 𝐯 through F is ∫F𝐯⋅𝐧dA

For each point (x,y,z) on F, 𝐯(x,y,z)⋅𝐧 is the projection of the vector (x,y,z) onto the unit normal vector 𝐧, which is the height h of the tetrahedron formed by v1,v2,v3 and (0,0,0). So the integrand is constant h on F.

∫F𝐯⋅𝐧dA=A⋅h=±12‖v1∧v2∧v3‖

where ‖v1∧v2∧v3‖ is 6×the volume of the tetrahedron formed by v1,v2,v3 and (0,0,0). The sign of the pseudoscalar value v1∧v2∧v3 represents the orientation of our area, and needs to be taken into account to calculate the total flux.

The total flux is the sum of the fluxes through all faces:

V(P)=13∫∂P𝐯⋅𝐧dA=16‖∑Fv1∧v2∧v3‖

## See also

* Green's theorem
* Planimeter
* Polygon area
* Pick's theorem
* Heron's formula

## External links

* Mathologer video about Gauss's shoelace formula

## References

1. ↑ Bart Braden (1986). "The Surveyor's Area Formula". The College Mathematics Journal 17 (4): 326–337. doi:10.2307/2686282. https://www.maa.org/sites/default/files/pdf/pubs/Calc_Articles/ma063.pdf.
2. ↑ 2.0 2.1 Dahlke, Karl. "Shoelace Formula". http://www.mathreference.com/la-det,shoe.html. Retrieved 9 June 2008.
3. ↑ Hans Pretzsch, Forest Dynamics, Growth and Yield: From Measurement to Model, Springer, 2009, ISBN 3-540-88306-1, p. 232.
4. ↑ Meister, A. L. F. (1769), "Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus" (in Latin), Nov. Com. Gött. 1: 144, https://books.google.com/books?id=fOE_AAAAcAAJ .
5. ↑ Max Koecher, Aloys Krieg: Ebene Geometrie, Springer-Verlag, 2013, ISBN 3662068095, 9783662068090, p. 116
6. ↑ P.W. Shor; C.J. Van Wyk (1992), "Detecting and decomposing self-overlapping curves", Comput. Geom. Theory Appl. 2 (1): 31–50, doi:10.1016/0925-7721(92)90019-O
7. ↑ Ralph P. Boland; Jorge Urrutia (2000). "Polygon Area Problems". 12th Canadian Conference on Computational Geometry.. pp. 159–162.
8. ↑ Antti Laaksonen: Guide to Competitive Programming: Learning and Improving Algorithms Through Contests, Springer, 2018, ISBN 3319725475, 9783319725475, p. 217
9. ↑ Mauren Abreu de Souza, Humberto Remigio Gamba, Helio Pedrini: Multi-Modality Imaging: Applications and Computational Techniques, Springer, 2018, ISBN 331998974X, 9783319989747, p. 229
10. ↑ Allgower, Eugene L.; Schmidt, Phillip H. (1986). "Computing Volumes of Polyhedra". Mathematics of Computation 46 (173): 171–174. doi:10.2307/2008221. ISSN 0025-5718. https://www.ams.org/journals/mcom/1986-46-173/S0025-5718-1986-0815838-7/S0025-5718-1986-0815838-7.pdf.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Shoelace formula. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Shoelace_formula&oldid=3989322"