This document explains the ear-clipping triangulation algorithm in full detail, with particular attention to the mathematical foundations of each geometric test and the manner in which the algorithm is guaranteed to terminate.
Given a simple polygon with n vertices — no holes, no self-intersections — partition its interior into non-overlapping triangles that cover it exactly. The result always contains exactly n − 2 triangles. Ear-clipping achieves this by repeatedly identifying and removing a single vertex whose local triangle is entirely interior to the polygon, until only three vertices remain.
Every geometric decision in the algorithm reduces to a single scalar. Begin with the 3D cross product. Embed two 2D vectors in 3D by setting z = 0:
u = (u.x, u.y, 0) v = (v.x, v.y, 0)
| i j k |
u x v = | u.x u.y 0 |
| v.x v.y 0 |
= i(u.y*0 - 0*v.y) - j(u.x*0 - 0*v.x) + k(u.x*v.y - u.y*v.x) = (0, 0, u.x*v.y - u.y*v.x)
The x and y components vanish. Only the z-component survives:
The cross product magnitude is
|u x v| = |u| |v| sin(θ)where θ is the angle from u to v measured counter-clockwise. sin(θ) is what carries the sign:
θ ∈ (0, 180) --> sin(θ) > 0 --> cross > 0 --> left turn
θ ∈ (180, 360) --> sin(θ) < 0 --> cross < 0 --> right turn
So the sign of the cross product is the sign of sin(θ), which is positive for
angles in the upper half and negative for angles in the lower half. A left turn
means v is in the upper half-plane relative to u, a right turn means it is in
the lower half.
The blue arrow is u, the red arrow is v. The shaded area equals |cross(u,v)|. The box on the right sketches the formula: the blue bar represents u.x*v.y, the red bar represents u.y*v.x, their difference is the signed area.
For three points A, B, C, form vectors from B:
| Sign | Meaning |
|---|---|
| > 0 | A → B → C is a counter-clockwise (left) turn |
| < 0 | A → B → C is a clockwise (right) turn |
| = 0 | A, B, C are collinear |
Left: the turn from u (black) to v (blue) is CCW, cross > 0, marked with +. Right: the turn to v (red) is CW, cross < 0, marked with −. The shaded wedge shows the angular region between the vectors.
Before any cross product sign can be interpreted, the winding order of the polygon vertices must be established. The Shoelace formula gives the signed area:
If 2A > 0, the vertices are in counter-clockwise order.
If 2A < 0, the vertices are in clockwise order.
Every cross-product sign test in the remainder of the algorithm depends on this convention being consistent. If the polygon arrives in clockwise order, reverse the vertex list before proceeding.
For three consecutive polygon vertices V_{i-1}, V_i, V_{i+1}, form edge vectors from the middle vertex:
For a CCW polygon the interior is always to the left of each directed edge. At a convex vertex the path bends leftward, agreeing with the winding, so D > 0 and the interior angle is less than 180 degrees. At a reflex vertex the path bends rightward against the winding, so D < 0 and the interior angle exceeds 180 degrees. The cross product is the signed measure of that bending.
Left: a convex vertex (blue dot). The cross product is positive; the green arrow points with the CCW winding; interior angle < 180. Right: a reflex vertex (red dot). The cross product is negative; the red arrow points against the winding; interior angle > 180.
A reflex vertex cannot be an ear tip. The triangle formed at a reflex vertex would extend outside the polygon. Only convex vertices are candidates.
To validate a candidate ear, no other polygon vertex may fall inside the proposed triangle. The test follows from the same left-of-edge logic. A CCW triangle (A, B, C) has its interior on the left of every directed edge. A point P is inside if and only if it is to the left of A→B, left of B→C, and left of C→A simultaneously:
If even one value flips sign, P lies outside that edge and therefore outside the triangle.
Green dot (P): inside the triangle, all three d values positive. Red dot (Q): outside, it fails the test for at least one edge. Blue arrows show the inward normals of each edge.
A vertex V_i is an ear tip when both of the following conditions hold:
1. V_i is convex (cross product at V_i is positive, Section 4).
2. The triangle (V_{i-1}, V_i, V_{i+1}) contains no other polygon vertex in its interior (Section 5).
Condition 1 ensures the triangle lies on the correct side of the boundary. Condition 2 ensures it does not intrude on a concave indent. A reflex vertex inside the candidate triangle would mean the triangle cuts across a region not belonging to it.
Orange shading: a candidate ear blocked because a reflex vertex (red X) falls inside it. Green shading: a valid ear on the bottom-left corner, no other vertex inside. Blue dots are convex vertices; the orange and green dots mark the respective ear tips.
The algorithm terminates because of a result due to Gary Meisters (1975): every simple polygon with four or more vertices has at least two non-overlapping ears. This guarantees that the search will always find an ear. Each successful clip removes one vertex. Starting from n vertices and ending at 3, the loop runs n − 3 times, yielding n − 3 clipped triangles plus the one final triangle, for a total of n − 2 triangles.
The image below shows four frames. Each frame is the polygon after the previous ear has been removed. The highlighted triangle is the ear being clipped in that step and the coloured dot marks the ear tip.
Frame 1: original 6-vertex L-shape, red ear at V1. Frame 2: after removing V1, green ear at the new V1. Frame 3: after that removal, blue ear. Frame 4: final triangle, yellow.
The following triangulates a polygon and renders each clipped triangle into a pixel buffer using canvas.h. Compile with cc sketch.c -o sketch -lm.
| Concept | Math behind it |
|---|---|
| Winding direction | Sign of Shoelace formula (signed area) |
| Convex vs reflex vertex | Sign of cross product at that vertex |
| Is P left of edge A→B? | Sign of (B−A) × (P−A) |
| Is P inside a triangle? | All three edge cross products share the same sign |
| Does an ear always exist? | Two-Ears Theorem (Meisters, 1975) |
| Triangle count | n − 2 |
| Time complexity | O(n^2) naive |