Polygons: Planar, Closed, and Simple | Algorithms II

Definitions

A polygon is a planar figure bounded by a closed chain of line segments (edges) connecting an ordered sequence of vertices. Three properties are critical for the algorithms in this module:

Planar

The polygon lies in a 2D flat plane that is infinite in both directions. On a non-planar surface (e.g. a sphere), “inside” vs “outside” is ambiguous: a closed polygon boundary divides the surface into two finite regions, and either could be labelled “inside.”

On a planar surface, the polygon’s boundary separates a finite region (inside) from an infinite region (outside).

Closed

A closed polygon has an edge from its last vertex back to its first, forming a complete loop. An open polygon does not enclose any area, so “inside” and “outside” are not defined.

Example: the letter O is closed and encloses area; the letter C is open and does not.

Simple

A simple polygon has no self-intersections; edges meet only at vertices and nowhere else.

Simple vs self-intersecting polygon

Other Classifications

Convex polygon: All interior angles $< 180^\circ$ . Any line segment connecting two interior points lies entirely inside the polygon. A convex polygon’s interior is the intersection of the half-planes defined by each edge.
Star-shaped polygon: There exists at least one point from which the entire polygon is visible.
Monotone polygon: For some direction (typically horizontal), every line perpendicular to that direction intersects the polygon in at most one connected segment.

Representation

A polygon is represented as an ordered list of vertices $p_1, p_2, \ldots, p_n$ , with edges $(p_i, p_{i+1})$ for $i = 1 \ldots n-1$ and $(p_n, p_1)$ for a closed polygon.

The order can be clockwise (CW) or counter-clockwise (CCW). Many algorithms assume CCW order.

Area: The Shoelace Formula

For a simple polygon with vertices $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ in order, the signed area is:

$A = \frac{1}{2} \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i)$

where $(x_{n+1}, y_{n+1}) = (x_1, y_1)$ .

$A > 0$ : vertices are ordered counter-clockwise
$A < 0$ : vertices are ordered clockwise
$A = 0$ : degenerate (collinear vertices or self-intersecting)

The absolute value $|A|$ gives the polygon’s area.

Worked Example

Triangle with vertices $(0,0)$ , $(4,0)$ , $(0,3)$ in CCW order:

$A = \frac{1}{2}[0 \cdot 0 - 4 \cdot 0 + 4 \cdot 3 - 0 \cdot 0 + 0 \cdot 0 - 0 \cdot 3] = \frac{1}{2}[0 + 12 + 0] = 6$

The actual area of this right triangle is $\frac{1}{2} \cdot 4 \cdot 3 = 6$ . The positive sign confirms CCW order.

Degenerate Cases

Collinear points: three consecutive vertices lying on a straight line produce zero contribution from the middle vertex. This can be simplified by removing the middle vertex.
Zero area: if the points form a line rather than a shape, the shoelace sum is zero.

Summary

Property	Meaning
Planar	Lies in a 2D flat plane
Closed	Last vertex connects to first
Simple	No self-intersections
Convex	All line segments between interior points stay inside
Shoelace formula	$A = \frac{1}{2} \sum (x_i y_{i+1} - x_{i+1} y_i)$
Signed area sign	$>0$ = CCW, $<0$ = CW
Time for area	$\Theta(n)$