Skip to content
AfluidityAlgorithm Atlas
GeometryAll categories
FoundationConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Shoelace Formula

Computes the exact signed and unsigned area enclosed by a simple 2D polygon from its ordered vertex coordinates in O(n) linear time.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Geometry
Difficulty
Beginner
Family
Polygon & Planar Measurement
Tier
Foundation
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
1
Relationships
1
Code example
Not ready
Visualization
Ready
Aliases
Gauss's Area Formula, Surveyor's Formula, Polygon Area Cross-Product Formula

Overview

The Shoelace Formula (Gauss's area formula) sums the 2D cross products (x_i * y_{i+1} - x_{i+1} * y_i) around the closed boundary of a simple polygon and divides by two, giving both the exact enclosed area and the vertex winding orientation (counter-clockwise vs clockwise).

Core Concepts

2D cross productsigned trapezoid/triangle summationGreen's theoremwinding orientation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Shoelace Formula across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(n)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(n)

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(1)

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

  • Use the Shoelace Formula when you need the exact area of a simple (non-self-intersecting) 2D polygon given its ordered boundary vertices.
  • Use its signed output before divide-by-two to test whether a polygon ring is wound counter-clockwise or clockwise.

When Not to Use

  • Avoid direct application on self-intersecting (figure-eight) polygons if you need total covered area rather than net signed winding area; decompose into simple polygons first.

What It Does

  • Calculates the exact area enclosed by any non-self-intersecting 2D polygon from vertex coordinates
  • Determines polygon winding order (CCW positive signed area vs CW negative signed area)

Use Cases

  • Computing land parcel, room, or contour area from GIS and CAD polygon vertices
  • Checking clockwise vs counter-clockwise winding order of mesh faces and 2D contours
  • Computing polygon centroids and moments of inertia in 2D physics engines

Inputs

  • Ordered list of n 2D polygon vertices (x_0, y_0), ..., (x_{n-1}, y_{n-1})

Outputs

  • Exact polygon area A >= 0 and signed area A_signed

Key Formulas (1)

Shoelace Area Formula

A = (1/2) |sum_{i=0}^{n−1} (xi y_{i+1} − x_{i+1} yi)|
A = (1/2) |sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i)|

Half the magnitude of the sum of 2D cross products of adjacent boundary vertices.

Pseudocode

  1. 1.Initialize twiceSignedArea = 0
  2. 2.For i from 0 to n - 1:
  3. 3. Let j = (i + 1) mod n
  4. 4. twiceSignedArea += x[i] * y[j] - x[j] * y[i]
  5. 5.Return abs(twiceSignedArea) / 2

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize twiceSignedArea = 0
  2. For i from 0 to n - 1:
  3. Let j = (i + 1) mod n
  4. twiceSignedArea += x[i] * y[j] - x[j] * y[i]
  5. Return abs(twiceSignedArea) / 2

Canonical Example

Input
Vertices = [(0, 0), (4, 0), (4, 3), (0, 3)]
Output
Area = 12 (signed area = +12, counter-clockwise)
Explanation
Summing x_i*y_{i+1} - x_{i+1}*y_i over the 4 rectangle edges yields 0 + 12 + 12 + 0 = 24; dividing by 2 gives area 12.

Implementation Notes

  • Shift coordinates by (x_0, y_0) to preserve floating-point precision on large world coordinates.

Common Pitfalls

  • Forgetting to close the loop by pairing the last vertex (x_{n-1}, y_{n-1}) with the first vertex (x_0, y_0).
  • Catastrophic floating-point cancellation when vertex coordinates have huge offsets (e.g. UTM coordinates); subtract the first vertex (x_0, y_0) to shift near the origin before summing.

Interactive Mechanism Walkthrough & State Debugger

Spatial Primitive & Sweep-Line Canvas
Shoelace Formula mechanism walkthrough step 1 of 5
sweep-line Xx = 60px
active hull vertices2
orientation testccw(p, q, r) > 0
invariantUpper/Lower Envelope
Step 1 of 5: Initialize twiceSignedArea = 0

Sources (1)

What each reference supports for this entry.

Meister (1769) / Gauss — Generalia de genesi figurarum planarum

Paper

Classical derivation of polygonal area from boundary vertex coordinates.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Often paired withEar Clipping Triangulation

Geometry · Core

Signed area from the Shoelace formula determines polygon winding orientation prior to ear clipping.

Compare with this

Relationships

View full relationship page
Often paired withEar Clipping Triangulation

Signed area from the Shoelace formula determines polygon winding orientation prior to ear clipping.

Related Algorithms

Point in PolygonAndrew's Monotone ChainEar Clipping Triangulation

Tags

GeometryPolygonsComputational GeometryLinear Time