Shoelace formula

The shoelace formula or shoelace algorithm (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] The user cross-multiplies corresponding coordinates to find the area encompassing the polygon, and subtracts it from the surrounding polygon to find the area of the polygon within. It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like threading shoelaces.^[2] It is also sometimes called the shoelace method. 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 by Carl Friedrich Gauss in 1795.^{[full citation needed]} It can be verified by dividing the polygon into triangles, and can be considered to be a special case of Green's theorem.

The area formula is derived by taking each edge AB, and calculating the area of triangle ABO with a vertex at the origin O, by taking the cross-product (which gives the area of a parallelogram) and dividing by 2. As one wraps around the polygon, these triangles with positive and negative area will overlap, and the areas between the origin and the polygon will be cancelled out and sum to 0, while only the area inside the reference triangle remains. This is why the formula is called the surveyor's formula, since the "surveyor" is at the origin; if going counterclockwise, positive area is added when going from left to right and negative area is added when going from right to left, from the perspective of the origin.^{[citation needed]}

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.^[5] 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.^[6]

Statement[]

The formula can be represented by the expression

${\displaystyle {\begin{aligned}\mathbf {A} &={1 \over 2}\left|\left(\sum _{i=1}^{n-1}x_{i}y_{i+1}\right)+x_{n}y_{1}-\left(\sum _{i=1}^{n-1}x_{i+1}y_{i}\right)-x_{1}y_{n}\right|\\[4pt]&={1 \over 2}|x_{1}y_{2}+x_{2}y_{3}+\cdots +x_{n-1}y_{n}+x_{n}y_{1}-x_{2}y_{1}-x_{3}y_{2}-\cdots -x_{n}y_{n-1}-x_{1}y_{n}|\end{aligned}}}$

where

• A is the area of the polygon,
• n is the number of sides of the polygon, and
• (x_i, y_i), i = 1, 2, ..., n are the ordered vertices (or "corners") of the polygon.

Alternatively^[3][7][8]

${\displaystyle {\begin{aligned}\mathbf {A} &={1 \over 2}\left|\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})\right|={1 \over 2}\left|\sum _{i=1}^{n}y_{i}(x_{i+1}-x_{i-1})\right|={1 \over 2}\left|\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})\right|\\[5pt]&={1 \over 2}\left|\sum _{i=1}^{n}(x_{i+1}+x_{i})(y_{i+1}-y_{i})\right|={1 \over 2}\left|\sum _{i=1}^{n}\det {\begin{pmatrix}x_{i}&x_{i+1}\\y_{i}&y_{i+1}\end{pmatrix}}\right|\end{aligned}}}$

where x_n+1 = x₁ and x₀ = x_n, as well as y_n+1 = y₁ and y₀ = y_n.

If the points are labeled sequentially in the counterclockwise direction, then the sum of the above determinants is positive and the absolute value signs can be omitted;^[1] if they are labeled in the clockwise direction, the sum of the determinants will be negative. This is because the formula can be viewed as a special case of Green's theorem.

A particularly concise statement of the formula can be given in terms of the exterior algebra. If ${\displaystyle v_{1},\dots ,v_{n}}$ are the consecutive vertices of the polygon (regarded as vectors in the Cartesian plane) then

${\displaystyle A={\frac {1}{2}}\cdot \left|\sum _{i=1}^{n}v_{i}\wedge v_{i+1}\right|.}$

Proofs[]

Proof for a triangle[]

Referring to the figure, let ${\displaystyle \mathbf {A} }$ be the area of the triangle whose vertices are given by the coordinates ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),}$ and ${\displaystyle (x_{3},y_{3}).}$ Draw the minimum area rectangle around the triangle so its sides are parallel to the ${\displaystyle x}$ or ${\displaystyle y}$ axes. At least one vertex of the triangle will be on a corner of the rectangle. In the figure, the areas of the three surrounding triangles are ${\displaystyle \mathbf {C} ,\mathbf {D} ,}$ and ${\displaystyle \mathbf {E} .}$ Obviously ${\displaystyle \mathbf {A} }$ is equal to the area of the rectangle (call it ${\displaystyle \mathbf {R} }$) minus the areas of the other three triangles:

${\displaystyle \mathbf {A} =\mathbf {R} -\mathbf {C} -\mathbf {D} -\mathbf {E} }$

By inspection of the figure it can be seen that the areas are given by

${\displaystyle \mathbf {R} =(x_{3}-x_{2})(y_{1}-y_{3})=(x_{3}y_{1}+x_{2}y_{3})-(x_{3}y_{3}+x_{2}y_{1})}$

${\displaystyle -\mathbf {C} =-{\frac {1}{2}}(x_{3}-x_{2})(y_{2}-y_{3})={\frac {1}{2}}(-x_{3}y_{2}-x_{2}y_{3})+{\frac {1}{2}}(x_{3}y_{3}+x_{2}y_{2})}$

${\displaystyle -\mathbf {D} =-{\frac {1}{2}}(x_{3}-x_{1})(y_{1}-y_{3})={\frac {1}{2}}(-x_{3}y_{1}-x_{1}y_{3})+{\frac {1}{2}}(x_{3}y_{3}+x_{1}y_{1})}$

