vault

Polygon Area

21 min read

Polygon Area

The area of a simple polygon with vertices (x_0, y_0), (x_1, y_1), …, (x_{n-1}, y_{n-1}) (taken in order around the boundary, no self-intersection) is given by the shoelace formula — also known as the surveyor’s formula or Gauss’s area formula: Area = (1/2) · |Σ_{i=0}^{n-1} (x_i · y_{i+1} − x_{i+1} · y_i)| where indices are taken modulo n (so x_n = x_0, y_n = y_0). The signed version (without the absolute value) is positive for counterclockwise vertex orderings and negative for clockwise — making it an indicator of polygon winding orientation as well as area. The formula generalises gracefully: it computes area for convex and concave polygons alike (any simple polygon, regardless of convexity); it computes the centroid (centre of mass) by analogous sums; it generalises to oriented surface integrals of any closed curve via Green’s theorem. It is named “shoelace” because if you write the coordinates in two columns and cross-multiply diagonally — like lacing a shoe — the sum naturally falls out. Used pervasively in: GIS (geographic information systems compute the area of countries, lakes, and parcels this way); CAD (computer-aided design uses signed area to determine the inside-vs-outside of a polygon); computer graphics (winding-number-based fill rules use the signed area of sub-loops); and competitive programming (a one-liner O(n) for any polygon-area question).

1. Intuition — Triangles Fanning from the Origin

A child-friendly analogy: imagine you cut out a polygon from a piece of paper and want to compute its area. The polygon could be a square (easy: side²), a triangle (easy: base × height / 2), or an irregular pentagon (less easy). For the irregular case, the trick is to pick any point — say, the origin (0, 0) — and draw straight lines to each vertex. This decomposes the polygon into n triangles fanning out from the origin. Compute each triangle’s signed area (with a sign that says “did I lay this triangle on top of another or carve a notch out?”), and add them up. The signs cancel where the triangles overlap (covering the same physical area twice), and what’s left is the polygon’s actual area.

The mathematical content of the shoelace formula is exactly this: the signed area of triangle (0, 0), (x_i, y_i), (x_{i+1}, y_{i+1}) is (1/2) · (x_i · y_{i+1} − x_{i+1} · y_i) — which we recognise as (1/2) · cross product (see Vector Cross Product). Summing over all consecutive vertex pairs gives a signed total. For a CCW polygon, the triangles “stick out” in alignment with the boundary, contributing positively. For a CW polygon, all signs flip. For a concave polygon, some triangles’ cross products are negative — they’re triangles whose “third vertex” (the polygon vertex) lies “behind” the line from origin to the previous vertex. The negative cancels the positive of an earlier-computed triangle that double-covered that region.

The “shoelace” name comes from the visual presentation: write the coordinates as

x_0    y_0
x_1    y_1
x_2    y_2
...
x_{n-1} y_{n-1}
x_0    y_0   ← repeat first row at end

Multiply the down-right diagonals (x_i · y_{i+1}) and the down-left diagonals (x_{i+1} · y_i); subtract the latter from the former; halve and absolute-value. The two diagonal patterns crossing each other look like the criss-cross of shoelaces. (Etymology in Braden 1986, who attributes the formula to Meister 1769 with consolidation by Gauss in his collected works.)

The deeper mathematical justification is Green’s theorem: for a simple closed curve C enclosing region R,

Area(R) = (1/2) · ∮_C (x dy − y dx)

For a polygon, C is the polygonal boundary, and the line integral around each edge from (x_i, y_i) to (x_{i+1}, y_{i+1}) evaluates to (1/2) · (x_i · y_{i+1} − x_{i+1} · y_i). Summing over edges gives the shoelace formula. So the formula is not a “trick” — it’s the discretisation of a fundamental result in vector calculus.

2. Tiny Worked Example — Convex and Concave

2.1 Convex Pentagon

Vertices in CCW order:

P_0 = (0, 0)
P_1 = (4, 0)
P_2 = (5, 3)
P_3 = (2, 5)
P_4 = (-1, 3)

Compute the shoelace sum:

