Every other entry in this site's Geometry category answers one question about a fixed shape —
does this point sit inside it, do these two segments cross, which polygon owns this later query.
Triangulation asks something different: cut a simple polygon (convex or concave, same freedom as
Point in Polygon) into n − 2 triangles
that exactly tile it, no gaps and no overlaps. Triangles are the shape every downstream consumer
actually wants — a GPU rasterizes triangles, not arbitrary polygons; an area or centroid computation
over triangles is trivial; a physics engine's collision routines assume convex pieces. Ear
clipping is the direct way to get there: find a vertex that can be safely cut off along with
its two neighboring edges, cut it, and repeat until three vertices remain — the loop terminates by
finding an ear, one triangle at a time.
An ear is a vertex v, with neighbors prev and
next, that satisfies two conditions: the interior angle at v is convex
(less than 180°), and no other vertex of the polygon lies inside the triangle
(prev, v, next). Cut that triangle off — remove v, connect
prev directly to next with a new diagonal — and what's left is still a
valid simple polygon, one vertex smaller, ready for the same test again.
The same seven-vertex arrow polygon used by Point in Polygon and Slab Decomposition, vertices numbered 0–6 in their original order. Step through and watch two things that look like they shouldn't happen but do, verified live from the polygon's real coordinates every time: vertex 1 and vertex 5 both start out reflex (concave, can never be an ear) and later become ears once clipping changes who their neighbors are; vertex 3 starts out convex but blocked — vertex 5 sits inside its candidate triangle — and later becomes an ear too, the moment vertex 5 stops being a third-party point and becomes vertex 3's own direct neighbor instead.
Termination is guaranteed by a classical fact usually called the two ears theorem
(G. H. Meisters, 1975): every simple polygon with four or more vertices has at least two ears. Cutting
one off is always safe — by the very definition of an ear, nothing else lies inside triangle
(prev, v, next), so the new diagonal (prev, next) can't cross any other edge
of the polygon, and what remains is still a simple polygon, still satisfying the same theorem, one
vertex lighter. Repeat n − 3 times and three vertices are left — trivially a triangle,
no test needed — for n − 2 triangles in total.
A vertex's own convexity depends only on itself and its two current neighbors, so clipping an ear
can only possibly change the convexity of that ear's own prev and next —
every other live vertex's neighbors are untouched. The "is anything else inside my triangle" half of
the test only ever gets easier to satisfy as vertices are removed, since there are strictly
fewer candidates left to intrude — a vertex once confirmed an ear stays a valid ear forever. So a
correct O(n²) implementation doesn't need to retest every remaining vertex after every
clip: cache each live vertex's ear/reflex status, and after clipping v, only recompute
its former neighbors prev and next — they're the only two whose own local
geometry actually changed. This page's own demo shows both flavors of that recheck landing on the
same polygon: vertex 1 flips from reflex to ear once its neighbor set changes; vertex 3 flips from
blocked to ear once its blocker, vertex 5, becomes its own neighbor instead of a third party sitting
inside its triangle.
function triangulate(poly) {
const ccw = signedArea(poly) > 0;
const nodes = poly.map((p, i) => ({ ...p, idx: i, prev: null, next: null }));
nodes.forEach((n, i) => {
n.prev = nodes[(i - 1 + nodes.length) % nodes.length];
n.next = nodes[(i + 1) % nodes.length];
});
function isConvex(n) {
const c = cross(n.prev, n, n.next);
return ccw ? c > 0 : c < 0;
}
function blockerOf(n) { // any other live vertex inside triangle (prev, n, next)?
let k = n.next.next;
while (k !== n.prev) {
if (pointInTriangle(k, n.prev, n, n.next)) return k;
k = k.next;
}
return null;
}
function updateStatus(n) {
n.isReflex = !isConvex(n);
n.isEar = !n.isReflex && blockerOf(n) === null;
}
nodes.forEach(updateStatus);
let live = nodes.length, scanStart = nodes[0], triangles = [];
while (live > 3) {
let cur = scanStart;
while (!cur.isEar) cur = cur.next; // guaranteed to find one — two ears theorem
const { prev, next } = cur;
triangles.push([prev.idx, cur.idx, next.idx]);
prev.next = next; next.prev = prev; // clip
live--; scanStart = next;
updateStatus(prev); updateStatus(next); // only these two can have changed
}
triangles.push([scanStart.idx, scanStart.next.idx, scanStart.next.next.idx]);
return triangles;
}Convexity alone isn't enough to make a vertex an ear — skipping the "does anything else sit inside my triangle" check produces a wrong triangulation with the same triangle count, not an obvious crash. On this page's own arrow polygon, vertex 3 (the tip) is convex from the start, so a version of the algorithm that clips the first convex vertex it finds — no containment check at all — clips it immediately instead of waiting for it to legitimately become an ear once vertex 5 is gone. Ran both versions to completion on this exact polygon: the correct version (shown above) produces 5 triangles summing to exactly 57,000, matching the polygon's own shoelace area; the convexity-only version also produces 5 triangles, but they sum to 67,000 — 10,000 too much, because two of its triangles overlap around vertex 3's premature cut instead of tiling cleanly. The triangle count alone is not a correctness check.
Skipping the neighbor recheck after a clip — leaving prev and
next's cached status stale — breaks the algorithm on most inputs, but not reliably
enough to catch on a small example. Tested directly: on this page's own seven-vertex arrow,
a version with the two updateStatus calls removed after each clip still happens to
produce the correct 5 triangles, purely because one particular vertex (0) stays flagged an ear the
whole time and keeps supplying a valid clip every round — a coincidence of this specific polygon's
shape, not evidence the shortcut is safe. Run the same broken version across 3,000 random simple
polygons (5–30 vertices, generated by sorting random points around a center and connecting them in
angular order, each one independently confirmed genuinely simple — non-self-intersecting — before
being trusted as a test case): it gets stuck with no ear left to find on 334 of them, produces the
wrong triangle count or a wrong total area on another 515, and only happens to come out correct on
the remaining 2,151. Skipping the recheck isn't a shortcut that trades correctness for speed — it's
broken on 28% of random inputs, and the other 72% is luck, not a guarantee.
Time: O(n²). There are n − 2 clips; each one scans the
live vertex list for a cached ear flag (O(n) worst case) and recomputes exactly two
vertices' status, each an O(n) containment check against every other live vertex — so
each clip costs O(n), and O(n) clips give O(n²) total.
Space: O(n) for the doubly linked vertex list and the output triangle
list. Sorting-based algorithms that first decompose the polygon into monotone pieces
bring worst-case time down to O(n log n) — themselves typically built with a plane-sweep
structure in the same family as the randomized incremental trapezoidal map named on
Slab Decomposition and
Point in Polygon's own Complexity sections, still not
built on this site. A genuinely linear O(n) algorithm exists (Chazelle, 1991), but it's
complex enough that it's essentially never used in practice — O(n log n) monotone
decomposition is the real-world standard for anything beyond ear clipping's simplicity.
This site's guide, Choosing a Geometry Algorithm, places this entry as the route to take when a simple polygon's boundary already exists and needs cutting into triangles — reach for Delaunay Triangulation instead when there's no boundary to start from, only a bare point set.