Shoelace formula

File:Trapez-formel-einf.svg

Given: A planar simple polygon with a positively oriented (counter clock wise) sequence of points $P\_i=(x\_i,y\_i),\; i=1,\backslash dots,n$ in a Cartesian coordinate system.

For the simplicity of the formulas below it is convenient to set $P\_0\; =\; P\_n,\; P\_\{n+1\}\; =\; 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.Antti Laaksonen: Guide to Competitive Programming: Learning and Improving Algorithms Through Contests, Springer, 2018, ISBN 3319725475, 9783319725475, p. 217

The trapezoid formula sums up a sequence of oriented areas $A\_i=\backslash tfrac\; 1\; 2(y\_i\; +\; y\_\{i+1\})(x\_i\; -\; x\_\{i+1\})$ of trapezoids with $P\_iP\_\{i+1\}$ as one of its four edges (see below):

$$\backslash begin\{align\}$$

A &= \frac 1 2 \sum_{i=1}^n (y_i + y_{i+1})(x_i - x_{i+1})\\

&=\frac 1 2 \Big((y_1+y_2)(x_1-x_2)+ \cdots +(y_n+y_1)(x_n-x_1)\Big)

\end{align}

The triangle formula sums up the oriented areas $A\_i$ of triangles $OP\_iP\_\{i+1\}$:Mauren Abreu de Souza, Humberto Remigio Gamba, Helio Pedrini: Multi-Modality Imaging: Applications and Computational Techniques, Springer, 2018, ISBN 331998974X, 9783319989747, p. 229

$$\backslash begin\{align\}$$

A &= \frac 1 2 \sum_{i=1}^n (x_iy_{i+1}-x_{i+1}y_i)

=\frac 1 2\sum_{i=1}^{n}\begin{vmatrix} x_i & x_{i+1} \\ y_i & y_{i+1} \end{vmatrix}

=\frac 1 2\sum_{i=1}^{n}\begin{vmatrix} x_i & y_i \\ x_{i+1} & y_{i+1} \end{vmatrix}\\

&=\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{align}

File:Shoelace3.png

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:

$$\backslash begin\{align\}2A$$

&=

\begin{vmatrix} x_1 & x_2 \\

y_1 & y_2 \end{vmatrix} +

\begin{vmatrix} x_2 & x_3 \\

y_2 & y_3 \end{vmatrix} +\cdots +

\begin{vmatrix} x_n & x_1 \\

y_n & y_1 \end{vmatrix} \\[10mu]

&= \begin{vmatrix} x_1 & x_2 &x_3 \cdots &x_n&x_1\\

y_1 & y_2 &y_3 \cdots &y_n&y_1 \end{vmatrix}

\end{align}

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

$$\backslash begin\{align\}$$

A &=\frac 1 2 \sum_{i=1}^n y_i(x_{i-1}-x_{i+1})\\

& =\frac 1 2

\Big(y_1(x_n-x_2)+y_2(x_1-x_3)+

\cdots+y_n(x_{n-1}-x_1)\Big)

\end{align}

$$A=\backslash frac\; 1\; 2\; \backslash sum\_\{i=1\}^n\; x\_i(y\_\{i+1\}\; -\; y\_\{i-1\})$$

A particularly concise statement of the formula can be given in terms of the exterior algebra. Let $\backslash mathbf\{v\}\_1,\; \backslash mathbf\{v\}\_2,\; \backslash dots,\; \backslash mathbf\{v\}\_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 $(\backslash mathbf\{x\},\; \backslash mathbf\{y\})$ gives $\backslash mathbf\{v\}\_i\; \backslash wedge\; \backslash mathbf\{v\}\_\{i+1\}\; =\; (x\_i\; y\_\{i+1\}\; -\; x\_\{i+1\}\; y\_i)\; \backslash ;\; \backslash mathbf\{x\}\; \backslash wedge\; \backslash mathbf\{y\}$ and the oriented area is given as follows.

A = \frac{1}{2} \sum_{i=1}^{n} v_i \wedge v_{i+1}

= \frac{1}{2} \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \; \mathbf{x} \wedge \mathbf{y}

Note that the area is given as a multiple of the unit area $\backslash mathbf\{x\}\; \backslash wedge\; \backslash mathbf\{y\}$.

File:Trapez-formel-beispiel.svg

File:Trapez-shoelace.svg

For the area of the pentagon with

$$\backslash begin\{align\}$$

&P_1=(1,6),P_2=(3,1), P_3=(7,2),\\

&P_4=(4,4), P_5=(8,5)

\end{align}

one gets

$$\backslash begin\{align\}$$

2A &=

\begin{vmatrix} 1 & 3 \\ 6 & 1 \end{vmatrix} +

\begin{vmatrix} 3 & 7 \\ 1 & 2 \end{vmatrix} +

\begin{vmatrix} 7 & 4 \\ 2 & 4 \end{vmatrix} +

\begin{vmatrix} 4 & 8 \\ 4 & 5 \end{vmatrix} +

\begin{vmatrix} 8 & 1 \\ 5 & 6 \end{vmatrix} \\

