Polygon Area β Shoelace Formula and Applications
- Shoelace: area = |Ξ£(xα΅’yα΅’ββ - xα΅’ββyα΅’)| / 2. O(n) time, O(1) space.
- Signed area: positive = CCW, negative = CW. Essential for polygon orientation detection.
- Works for any simple polygon (non-self-intersecting), including non-convex.
The Shoelace formula (also Gauss's area formula, 1795) computes polygon area in O(n) from vertex coordinates. It is named for the pattern of cross-multiplication that resembles lacing a shoe. Beyond area, the formula's signed result reveals polygon orientation β fundamental for polygon clipping, triangulation, and ray casting. Every GIS system, every game physics engine, and every computational geometry library implements it.
Shoelace Formula
For a polygon with vertices (x1,y1), (x2,y2), ..., (xn,yn): Area = |Ξ£α΅’ (xα΅’Γyα΅’ββ - xα΅’ββΓyα΅’)| / 2
The signed version (without absolute value) is positive for CCW polygons, negative for CW.
def polygon_area(vertices: list[tuple]) -> float: """Signed area: positive = CCW, negative = CW.""" n = len(vertices) area = 0 for i in range(n): j = (i + 1) % n area += vertices[i][0] * vertices[j][1] area -= vertices[j][0] * vertices[i][1] return area / 2 def polygon_area_abs(vertices): return abs(polygon_area(vertices)) def is_counterclockwise(vertices): return polygon_area(vertices) > 0 # Unit square square = [(0,0),(1,0),(1,1),(0,1)] print(f'Area: {polygon_area_abs(square)}') # 1.0 print(f'CCW: {is_counterclockwise(square)}') # True # Triangle triangle = [(0,0),(4,0),(2,3)] print(f'Triangle area: {polygon_area_abs(triangle)}') # 6.0
CCW: True
Triangle area: 6.0
Centroid and Applications
def polygon_centroid(vertices): """Centroid (geometric centre) of a polygon.""" n = len(vertices) cx = cy = 0 area = polygon_area(vertices) # signed for i in range(n): j = (i + 1) % n cross = vertices[i][0]*vertices[j][1] - vertices[j][0]*vertices[i][1] cx += (vertices[i][0] + vertices[j][0]) * cross cy += (vertices[i][1] + vertices[j][1]) * cross factor = 1 / (6 * area) return (cx * factor, cy * factor) print(polygon_centroid([(0,0),(4,0),(4,4),(0,4)])) # (2.0, 2.0)
π― Key Takeaways
- Shoelace: area = |Ξ£(xα΅’yα΅’ββ - xα΅’ββyα΅’)| / 2. O(n) time, O(1) space.
- Signed area: positive = CCW, negative = CW. Essential for polygon orientation detection.
- Works for any simple polygon (non-self-intersecting), including non-convex.
- Exact for integer coordinates β no floating point error.
Interview Questions on This Topic
- QDerive the Shoelace formula from the trapezoidal decomposition.
- QHow does the signed area indicate polygon winding order?
- QWhat is the area of a polygon with vertices (0,0),(3,0),(3,4)?
Frequently Asked Questions
Does the Shoelace formula work for self-intersecting polygons?
It computes the algebraic area β regions traced clockwise cancel regions traced counterclockwise. For a figure-8, the two loops cancel to give area 0. This is correct for some applications (winding number calculation) but not for physical area.
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.