Shoelace formula
The Shoelace formula, also known as Gauss's area formula or the surveyor's formula, is a mathematical algorithm for computing the area of a simple polygon given the Cartesian coordinates of its vertices.[1] It provides an efficient method to determine the area A of a polygon with vertices (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) listed in counterclockwise order, using the expressionA = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|,
where (x_{n+1}, y_{n+1}) = (x_1, y_1).[1] This formula yields a signed area that indicates the polygon's orientation—positive for counterclockwise and negative for clockwise—allowing for straightforward absolute value to obtain the unsigned area.[2] The formula derives from principles in vector geometry and exterior algebra, where each term x_i y_{i+1} - x_{i+1} y_i represents twice the signed area of the triangle formed by the origin and consecutive vertices, summing to the total area via the shoelace pattern of cross-multiplications.[2] It is fundamentally connected to Green's theorem in calculus, which integrates line integrals around the polygon boundary to compute enclosed area, providing a rigorous theoretical foundation.[2] The name "shoelace" arises from the visual resemblance of the calculation's tabular layout to the crisscross pattern of tied shoelaces.[1] The concept of signed area underlying the formula was introduced by Albrecht Ludwig Friedrich Meister in his 1770 treatise Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus, though it first appeared in print in the 1810 German translation of Lazare Carnot's Géométrie de position.[3] Despite frequent association with Carl Friedrich Gauss—due to his 1825 letter praising Meister's work and possible influence on the translation—it was not originated by him.[3] The method applies to any simple polygon, including those with lattice points.[2] In practice, the Shoelace formula is valued for its simplicity and computational efficiency, finding use in surveying to measure land areas from coordinate surveys and in geometry for polygon analysis without decomposition into triangles.[1] It also supports extensions in computational geometry.[2]
Overview and History
Definition and Basic Properties
The shoelace formula provides a method to compute the area of a simple polygon given the Cartesian coordinates of its vertices. For a polygon with n vertices labeled (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) in sequential order, the area A is given by A = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|, where the indices are taken modulo n, so x_{n+1} = x_1 and y_{n+1} = y_1.[1][4] This formula assumes the vertices are listed in either clockwise or counterclockwise order around the boundary of the polygon, with counterclockwise ordering yielding a positive signed area before the absolute value is applied.[1][5] It further requires the polygon to be simple, meaning it does not intersect itself, to ensure the computed area corresponds to the enclosed region without overlaps or gaps.[4][6] Among its basic properties, the shoelace formula applies equally to both convex and concave simple polygons, as long as the vertices are provided in boundary order.[1][4] The inclusion of the absolute value ensures the output is an unsigned (positive) area regardless of the vertex ordering direction, while the signed version without it indicates the orientation.[5][1] The coordinates (x_i, y_i) are typically in a standard Euclidean plane, and the formula's result is invariant under translation of the coordinate system.[4]Historical Origin and Attribution
The concept of signed area for polygons was introduced by the Prussian mathematician Albrecht Ludwig Friedrich Meister in 1770, in his paper "Generalia de genesi figurarum planarum et inde pendentibus earum affectionibus," published in the Novi Commentarii Academiae Scientiarum Petropolitanae. Meister's contribution built upon principles of trapezoidal decomposition to compute polygon areas using vertex coordinates, marking a significant advancement in coordinate geometry for irregular shapes.[3][7] The shoelace formula itself first appeared in print in 1810 in the German translation of Lazare Carnot's Géométrie de position, where the translator Heinrich Christian Schumacher added a footnote attributing it to Carl Friedrich Gauss. In the early 19th century, the formula gained widespread recognition through this attribution to Gauss, who acknowledged Meister's foundational idea in his 1825 letter to Wilhelm Olbers. Despite Meister's prior work, the method became closely associated with Gauss due to his influential publications and demonstrations in fields like surveying. This misattribution persists in many mathematical texts, underscoring Gauss's role in popularizing the technique across Europe.[3][1] The formula is also known as the surveyor's formula, reflecting its practical adoption in land measurement and boundary calculations during the 19th century, where coordinate-based area determination proved efficient for irregular plots. Its development evolved from earlier 18th-century geometric approaches, such as basic trapezoid and triangle decompositions used by mathematicians like Leonhard Euler for approximating areas of curvilinear figures, providing a discrete, algebraic extension suited to polygonal computations.[1][3]Polygon Area Calculation Methods
Trapezoid Decomposition Method
The trapezoid method for computing polygon area applies the trapezoidal rule to the line integral around the boundary, treating each edge as contributing an area term based on average height times width projection. This summation form does not require explicit geometric decomposition into non-overlapping trapezoids but yields the exact area for polygons with given vertex coordinates.[1] For each pair of consecutive vertices (x_i, y_i) and (x_{i+1}, y_{i+1}), the contribution is given by the formula \frac{1}{2} (y_i + y_{i+1}) (x_{i+1} - x_i). The total area of the polygon is then the sum of these terms over all edges, expressed as: A = \sum_{i=1}^{n} \frac{1}{2} (y_i + y_{i+1}) (x_{i+1} - x_i), where the vertices are ordered clockwise or counterclockwise around the boundary, and (x_{n+1}, y_{n+1}) = (x_1, y_1) to close the polygon.[8] This summation accounts for signed areas, ensuring positive net area for properly oriented simple polygons. The method requires vertices to be provided in sequential boundary order. For implementations involving actual trapezoid strips (e.g., in scanline rendering), sorting by y-coordinates and tracking edge intersections is necessary to avoid overlaps, but the formula itself operates directly on the ordered list. It is particularly suitable for convex polygons, where edge contributions simplify without self-intersections.[8]Triangle Decomposition Method
The triangle decomposition method computes the area of a simple polygon by partitioning it into non-overlapping triangles and summing their individual areas. This approach leverages the fact that any simple polygon with n vertices can be triangulated into exactly n-2 triangles using non-crossing diagonals.[9] The resulting triangulation covers the entire interior of the polygon without gaps or overlaps, ensuring the total area is accurately represented as the aggregate of the triangle areas.[10] A straightforward process for triangulation involves selecting a reference vertex and connecting it to all non-adjacent vertices to form a fan of triangles. This fan method works reliably for convex polygons, where the reference vertex can "see" all other vertices without obstruction, producing n-2 triangles directly.[11] For each resulting triangle with vertices (x_a, y_a), (x_b, y_b), and (x_c, y_c), the area is calculated using the coordinate-based formula: \frac{1}{2} \left| x_a (y_b - y_c) + x_b (y_c - y_a) + x_c (y_a - y_b) \right| This formula derives from the determinant of the matrix formed by the vertex coordinates, providing a precise measure for each triangle's contribution.[12] The total polygon area is then the absolute sum of these triangle areas, accounting for orientation if necessary. This method is particularly efficient for simple polygons, as it requires only O(n) triangles and linear time in the number of vertices once triangulated, making it suitable for computational implementations.[9] However, it demands that the polygon be simple, meaning it has no self-intersections or holes, to guarantee a valid decomposition without overlapping or extraneous regions.[10] For non-convex simple polygons, more advanced triangulation algorithms may be needed if the fan from a single vertex introduces crossing edges.[11]Shoelace Formula
The shoelace formula is a direct computational method for determining the area of a simple polygon using the Cartesian coordinates of its vertices listed in sequential order.[1] It operates by performing cross-multiplications across consecutive vertex pairs, avoiding the need for geometric decomposition into simpler shapes.[1] This approach is particularly suited for polygons defined by ordered vertex lists in computational contexts.[1] To compute the area, arrange the vertices (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) in either clockwise or counterclockwise order, appending the first vertex at the end to form a closed loop. Calculate two separate sums: one for the products of each x_i with the subsequent y_{i+1}, and another for each y_i with the subsequent x_{i+1}. The absolute area A is given by A = \frac{1}{2} \left| \sum_{i=1}^{n} x_i y_{i+1} - \sum_{i=1}^{n} y_i x_{i+1} \right|, where (x_{n+1}, y_{n+1}) = (x_1, y_1).[1] The formula's name originates from the crisscrossing pattern of these multiplications, evoking the lacing of shoelaces across coordinates.[1] A key benefit of the shoelace formula is its O(n) time complexity, achieved through a linear traversal of the n vertices with simple arithmetic operations.[13] It eliminates requirements for polygon triangulation, trapezoidal breakdown, or coordinate sorting, making it efficient for direct coordinate-based calculations.[1] Without the absolute value, the formula produces a signed area that indicates vertex ordering: positive for counterclockwise traversal and negative for clockwise.[1] This signed interpretation aids in verifying polygon orientation during computation.[1] The shoelace formula builds on summation principles akin to those in trapezoid and triangle decomposition methods.[14]Alternative Formulations
The shoelace formula admits several equivalent algebraic formulations that leverage linear algebra and geometric interpretations, offering compact expressions for the signed area of a simple polygon with vertices (x_1, y_1), \dots, (x_n, y_n) listed in counterclockwise order. One prominent alternative is the determinant form, which expresses the area as half the absolute value of the determinant of a matrix formed by the vertex coordinates. Specifically, A = \frac{1}{2} \left| \det \begin{pmatrix} x_1 & x_2 & \cdots & x_n & x_1 \\ y_1 & y_2 & \cdots & y_n & y_1 \end{pmatrix} \right|, where the notation represents the expansion into a sum of 2×2 determinants for consecutive pairs of vertices, equivalent to the standard summation but in condensed matrix guise.[1] This form underscores the linear dependence among the coordinates contributing to the enclosed area. In vector notation, the formula utilizes the 2D cross product of position vectors \mathbf{r}_i = (x_i, y_i) and \mathbf{r}_{i+1} = (x_{i+1}, y_{i+1}) (with \mathbf{r}_{n+1} = \mathbf{r}_1), yielding A = \frac{1}{2} \left| \sum_{i=1}^n \mathbf{r}_i \times \mathbf{r}_{i+1} \right|, where the scalar cross product is defined as \mathbf{r}_i \times \mathbf{r}_{i+1} = x_i y_{i+1} - x_{i+1} y_i. This representation interprets each term as the signed area contribution from the parallelogram spanned by consecutive position vectors relative to the origin.[15] A related determinant-based variant arises when triangulating the polygon from the origin, expressing the total area as the sum of triangular areas via 3×3 matrices augmented with a column of ones. For each triangle formed by the origin and vertices i and i+1, \text{Area}_i = \frac{1}{2} \det \begin{pmatrix} x_i & y_i & 1 \\ x_{i+1} & y_{i+1} & 1 \\ 0 & 0 & 1 \end{pmatrix} = \frac{1}{2} (x_i y_{i+1} - x_{i+1} y_i), so the polygon signed area is A = \sum_{i=1}^n \text{Area}_i, aligning with the vector cross product interpretation.[15] For closed polygons, a compact matrix representation can be viewed through the lens of the aforementioned 2×(n+1) determinant, which avoids explicit summation and resembles a permanent-like expansion but leverages the antisymmetric properties of the determinant for efficiency in computation.[1] In the framework of exterior algebra over \mathbb{R}^2, the formula adopts a bilinear form using the Grassmann algebra generated by basis vectors e_1, e_2 with wedge product satisfying e_i \wedge e_j = -e_j \wedge e_i for i \neq j and e_i \wedge e_i = 0. Representing vertices as v_i = x_i e_1 + y_i e_2, the signed area is A = \frac{1}{2} \left( \sum_{i=1}^n v_i \wedge v_{i+1} \right), where v_i \wedge v_{i+1} = (x_i y_{i+1} - x_{i+1} y_i) (e_1 \wedge e_2), and the area is half the absolute value of the coefficient of e_1 \wedge e_2. This oriented formulation naturally extends to signed areas and emphasizes the antisymmetric bilinear structure underlying the geometry.[2]Deriving the Shoelace Formula
From Trapezoidal Integration
The area of a polygon can be computed using the trapezoidal rule applied to the boundary, treating the signed area as the negative of the sum of signed trapezoid areas formed by each edge and the x-axis. For a polygon with vertices (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n), traversed in counter-clockwise order and closed so that (x_{n+1}, y_{n+1}) = (x_1, y_1), the signed area A is given by A = -\sum_{i=1}^n \frac{1}{2} (y_i + y_{i+1}) (x_{i+1} - x_i). This represents A = -\oint y \, dx, the line integral along the polygon's boundary via Green's theorem, where the contribution from each edge is the signed area of the trapezoid with parallel sides of lengths y_i and y_{i+1} and width |x_{i+1} - x_i|, with sign according to the direction of traversal.[16] Expanding the sum step by step yields A = -\frac{1}{2} \sum_{i=1}^n \left[ y_i (x_{i+1} - x_i) + y_{i+1} (x_{i+1} - x_i) \right] = -\frac{1}{2} \sum_{i=1}^n y_i x_{i+1} + \frac{1}{2} \sum_{i=1}^n y_i x_i - \frac{1}{2} \sum_{i=1}^n y_{i+1} x_{i+1} + \frac{1}{2} \sum_{i=1}^n y_{i+1} x_i. The terms \frac{1}{2} \sum y_i x_i - \frac{1}{2} \sum y_{i+1} x_{i+1} cancel because the sums are identical over the closed cycle. Reindexing the remaining terms gives A = -\frac{1}{2} \sum_{i=1}^n y_i x_{i+1} + \frac{1}{2} \sum_{i=1}^n y_{i+1} x_i = \frac{1}{2} \sum_{i=1}^n (y_{i+1} x_i - y_i x_{i+1}) = \frac{1}{2} \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i), which is the shoelace formula in its standard signed form, positive for counterclockwise order. The absolute value is taken for the unsigned area of simple polygons.[4] This trapezoidal sum serves as a Riemann sum approximation to the boundary integral \oint y \, dx, with each edge contributing a single trapezoid panel. For polygonal boundaries with linear edges, the approximation is exact because the trapezoidal rule integrates linear functions precisely: along each non-vertical edge, y is a linear function of x, so the average height (y_i + y_{i+1})/2 multiplied by the base x_{i+1} - x_i gives the exact segmental integral; vertical edges contribute zero to \int y \, dx since dx = 0. Thus, the overall sum approximates \oint y \, dx, and with the negative sign, yields the precise signed area A via the shoelace expression.[17][18]Using Determinants and Vectors
The area of a triangle with vertices \mathbf{r}_a = (x_a, y_a), \mathbf{r}_b = (x_b, y_b), and \mathbf{r}_c = (x_c, y_c) can be expressed using the magnitude of the cross product of two vectors formed by these points: \frac{1}{2} \| (\mathbf{r}_b - \mathbf{r}_a) \times (\mathbf{r}_c - \mathbf{r}_a) \|.[15] In two dimensions, the cross product of vectors \mathbf{u} = (u_x, u_y) and \mathbf{v} = (v_x, v_y) is the scalar u_x v_y - u_y v_x, which equals the determinant of the matrix formed by their components: \det \begin{pmatrix} u_x & v_x \\ u_y & v_y \end{pmatrix}.[15] Thus, the triangle area is equivalently \frac{1}{2} \left| \det \begin{pmatrix} x_b - x_a & x_c - x_a \\ y_b - y_a & y_c - y_a \end{pmatrix} \right|.[15] This vector-based approach extends to polygons by leveraging triangle decomposition, where a simple polygon is partitioned into non-overlapping triangles sharing a common vertex or via diagonals.[11] The total area is the sum of the areas of these triangles, each computed as \frac{1}{2} (\mathbf{r}_j - \mathbf{r}_i) \times (\mathbf{r}_k - \mathbf{r}_i) for appropriate vertices \mathbf{r}_i, \mathbf{r}_j, \mathbf{r}_k. When expanding this summation across the triangulated polygon, internal terms—corresponding to shared edges—cancel due to opposite orientations in adjacent triangles, resulting in a telescoping sum that reduces to contributions solely from the boundary edges.[11] For a polygon with vertices \mathbf{r}_1, \mathbf{r}_2, \dots, \mathbf{r}_n ordered counterclockwise, the boundary sum yields the oriented area as \frac{1}{2} \sum_{i=1}^n \mathbf{r}_i \times \mathbf{r}_{i+1}, where \mathbf{r}_{n+1} = \mathbf{r}_1 enforces closure and ensures the telescoping completes without residual internal terms.[11] Substituting the 2D cross product gives \frac{1}{2} \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i), with the absolute value taken for the unsigned area of simple polygons.[15] This formulation directly recovers the shoelace formula through the vector and determinant perspective.[11]Via Green's Theorem
Green's theorem provides a powerful framework for computing the area of a region in the plane by converting a double integral over the region into a line integral over its boundary. Specifically, for a positively oriented, piecewise smooth, simple closed curve C enclosing a region D, the area A of D is given by A = \frac{1}{2} \oint_C (x \, dy - y \, dx). This formula arises from applying Green's theorem to the vector field \mathbf{F} = (-y, x), whose curl is 2, and scaling appropriately to yield the area integral \iint_D 1 \, dA[19]. For a polygonal region, the boundary C consists of straight line segments connecting the vertices (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n), with (x_{n+1}, y_{n+1}) = (x_1, y_1) to close the path. To evaluate the line integral, parameterize each segment from (x_i, y_i) to (x_{i+1}, y_{i+1}) as \mathbf{r}(t) = (x_i + t(x_{i+1} - x_i), y_i + t(y_{i+1} - y_i)) for t \in [0, 1]. The differentials are dx = (x_{i+1} - x_i) \, dt and dy = (y_{i+1} - y_i) \, dt, so the contribution from each segment is \int_{C_i} (x \, dy - y \, dx) = \int_0^1 \left[ (x_i + t(x_{i+1} - x_i))(y_{i+1} - y_i) - (y_i + t(y_{i+1} - y_i))(x_{i+1} - x_i) \right] dt. Evaluating the integral simplifies to x_i y_{i+1} - x_{i+1} y_i, independent of t, because the linear terms cancel out exactly for straight lines[20]. Summing over all segments yields the total line integral as \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i), so the area is A = \frac{1}{2} \sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i). This expression is exact for polygons, as the parameterization captures the straight-line geometry precisely without approximation error[19]. The formula produces a signed area: positive for counterclockwise orientation and negative for clockwise, reflecting the direction of traversal in the line integral setup[20]. This discrete summation directly connects to the shoelace formula as the polygonal instantiation of the continuous line integral from Green's theorem[21].Examples and Applications
Computational Example for Simple Polygon
Consider a convex quadrilateral, which is a simple polygon, with vertices listed in counterclockwise order: (0,0), (3,0), (3,3), and (0,3). This configuration forms a square with side length 3. To apply the shoelace formula, list the coordinates cyclically by appending the first vertex at the end, and compute the sums \sum x_i y_{i+1} and \sum y_i x_{i+1}.[22] The partial products are organized in the following table for clarity:| i | x_i | y_i | x_i y_{i+1} | y_i x_{i+1} |
|---|---|---|---|---|
| 1 | 0 | 0 | $0 \cdot 0 = 0 | $0 \cdot 3 = 0 |
| 2 | 3 | 0 | $3 \cdot 3 = 9 | $0 \cdot 3 = 0 |
| 3 | 3 | 3 | $3 \cdot 3 = 9 | $3 \cdot 0 = 0 |
| 4 | 0 | 3 | $0 \cdot 0 = 0 | $3 \cdot 0 = 0 |
| Sum | 18 | 0 |