& =(1-18)\;+(6-7)\;+(28-8)\;+(20-32)\;+(48-5)=33 \\

A&= 16.5

\end{align}

The advantage of the shoelace form: Only 6 columns have to be written for calculating the 5 determinants with 10 columns.

File:Trapez-formel-prinz.svg

The edge $P\_i,\; P\_\{i+1\}$ determines the trapezoid $(x\_i,y\_i),\; (x\_\{i+1\},y\_\{i+1\}),\; (x\_i,0),\; (x\_\{i+1\},0)$ with its oriented area

:$$A\_i=\backslash tfrac\; 1\; 2(y\_i\; +\; y\_\{i+1\})(x\_i\; -\; x\_\{i+1\})$$

In case of 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\; =\; \backslash sum\_\{i=1\}^nA\_i\; =\backslash frac\; 1\; 2\; \backslash sum\_\{i=1\}^n\; (y\_i\; +\; y\_\{i+1\})(x\_i\; -\; x\_\{i+1\})$$

File:Trapezformel-3eckform.svg

Eliminating the brackets and using

$\backslash sum\_\{i=1\}^n\; x\_iy\_i=\backslash sum\_\{i=1\}^n\; x\_\{i+1\}y\_\{i+1\}$ (see convention $P\_\{n+1\}=P\_1$ above), one gets the determinant form of the area formula:

$$A\; =\backslash frac\; 1\; 2\; \backslash sum\_\{i=1\}^n\; (x\_i\; y\_\{i+1\}-x\_\{i+1\}y\_i)$$

=\frac 1 2\sum_{i=1}^{n}\begin{vmatrix} x_i & x_{i+1} \\ y_i & y_{i+1} \end{vmatrix}

Because one half of the i-th determinant is the oriented area of the triangle $O,P\_i,P\_\{i+1\}$ this version of the area formula is called triangle form.

With $\backslash sum\_\{i=1\}^n\; x\_iy\_\{i+1\}=\backslash sum\_\{i=1\}^n\; x\_\{i-1\}y\_i\backslash$ (see convention $P\_0\; =\; P\_n,\; P\_\{n+1\}\; =\; P\_1$ above) one gets

$$2A=\backslash sum\_\{i=1\}^n\; (x\_iy\_\{i+1\}-x\_\{i+1\}y\_i)$$

=\sum_{i=1}^n x_iy_{i+1} - \sum_{i=1}^n x_{i+1}y_i

=\sum_{i=1}^n x_{i-1}y_i - \sum_{i=1}^n x_{i+1}y_i

Combining both sums and excluding $y\_i$ leads to

$$A=\backslash frac\; 1\; 2\; \backslash sum\_\{i=1\}^n\; y\_i(x\_\{i-1\}-x\_\{i+1\})$$

With the identity $\backslash sum\_\{i=1\}^n\; x\_\{i+1\}y\_i=\backslash sum\_\{i=1\}^n\; x\_iy\_\{i-1\}$ one gets

$$A=\backslash frac\; 1\; 2\; \backslash sum\_\{i=1\}^n\; x\_i(y\_\{i+1\}-y\_\{i-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.

$A(P\_1,\; \backslash dots,\; P\_n)$ indicates the oriented area of the simple polygon $P\_1,\; \backslash dots,\; P\_n$ with $n\backslash 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

$$A(P\_1,\; \backslash dots,\; P\_n)\; =\; A(P\_1,\; \backslash dots,\; P\_\{k-1\},\; P\_\{k+1\},\; \backslash dots,\; P\_n)$$

+A(P_{k-1}, P_k, P_{k+1})

In case of $k=1\backslash ;\; \backslash text\{or\}\backslash ;\; n$ one should first shift the indices.

Hence:

1. Moving $P\_k$ affects only $A(P\_\{k-1\},P\_k,P\_\{k+1\})$ and leaves $A(P\_1,...,P\_\{k-1\},P\_\{k+1\},\; ...,P\_n)$ unchanged. There is no change of the area if $P\_k$ is moved parallel to $\backslash overline\{P\_\{k-1\}P\_\{k+1\}\}$.
2. Purging $P\_k$ changes the total area by $A(P\_\{k-1\},P\_k,P\_\{k+1\})$, which can be positive or negative.
3. Inserting point $Q$ between $P\_k,P\_\{k+1\}$ changes the total area by $A(P\_k,Q,P\_\{k+1\})$, 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),\backslash \; Q=(4,3)$

File:Trapez-f-beisp-dyn.svg

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)=\backslash tfrac\; 1\; 2$$

\begin{vmatrix} 3 & 7 & 4 & 8 & 1 & 3\\

1 & 2 & 4 & 6 & 7 & 1 \end{vmatrix}= 20.5

• green triangle: $$A(P\_2,\; P\_3,\; P\_4)=\backslash tfrac\; 1\; 2$$

\begin{vmatrix} 7 & 4 & 8 & 7\\

2 & 4 & 6 & 2 \end{vmatrix} = -7

• red triangle: $$A(P\_1,Q,P\_2)=\backslash tfrac\; 1\; 2$$

\begin{vmatrix} 3 & 4 & 7 & 3\\

