Ear Clipping Visualization | Cutting a Polygon into Triangles

The idea: cut off an ear

A graphics card can only fill triangles. To draw any other filled shape, a font letter, a country on a map, a polygon in a game, the program first cuts the shape into triangles. This is polygon triangulation, and ear clipping is the simplest way to do it.

An ear is a corner v, with neighbours p and n, whose triangle p v n lies wholly inside the polygon. Cut along the line p–n (a diagonal) and the ear falls off as one triangle. What is left is a polygon with one vertex less. Repeat until 3 vertices are left.

The page's 10-gon A to J. The triangle B C D at corner C is green: an ear. The triangle J A B at corner A is orange and holds the reflex vertex I: blocked. The triangle A B C at corner B is red: B is reflex and its triangle lies outside. — Three kinds of corner: C is an ear, A is convex but blocked by I, B is reflex.

The page uses polygons with whole-number coordinates, listed counter-clockwise, so every test is exact and can be checked by hand.

Convex or reflex: one cross product

Walk along the boundary from p to v to n. If the walk turns left, the inside angle at v is under 180° and v is convex. If it turns right, the angle is over 180° and v is reflex. The turn is the sign of the cross product:

cross(p, v, n) = (vx − px)·(ny − py) − (vy − py)·(nx − px)
> 0: left turn, convex       ≤ 0: right turn (or straight), reflex

A reflex corner can never be an ear: its triangle lies outside the polygon. In the 10-gon, B, E, G and I are reflex. The same test is used to build a convex hull, see Convex Hull: Graham Scan vs Gift Wrapping.

Is a convex corner an ear?

A convex corner is an ear only if no other vertex lies inside its triangle (or on its edges). If one does, the diagonal p–n would cross the boundary. Point q is inside triangle p v n when it is on the left of all three edges:

cross(p, v, q) ≥ 0  and  cross(v, n, q) ≥ 0  and  cross(n, p, q) ≥ 0

Only reflex vertices need to be tested. If any vertex is inside the triangle, the boundary has to dent into it, and a dent has a reflex vertex inside the triangle. So the page tests only the red vertices. At A, the triangle J A B holds I, so A is blocked; B is reflex; C is the first ear (Demo: A is blocked, B is reflex, C is the first ear).

Clip and repeat: n − 2 triangles

Examine the vertex at the scan pointer. Reflex or blocked: move to the next vertex.
An ear: output the triangle p v n, draw the diagonal p–n and remove v from the list.
Only p and n can change their status, so the scan goes on at n.
When 3 vertices are left, they are the last triangle.

Each clip removes one vertex and makes one triangle, and the last 3 vertices make one more. So an n-gon always gives n − 2 triangles, joined by n − 3 diagonals. The angles agree: the inside angles of an n-gon add up to (n − 2)·180°, which is n − 2 triangles' worth.

Left: the 10-gon A to J. Right: the same polygon cut into 8 numbered triangles B C D, B D E, B E F, B F G, B G H, B H I, I J A and A B I by 7 blue diagonals. — The 10-gon becomes 8 triangles and 7 diagonals, whatever order the ears are clipped in.

In the 10-gon, every clip after C happens next to B, so B ends up in six triangles, a fan. A clip can also turn a reflex vertex convex: once D is gone, E's neighbour is B, and B → E → F turns left (Demo: clip every ear of the 10-gon).

The two ears theorem

Can the scan get stuck, with no ear anywhere? No. Gary Meisters proved in 1975 that every simple polygon with more than 3 vertices has at least two ears that do not overlap. After a clip the rest is still a simple polygon, so there is always another ear to find. The 10-gon starts with 5 ears: C, D, F, H and J (Demo: find all the ears).

Cost and triangle shape

Polygon	n	Vertices examined	Point tests	Triangles
10-gon	10	10	12	8
Convex hexagon	6	3	0	4
Comb	10	13	12	8

A convex polygon has no reflex vertex, so every corner is an ear and the result is a fan from one vertex with no point tests at all (Demo: a convex hexagon becomes a fan). In the comb, the teeth are reflex and block the corners at the base (Demo: the comb). Each ear test can cost O(n) point tests and there are n − 2 ears to find, so the simple method is O(n²). That is fast enough for the few hundred vertices of a glyph or a map shape, which is why real libraries use it.

Ear clipping takes the first ear it finds, so it can make long thin slivers, like the fan around B. When triangle shape matters, the Delaunay rule gives fat triangles: see Delaunay Triangulation: Bowyer–Watson and Edge Flips.

Where it is used

Once the polygon is triangles, the GPU fills each one pixel by pixel, as in Rasterization: Edge Functions and the Z-Buffer. Mapbox's earcut library triangulates map shapes this way in web maps, and 3D tools use it to turn n-sided faces into triangles. A convex polygon with n corners has many triangulations, one per Catalan number C(n − 2): 5 for a pentagon, see Catalan Numbers. The cheapest of them can be found with interval dynamic programming, like the order in Matrix Chain Multiplication.

What the page leaves out

The page leaves out polygons with holes (real code joins each hole to the outer boundary with a bridge edge first), self-crossing polygons, repeated points and three vertices on one line, floating-point coordinates and their rounding errors, the faster O(n log n) method that first splits the polygon into monotone pieces, Chazelle's linear-time algorithm, and the tricks real libraries use to skip point tests, such as a z-order curve over the reflex vertices.