${\displaystyle -\mathbf {E} =-{\frac {1}{2}}(x_{1}-x_{2})(y_{1}-y_{2})={\frac {1}{2}}(-x_{1}y_{1}-x_{2}y_{2})+{\frac {1}{2}}(x_{1}y_{2}+x_{2}y_{1})}$

Collecting terms and rearranging yields

${\displaystyle \mathbf {A} ={\frac {1}{2}}((x_{2}y_{3}-x_{3}y_{2})-(x_{1}y_{3}-x_{3}y_{1})+(x_{1}y_{2}-x_{2}y_{1}))}$

which can be written as a determinant

${\displaystyle \mathbf {A} ={\frac {1}{2}}{\begin{vmatrix}1&1&1\\x_{1}&x_{2}&x_{3}\\y_{1}&y_{2}&y_{3}\end{vmatrix}}}$

If the coordinates are written in a clockwise order, the value of the determinant will be ${\displaystyle -\mathbf {A} .}$

Rearranging another way

${\displaystyle \mathbf {A} ={\frac {1}{2}}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|}$

which is the form of the shoelace formula. This formula can be extended to find the area of any polygon since a simple polygon can be divided into triangles.

Proof for a quadrilateral and general polygon[]

Finding the area of a quadrilateral demonstrates how the shoelace formula is generalized to any polygon by dividing the polygon into triangles. Consider the figure of a quadrilateral whose coordinates are labeled in counterclockwise order. The quadrilateral is divided into two triangles with areas ${\displaystyle \mathbf {A} }$ and ${\displaystyle \mathbf {B} .}$ Using the triangle formula on each triangle we get

${\displaystyle \mathbf {A} ={\frac {1}{2}}(x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3})}$

${\displaystyle \mathbf {B} ={\frac {1}{2}}(x_{1}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{3}y_{1}-x_{4}y_{3}-x_{1}y_{4})}$

Since both triangles were traced in a counterclockwise direction, both areas are positive and we get the area of the quadrilateral by adding the two areas. The last positive term and the last negative term of ${\displaystyle \mathbf {A} }$ cancel with the first positive term and the first negative term of ${\displaystyle \mathbf {B} }$ giving

${\displaystyle \mathbf {A} _{\text{quad.}}={\frac {1}{2}}(x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{1}y_{4}).}$

Examples[]

The user must know the points of the polygon in a Cartesian plane. For example, take a triangle with coordinates {(2, 1), (4, 5), (7, 8)}. Take the first x-coordinate and multiply it by the second y-value, then take the second x-coordinate and multiply it by the third y-value, and repeat as many times until it is done for all wanted points. This can be represented by the following formula:^[9]

${\displaystyle \mathbf {A} _{\text{tri.}}={1 \over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|}$

for x_i and y_i representing each respective coordinate. This formula is just the expansion of those given above for the case n = 3. Using it, one can find that the area of the triangle equals one half of the absolute value of 10 + 32 + 7 − 4 − 35 − 16, which equals 3. The number of variables depends on the number of sides of the polygon. For example, a pentagon will be defined up to x₅ and y₅:

${\displaystyle \mathbf {A} _{\text{pent.}}={1 \over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{5}+x_{5}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{5}y_{4}-x_{1}y_{5}|}$

and a quadrilateral will be defined up to x₄ and y₄:

${\displaystyle \mathbf {A} _{\text{quad.}}={1 \over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{1}y_{4}|.}$

More complex example[]

Consider the polygon defined by the points (3, 4), (5, 11), (12, 8), (9, 5) and (5, 6), as illustrated in the diagram.

The area of this polygon is:

${\displaystyle {\begin{aligned}\mathbf {A} &={1 \over 2}\,{\big |}3\times 11+5\times 8+12\times 5+9\times 6+5\times 4\\&{}\qquad {}-4\times 5-11\times 12-8\times 9-5\times 5-6\times 3{\big |}\\[10pt]&={60 \over 2}=30.\end{aligned}}}$

Etymology[]

The reason this formula is called the shoelace formula is because of a common method used to evaluate it. This method uses matrices. As an example, choose the triangle with vertices (2, 4), (3, −8), and (1, 2). Then construct the following matrix by “walking around” the triangle and ending with the initial point.^[10]

${\displaystyle {\begin{bmatrix}2&4\\3&-8\\1&2\\2&4\end{bmatrix}}}$

First, draw diagonal down and to the right slashes (as shown below),

  

and multiply the two numbers connected by each slash, then add all the products: (2 × −8) + (3 × 2) + (1 × 4) = −6. Do the same thing with slashes diagonal down and to the left (shown below with downwards slashes):

  

(4 × 3) + (−8 × 1) + (2 × 2) = 8. Then take the difference of these two numbers: |(−6) − (8)| = 14. Halving this gives the area of the triangle: 7. Organizing the numbers like this makes the formula easier to recall and evaluate. With all the slashes drawn, the matrix loosely resembles a shoe with the laces done up, giving rise to the algorithm's name.

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

(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.^[11] 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:

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
• Pick's theorem
• Heron's formula

External links[]

• Mathologer video about Gauss' shoelace formula

References[]