1 & 3 & 2 & 1 \end{vmatrix} = -3.5

• blue polygon minus point $P\_3$: $$A(P\_1,\; P\_2,\; P\_4,\; P\_5)=\backslash tfrac\; 1\; 2$$

\begin{vmatrix} 3 & 7 & 8 & 1 & 3\\

1& 2 & 6 & 7 & 1 \end{vmatrix}= 27.5

• blue polygon plus point $Q$ between $P\_1,P\_2$: $$A(P\_1,\; Q,\; P\_2,\; P\_3,\; P\_4,\; P\_5)=\backslash tfrac\; 1\; 2$$

\begin{vmatrix} 3 & 4 & 7 & 4& 8 & 1 &3\\

1 & 3 & 2 & 4& 6 & 7 &1 \end{vmatrix} = 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$$

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\; =\; \backslash frac\{1\}\{2\}\backslash left\backslash |\; \backslash sum\_\{i=1\}^\{n\}\; v\_i\; \backslash wedge\; v\_\{i+1\}\; \backslash right\backslash |$$(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.{{Cite journal|last1=Allgower|first1=Eugene L.|last2=Schmidt|first2=Phillip H.|date=1986|title=Computing Volumes of Polyhedra|url=https://www.ams.org/journals/mcom/1986-46-173/S0025-5718-1986-0815838-7/S0025-5718-1986-0815838-7.pdf|journal=Mathematics of Computation|volume=46|issue=173|pages=171–174|doi=10.2307/2008221|jstor=2008221 |issn=0025-5718|doi-access=free}} 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\; =\; \backslash frac\{1\}\{6\}\; \backslash left\backslash |\; \backslash sum\_\{F\}\; v\_a\; \backslash wedge\; v\_b\; \backslash wedge\; v\_c\; \backslash right\backslash |$$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).

{{Math proof|Apply the divergence theorem to the vector field $\backslash mathbf\{v\}(x,y,z)\; =\; (x,y,z)$ and the polyhedron $P$ with boundary $\backslash partial\; P$ consisting of triangular faces $F\_i$:

$$\backslash nabla\; \backslash cdot\; \backslash mathbf\{v\}\; =\; \backslash frac\{\backslash partial\; \backslash mathbf\{v\}\}\{\backslash partial\; x\}\; +\; \backslash frac\{\backslash partial\; \backslash mathbf\{v\}\}\{\backslash partial\; y\}\; +\; \backslash frac\{\backslash partial\; \backslash mathbf\{v\}\}\{\backslash partial\; z\}\; =\; 3$$

So

$$\backslash frac13\backslash int\_\{P\}\; \backslash nabla\; \backslash cdot\; \backslash mathbf\{v\}\backslash ,dV\; =\; V(P)$$

For each triangular face $F$ with vertices $v\_1,v\_2,v\_3$,

denote the outward normal vector by $\backslash mathbf\{n\}$, denote the area by $A$.

$\backslash mathbf\{n\}\; A\; =\; (v\_3-v\_2)\backslash wedge(v\_1-v\_2)$ is the normal vector of $F$ with magnitude $A$.

The flux of $\backslash mathbf\{v\}$ through $F$ is $\backslash int\_\{F\}\backslash mathbf\{v\}\backslash cdot\backslash mathbf\{n\}\backslash ,dA$

For each point $(x,y,z)$ on $F$,

$\backslash mathbf\{v\}(x,y,z)\backslash cdot\backslash mathbf\{n\}$ is the projection of the vector $(x,y,z)$ onto the unit normal vector $\backslash mathbf\{n\}$, which is the height $h$ of the tetrahedron formed by $v\_1,v\_2,v\_3$ and $(0,0,0)$.

So the integrand is constant $h$ on $F$.

$$\backslash int\_\{F\}\backslash mathbf\{v\}\backslash cdot\backslash mathbf\{n\}\backslash ,dA\; =A\backslash cdot\; h=\; \backslash pm\; \backslash frac\{1\}\{2\}\backslash |v\_1\backslash wedge\; v\_2\backslash wedge\; v\_3\backslash |$$

where $\backslash |v\_1\backslash wedge\; v\_2\backslash wedge\; v\_3\backslash |$ is 6×the volume of the tetrahedron formed by $v\_1,v\_2,v\_3$ and $(0,0,0)$. The sign of the pseudoscalar value $v\_1\backslash wedge\; v\_2\backslash wedge\; v\_3$ 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)=\backslash frac13\backslash int\_\{\backslash partial\; P\}\backslash mathbf\{v\}\backslash cdot\backslash mathbf\{n\}\backslash ,dA\; =\; \backslash frac\{1\}\{6\}\backslash left\backslash |\backslash sum\_F\; v\_1\backslash wedge\; v\_2\backslash wedge\; v\_3\backslash right\backslash |$$

}}

• Planimeter
• Polygon area
• Pick's theorem
• Heron's formula

• [https://www.youtube.com/watch?v=0KjG8Pg6LGk Mathologer video about Gauss's shoelace formula]

{{Reflist}}

Category:Area

Category:Geometric algorithms

Category:Surveying