Shoelace formula

Given: A planar simple polygon with a positively oriented (counterclockwise) 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_{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. Trapezoid formula The trapezoid formula sums up a sequence of oriented areas A_i=\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): \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} Triangle formula The triangle formula sums up the oriented areas A_i of triangles OP_iP_{i+1}: \begin{align} B &= \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} Shoelace formula 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: \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. Other formulas \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=\frac 1 2 \sum_{i=1}^n x_i(y_{i+1} - y_{i-1}) Exterior algebra A particularly concise statement of the formula can be given in terms of the exterior algebra. Let \mathbf{v}_1, \mathbf{v}_2, \dots, \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 (\mathbf{x}, \mathbf{y}) gives \mathbf{v}_i \wedge \mathbf{v}_{i+1} = (x_i y_{i+1} - x_{i+1} y_i) \; \mathbf{x} \wedge \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 \mathbf{x} \wedge \mathbf{y} . == Example ==

For the area of the pentagon with \begin{align} &P_1=(1,6),P_2=(3,1), P_3=(7,2),\\[5pt] &P_4=(4,4), P_5=(8,5) \end{align} one gets \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} \\[5pt] & =(1-18)\;+(6-7)\;+(28-8)\;+(20-32)\;+(48-5)=33 \\[5pt] 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. == Deriving the formulas ==

Trapezoid formula 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=\tfrac 1 2(y_i + y_{i+1})(x_i - x_{i+1}) In case of x_i the number A_i is negative, otherwise positive or A_i=0 if x_i=x_{i+1}. 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 , 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 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_{i=1}^nA_i =\frac 1 2 \sum_{i=1}^n (y_i + y_{i+1})(x_i - x_{i+1}) Triangle form, determinant form Eliminating the brackets and using \sum_{i=1}^n x_iy_i=\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 =\frac 1 2 \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. Other formulas With \sum_{i=1}^n x_iy_{i+1}=\sum_{i=1}^n x_{i-1}y_i\ (see convention P_0 = P_n, P_{n+1} = P_1 above) one gets 2A=\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=\frac 1 2 \sum_{i=1}^n y_i(x_{i-1}-x_{i+1}) With the identity \sum_{i=1}^n x_{i+1}y_i=\sum_{i=1}^n x_iy_{i-1} one gets A=\frac 1 2 \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. == 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_{k-1}, P_{k+1}, \dots, P_n) +A(P_{k-1}, P_k, P_{k+1}) In case of k=1\; \text{or}\; n one should first shift the indices. Hence: • 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 \overline{P_{k-1}P_{k+1}}. • Purging P_k changes the total area by A(P_{k-1},P_k,P_{k+1}), which can be positive or negative. • 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),\ 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{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)=\tfrac 1 2 \begin{vmatrix} 7 & 4 & 8 & 7\\ 2 & 4 & 6 & 2 \end{vmatrix} = -7 • red triangle: A(P_1,Q,P_2)=\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)=\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)=\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 == 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 = \frac{1}{2}\left\| \sum_{i=1}^{n} v_i \wedge v_{i+1} \right\| (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. 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 = \frac{1}{6} \left\| \sum_{F} 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). {{Math proof|Apply the divergence theorem to the vector field \mathbf{v}(x,y,z) = (x,y,z) and the polyhedron P with boundary \partial P consisting of triangular faces F_i: \nabla \cdot \mathbf{v} = \frac{\partial \mathbf{v}}{\partial x} + \frac{\partial \mathbf{v}}{\partial y} + \frac{\partial \mathbf{v}}{\partial z} = 3 So \frac13\int_{P} \nabla \cdot \mathbf{v}\,dV = V(P) For each triangular face F with vertices v_1,v_2,v_3, denote the outward normal vector by \mathbf{n}, denote the area by A. \mathbf{n} A = (v_3-v_2)\wedge(v_1-v_2) is the normal vector of F with magnitude A. The flux of \mathbf{v} through F is \int_{F}\mathbf{v}\cdot\mathbf{n}\,dA For each point (x,y,z) on F, \mathbf{v}(x,y,z)\cdot\mathbf{n} is the projection of the vector (x,y,z) onto the unit normal vector \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. \int_{F}\mathbf{v}\cdot\mathbf{n}\,dA =A\cdot h= \pm \frac{1}{2}\|v_1\wedge v_2\wedge v_3\| where \|v_1\wedge v_2\wedge v_3\| 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\wedge v_2\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)=\frac13\int_{\partial P}\mathbf{v}\cdot\mathbf{n}\,dA = \frac{1}{6}\left\|\sum_F v_1\wedge v_2\wedge v_3\right\| }} ==See also==