S = (x_0 y_1 − x_1 y_0) + (x_1 y_2 − x_2 y_1) + (x_2 y_3 − x_3 y_2) + (x_3 y_4 − x_4 y_3) + (x_4 y_0 − x_0 y_4)
  = (0·0 − 4·0) + (4·3 − 5·0) + (5·5 − 2·3) + (2·3 − (−1)·5) + ((−1)·0 − 0·3)
  = 0 + 12 + (25 − 6) + (6 + 5) + 0
  = 0 + 12 + 19 + 11 + 0
  = 42

Area = |42| / 2 = 21.

Sanity check: the bounding box is [−1, 5] × [0, 5] = 6 × 5 = 30. Our pentagon clearly takes up more than half but less than all of this box — 21 / 30 = 0.7, plausible for a pentagon that mostly fills the box.

2.2 Concave Polygon (the “Pac-Man Mouth” Test)

Vertices in CCW order, with a triangular notch cut out:

Q_0 = (0, 0)
Q_1 = (6, 0)
Q_2 = (6, 6)
Q_3 = (3, 3)   ← the indentation; pulls the boundary inward
Q_4 = (0, 6)

Shoelace sum:

S = (0·0 − 6·0) + (6·6 − 6·0) + (6·3 − 3·6) + (3·6 − 0·3) + (0·0 − 0·6)
  = 0 + 36 + (18 − 18) + (18 − 0) + 0
  = 0 + 36 + 0 + 18 + 0
  = 54

Area = |54| / 2 = 27.

Sanity check: a 6 × 6 square has area 36. We cut out a triangle with vertices (6, 6), (3, 3), (0, 6) — that triangle has area (1/2) · base · height = (1/2) · 6 · 3 = 9. So 36 − 9 = 27. Matches.

The shoelace formula handles the concavity automatically because the signed sub-area computation around vertex Q_3 is negative — the cross-product (x_2 y_3 − x_3 y_2) = 18 − 18 = 0 and (x_3 y_4 − x_4 y_3) = 18 contributing positively — when traversed in CCW order with the indent. The concavity manifests as a smaller-than-bounding-box result, no special-casing needed.

2.3 Clockwise Order — Sign Inverts

Same pentagon as §2.1 but listed CW:

P_0 = (0, 0), P_1 = (-1, 3), P_2 = (2, 5), P_3 = (5, 3), P_4 = (4, 0)

Shoelace sum:

S = (0·3 − (−1)·0) + ((−1)·5 − 2·3) + (2·3 − 5·5) + (5·0 − 4·3) + (4·0 − 0·0)
  = 0 + (−5 − 6) + (6 − 25) + (0 − 12) + 0
  = 0 − 11 − 19 − 12 + 0
  = −42

Same magnitude, opposite sign. Area = |−42| / 2 = 21. The sign tells you the orientation: positive ⇒ CCW, negative ⇒ CW.

3. Pseudocode — The Two Common Forms

3.1 The “Straightforward” Form

function polygon_area(P):
    n := length(P)
    if n < 3:
        return 0
    s := 0
    for i := 0 to n − 1:
        x_i, y_i     := P[i]
        x_next, y_next := P[(i + 1) mod n]
        s := s + x_i * y_next − x_next * y_i
    return |s| / 2

3.2 The “Cross-Product” Form (Equivalent, More Geometric)

function polygon_area_cross(P):
    n := length(P)
    if n < 3:
        return 0
    s := 0
    origin := (0, 0)
    for i := 0 to n − 1:
        s := s + cross(origin, P[i], P[(i + 1) mod n])
    return |s| / 2

function cross(o, a, b):
    return (a.x − o.x) * (b.y − o.y) − (a.y − o.y) * (b.x − o.x)

These compute exactly the same numerical sum (the cross-product around the origin simplifies to x_i · y_{i+1} − x_{i+1} · y_i); use whichever form is more readable. The cross-product form makes the connection to Vector Cross Product explicit and is preferred when reasoning about the formula.

3.3 The “Anchored at Vertex 0” Form (Numerically Better)

function polygon_area_anchored(P):
    n := length(P)
    if n < 3:
        return 0
    s := 0
    for i := 1 to n − 2:
        s := s + cross(P[0], P[i], P[i + 1])
    return |s| / 2

This anchors the triangulation at P[0] instead of the origin, giving n − 2 triangles. Numerically more stable for floating-point inputs whose coordinates are far from zero (e.g., GPS coordinates ≈ 10^6 meters from a chosen origin), because the cross-product of (P[i] − P[0]) and (P[i+1] − P[0]) works with smaller intermediate magnitudes. For integer inputs, all three forms are bit-exact equivalent.

3.4 Centroid (Centre of Mass) of a Polygon

function polygon_centroid(P):
    n := length(P)
    A := signed_area(P)        # without abs, includes sign
    cx := 0
    cy := 0
    for i := 0 to n − 1:
        x_i, y_i     := P[i]
        x_next, y_next := P[(i + 1) mod n]
        cross_term := x_i * y_next − x_next * y_i
        cx := cx + (x_i + x_next) * cross_term
        cy := cy + (y_i + y_next) * cross_term
    cx := cx / (6 * A)
    cy := cy / (6 * A)
    return (cx, cy)

The centroid is the weighted average of triangle centroids, weighted by signed triangle area. Derivation in Wikipedia: Centroid of a polygon and O’Rourke 1998.

4. Python Implementation

from typing import Sequence
 
Point = tuple[int, int]
 
 
def signed_polygon_area_doubled(pts: Sequence[Point]) -> int:
    """
    2 * signed area of the simple polygon defined by `pts` (in order).
    Positive for CCW vertex order, negative for CW.
 
    Returns 2A so the result is exactly integer for integer coordinate inputs
    — avoids the / 2 which can introduce a half-integer.
 
    O(n) time, O(1) space.
    """
    n = len(pts)
    if n < 3:
        return 0
    s = 0
    for i in range(n):
        x1, y1 = pts[i]
        x2, y2 = pts[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return s
 
 
def polygon_area(pts: Sequence[Point]) -> float:
    """
    Unsigned area of a simple polygon.
    O(n) time.
    """
    return abs(signed_polygon_area_doubled(pts)) / 2
 
 
def polygon_orientation(pts: Sequence[Point]) -> str:
    """
    'CCW' if the polygon is given in counterclockwise order, 'CW' if clockwise,
    'COLLINEAR' if all points are collinear (zero area).
    """
    s = signed_polygon_area_doubled(pts)
    if s > 0:
        return "CCW"
    if s < 0:
        return "CW"
    return "COLLINEAR"
 
 
def polygon_centroid(pts: Sequence[Point]) -> tuple[float, float]:
    """
    Centroid (centre of mass) of a uniformly-dense simple polygon.
 
    Uses the signed-area-weighted formula. Polygon is assumed simple
    (no self-intersection); result is undefined for self-intersecting input.
    """
    n = len(pts)
    if n < 3:
        raise ValueError("polygon must have at least 3 vertices")
 
    a = 0
    cx = 0.0
    cy = 0.0
    for i in range(n):
        x1, y1 = pts[i]
        x2, y2 = pts[(i + 1) % n]
        cross_term = x1 * y2 - x2 * y1
        a += cross_term
        cx += (x1 + x2) * cross_term
        cy += (y1 + y2) * cross_term
 
    a /= 2.0          # signed area
    if a == 0:
        raise ValueError("degenerate polygon: zero signed area")
    cx /= 6 * a
    cy /= 6 * a
    return cx, cy
 
 
def polygon_area_anchored(pts: Sequence[Point]) -> float:
    """
    Numerically more stable formulation that anchors triangles at pts[0]
    instead of the origin. For integer inputs this is bit-equivalent to
    the standard formula; for float inputs with large absolute coordinates
    this loses fewer digits of precision.
    """
    n = len(pts)
    if n < 3:
        return 0.0
    x0, y0 = pts[0]
    s = 0
    for i in range(1, n - 1):
        x1, y1 = pts[i]
        x2, y2 = pts[i + 1]
        # cross product of (P[i] - P[0]) and (P[i+1] - P[0])
        s += (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0)
    return abs(s) / 2.0

A few implementation notes:

  1. signed_polygon_area_doubled returns 2A, not A. This is deliberate: for integer-coordinate inputs, 2A is exactly integer, while A may be a half-integer (e.g., a triangle with vertices (0,0), (1,0), (0,1) has A = 0.5). Returning 2A lets downstream code stay in integer arithmetic for as long as possible.
  2. Use (i + 1) % n to wrap around the last vertex to the first. Forgetting this drops the last edge’s contribution, giving wrong area.
  3. The centroid formula divides by 6A (not 2A). Two factors of 2 come from the cross-product (= 2 · signed triangle area); one factor of 3 from “centroid of triangle is the average of the three vertex positions” (only the (x_i + x_next) part appears because the third vertex is the origin). It’s not a typo — see Bourke 1988 for the derivation.
  4. polygon_area_anchored is preferred when input coordinates are floats with large magnitudes. For integer inputs this should be irrelevant.

5. Complexity

  • Time: O(n) for any of the formulations. Each vertex contributes O(1) arithmetic operations: two multiplications, one subtraction, one addition.
  • Space: O(1) working memory (just a running sum). The input polygon takes O(n) space, but that’s the input itself.

This is information-theoretically optimal: any algorithm that computes the area must read every vertex, since changing a single vertex changes the area in general. So Ω(n) is a tight lower bound.

5.1 Bit Width for Integer Inputs

For polygon vertices with |x|, |y| ≤ M:

  • Each cross-product term x_i · y_{i+1} − x_{i+1} · y_i is at most 2M² in magnitude.
  • The sum over n terms is at most 2 · n · M².
  • For M = 10^9 and n = 10^5, the sum can reach 2 · 10^{23} — overflows int64 (which tops out at ~9.2 · 10^{18}).

Implication: for large-coordinate, many-vertex inputs, use int128 in C++ or Python’s arbitrary-precision integers. Or scale down coordinates by a factor of, say, 10^3 if precision permits.

5.2 Sensitivity to Vertex Ordering

The formula assumes vertices are given in traversal order along the boundary. If they’re scrambled, the formula computes the signed area of an arbitrary self-intersecting polyline — which is not the same as the polygon’s “set-theoretic area” (the area of the region of points enclosed by the boundary). For self-intersecting input the formula computes the “winding number weighted area” — useful in some contexts (CAD even-odd fill rules), wrong in others. Always validate that input is a simple polygon if the application requires the set-theoretic interpretation.

6. Variants and Sub-Patterns

6.1 Pick’s Theorem — Lattice Polygon Area in Closed Form

For a polygon whose vertices have integer coordinates (a “lattice polygon”), Pick’s theorem (Pick 1899) gives:

A = i + b/2 − 1

where i is the number of integer lattice points strictly inside the polygon and b is the number of integer lattice points on the boundary. Combining with the shoelace formula gives a way to count interior lattice points without enumeration:

i = A − b/2 + 1
b = Σ_{edges} gcd(|x_{i+1} − x_i|, |y_{i+1} − y_i|)

Useful in competitive programming whenever the question “how many lattice points lie inside this polygon” comes up.

6.2 Signed Area for Self-Intersecting Polygons

If the polygon is self-intersecting (e.g., a “figure-8”), the shoelace formula computes a winding-number weighted signed area: each region is multiplied by its winding number. For a figure-8 with one CCW lobe and one CW lobe of equal area, the formula returns 0. For a star polygon (5-pointed star traversed CCW), the formula returns the area of the central pentagon counted twice plus the five points counted once. This is occasionally the desired semantics (CAD), but for the “set-theoretic area of the region enclosed”, you must first decompose the input into simple polygons (Bentley-Ottmann segment intersection, see Line Sweep) and apply the formula to each.

6.3 Spherical Polygon Area (GIS Application)

For polygons on a sphere (e.g., country boundaries on the Earth), the planar shoelace formula is wrong. The right formula uses L’Huilier’s theorem for spherical excess, or for many small triangles, the planar shoelace on a local equal-area projection (e.g., Albers conic). GIS libraries (PostGIS, GEOS, Shapely with pyproj) handle this transparently by reprojecting to an equal-area frame before computing.

6.4 Continuous (Calculus) Area via Green’s Theorem

For an arbitrary closed curve C enclosing region R:

Area(R) = (1/2) · ∮_C (x dy − y dx)
        = ∮_C x dy
        = -∮_C y dx

For a polygon, this discretises to the shoelace formula. For a smooth curve given parametrically (x(t), y(t)), one numerically integrates by trapezoidal rule, which (after simplification) is exactly the shoelace formula on the sampled vertices.

6.5 3D Polygon Area

For a planar polygon embedded in 3D (vertices (x_i, y_i, z_i) all in some plane), the area is the magnitude of the 3D cross-product sum:

Area = (1/2) · | Σ_{i=0}^{n-1} (P_i − P_0) × (P_{i+1} − P_0) |

where × is the full 3D cross product. The result is a vector whose magnitude is twice the area; the direction is the polygon’s normal. Used in 3D graphics (face culling, normal computation, ray-polygon intersection).

For a non-planar polygon (e.g., a quadrilateral whose 4 vertices are not coplanar), “area” is ambiguous — it depends on which surface you choose to fill the polygon. The 3D-cross-product-sum gives a useful default (the “vector area”) that is well-defined for any polygon.

6.6 Monte Carlo Estimation (Pedagogical)

Randomly sample N points uniformly from the bounding box and count how many fall inside the polygon (using a point-in-polygon test):

Area ≈ (count_inside / N) · area_of_bounding_box

Convergence is O(1/√N) (slow). Useful only when the polygon is so complex (e.g., billions of vertices, or a fractal boundary) that a deterministic algorithm is infeasible.

7. Diagram — Triangle Fan and Sign Cancellation

flowchart LR
    O((origin)) -. triangle 0 .-> P0((P0))
    O -. triangle 1 .-> P1((P1))
    O -. triangle 2 .-> P2((P2))
    O -. triangle 3 .-> P3((P3))
    O -. triangle 4 .-> P4((P4))
    P0 --> P1
    P1 --> P2
    P2 --> P3
    P3 --> P4
    P4 --> P0
    
    P0 --> SUM[signed sum of cross products]
    P1 --> SUM
    P2 --> SUM
    P3 --> SUM
    P4 --> SUM
    SUM --> A[Area = |sum| / 2]

    style O stroke:#5af
    style SUM stroke:#5a5

What this diagram shows. The central point (blue, origin) is the apex of a triangle fan; the polygon vertices P_0, P_1, …, P_4 form the “outer edge” of the fan. Each triangle O-P_i-P_{i+1} contributes a signed area (positive if P_i, P_{i+1} traverse the apex counterclockwise, negative if clockwise). Solid arrows around the bottom (P_0 → P_1 → … → P_4 → P_0) show the polygon boundary in vertex order. Dashed lines from the origin to each vertex show how the polygon decomposes into triangles. Each triangle’s signed area is (1/2) · cross(O, P_i, P_{i+1}), computed via Vector Cross Product. The green box (signed sum) accumulates these signed areas; positive contributions and negative contributions cancel where triangles overlap (which happens for concave polygons or polygons that don’t surround the origin). The final box (Area) takes the absolute value and divides by 2. Key insight conveyed by the diagram: the formula doesn’t care whether the origin is inside or outside the polygon — sign cancellation handles both cases uniformly. This is why the same O(n) one-liner works for arbitrary simple polygons.

8. Pitfalls

  1. Forgetting to wrap the last vertex. The last edge of the polygon is P_{n-1} → P_0. If you write for i in range(n - 1), you miss it. Use (i + 1) % n or explicitly add the closing term x_{n-1} · y_0 − x_0 · y_{n-1} after the loop.

  2. Integer overflow. As noted in §5.1, products of int32 coordinates can overflow even int64 for large polygons (n · M²). Use int128 or Python ints for safety. C++ long long overflows silently and produces wildly wrong areas — a particularly nasty bug because the computed value is plausibly small instead of crashing.

  3. Treating self-intersecting polygons as simple. The formula computes a winding-number-weighted signed area for self-intersecting input. For “the area of the set of enclosed points”, you must first decompose the input into simple polygons (see Line Sweep §6.4). This bug is common in CAD-import code that doesn’t validate input.

  4. Wrong sign convention in centroid formula. The centroid uses signed area (with sign), not the absolute value. If you use |A|, you get the wrong centroid for CW-ordered polygons. Use the signed area in the centroid formula and sign-correct only at the end if needed.

  5. Using floats for integer-coordinate inputs. Loses precision for no benefit. The shoelace formula is exact in integer arithmetic; promoting to float only introduces round-off.

  6. Centroid of a polygon vs centroid of its vertices. The centroid of the polygon (as a 2D region) is not the average of its vertex coordinates. The vertex-average is the “vertex centroid”, which equals the polygon centroid only for very symmetric shapes (a regular polygon). Common interview gotcha: “compute the centre of a polygon” — clarify which centre the asker means.

  7. Negative area treated as a bug. A negative result from signed_polygon_area_doubled simply means the input is in CW order. Don’t flag this as an error — just take the absolute value. (Or, if your application cares about orientation, use the sign as the orientation indicator.)

  8. Using the planar formula for spherical (geographic) polygons. A country’s area on Earth’s surface cannot be computed by treating (latitude, longitude) as (y, x) and applying the shoelace formula — the answer is wrong by a factor of cos(latitude) and worse near the poles. Use a proper geographic CRS (coordinate reference system) and reproject to an equal-area projection first.

  9. Vertex order ambiguity when the polygon is given as a set of edges. If the input is a list of edges (segments) rather than an ordered vertex list, you must first reconstruct the ordered traversal. This is a graph problem (Eulerian circuit on the polygon’s boundary), not a geometry problem; don’t apply the shoelace formula until you have the right ordering.

  10. Confusing “polygon area” with “point-in-polygon” or “polygon-polygon intersection area”. All three are different problems. The shoelace formula is for the first. For the second, use the ray-casting or winding-number algorithm. For the third (intersection area of two polygons), use polygon clipping (Sutherland-Hodgman, Weiler-Atherton).

  11. Centroid undefined for zero-area polygons. If all vertices are collinear, the polygon has zero area and the centroid is undefined (the formula divides by 0 · A). Validate before computing.

  12. Floating-point cancellation for nearly-degenerate inputs. If two vertices are very close, x_i · y_{i+1} − x_{i+1} · y_i can be the subtraction of two nearly-equal large floats — catastrophic cancellation. Use polygon_area_anchored (anchor at vertex 0, work with differences) for better numerical conditioning. Or use rational arithmetic / exact predicates.

9. Common Interview Problems

ProblemSourceNotes
Compute area of a polygonDirect applicationOne-liner if input is given correctly
Largest Rectangle in HistogramLeetCode 84Different problem (1D), but uses analogous “shoelace” intuition
Erect the FenceLeetCode 587Convex hull; verify CCW orientation via signed area
Convex PolygonLeetCode 469Verify all consecutive triples have same cross-product sign — equivalent to checking the signed area is monotonic in some sense
Is Triangle Inside / Outside PolygonGeometry interviewUse signed area or ray-casting
Rectangle Area IILeetCode 850Sum of rectangles — but with overlaps; needs Line Sweep, not just shoelace
Largest Triangle AreaLeetCode 812signed_triangle_area_doubled / 2, see Vector Cross Product
Self-CrossingLeetCode 335Test path for self-intersection; uses signed-area-like reasoning
Calculator-style: count “regions” of a polygon arrangementApplicationEuler’s formula V − E + F = 2 plus shoelace per face
Centroid of polygonApplicationUse centroid formula; common in physics simulations and CAD

10. Open Questions

  • For polygons with n = 10^9 vertices (e.g., outline of a complex coastline at high resolution), is there a hierarchical / approximate algorithm that beats O(n)? Asymptotically no (you must read each vertex), but constants matter — a SIMD-vectorised inner loop can be 4–8× faster than the scalar version. CGAL and GEOS use specialised SIMD kernels.
  • What’s the right way to define “area” for polygons given in projective or homogeneous coordinates (e.g., as outputs of a perspective camera projection)? The straightforward extension uses the cross-product formula in homogeneous coords, but the answer depends on the projective frame.
  • Pick’s theorem (§6.1) says area + half-boundary-points − 1 = interior lattice points. Is there a fast algorithm to compute interior lattice points of a polygon given the shape but not the lattice points themselves? (Answer: yes — combine the shoelace formula and the gcd-based boundary count.) But for non-lattice polygons, lattice-point counting is Θ(area) worst case (Lehmer’s conjecture-related, AFAICT).
  • Numerical robustness: for floating-point input vertices, when does the shoelace formula’s result differ noticeably from the true area? Shewchuk 1996 discusses adaptive precision for orientation tests; the area-formula extension is straightforward but rarely implemented in textbooks.

11. See Also

Graph View

Backlinks