Ear Clipping Triangulation

Give a computer a jagged outline — the silhouette of a country, a cartoon cloud, a game character's hitbox — and sooner or later it needs to fill that shape, light it, or collide something against it. Almost every one of those operations is easiest on triangles, so the shape has to be cut into them first.

Ear clipping is the oldest and most intuitive way to do that cutting. Look at the polygon's corners one at a time. If a corner's tip can be sliced off with a single straight cut — a triangle that stays entirely inside the shape and traps no other corner — that corner is called an ear. Snip it off, and you are left with a smaller polygon and one more triangle in your collection. Keep going.

There is nothing clever about any single step. The whole trick is a guarantee: no matter how twisted the polygon, you can never get stuck without an ear to snip. That guarantee is what turns "seems to work" into an actual algorithm.

Here is a simple polygon with its corners numbered. At every step the algorithm tests each corner: is the triangle it forms with its two neighbors entirely inside the polygon, and empty of every other corner? If so, that corner is an ear and gets highlighted as a candidate.

<p class="hint">{{hint_para}}</p>
<svg id="stage" class="stage" viewBox="0 0 300 190" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="clip" type="button">{{btn_clip}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.stage { width: 100%; max-width: 460px; height: auto; background: #f4f6f8; border-radius: 10px;
         border: 1px solid #dde3e8; display: block; }
.tri { fill: #a8dadc; fill-opacity: .55; stroke: #1d3557; stroke-width: .8; }
.remaining { fill: #e8eef3; fill-opacity: .9; stroke: #457b9d; stroke-width: 1.4; }
.ear-candidate { fill: #ffe08a; fill-opacity: .85; stroke: #e09f3e; stroke-width: 1.2; }
.vertex { fill: #1d3557; }
.vertex.candidate-pt { fill: #e63946; }
.vlabel { font: 600 8px ui-monospace, monospace; fill: #1d3557; pointer-events: none; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Press Clip one ear to snip the first valid candidate it finds, or Auto-clip to run the whole process to completion. Watch the corner count shrink by one with every clip, and the triangle count grow by one, until a single triangle is all that remains. A polygon with n corners always yields exactly $n - 2$ triangles, and never fewer.

Ear clipping raises two separate questions, and both have been fully answered.

• Does it always work? Yes. The two-ears theorem, proved by Gary Meisters in 1975, guarantees that every simple polygon with more than three corners has at least two ears at any point in the process. That rules out the scary scenario where clipping paints you into a corner with no legal move left — it simply cannot happen.
• How fast is it? Testing whether one corner is currently an ear means checking it against every other corner — an $O(n)$ scan. You do that scan for (in the worst case) every one of the roughly $n$ corners you clip, one after another, giving the classic $O(n^{2})$ running time.
• Can it be faster? Yes, dramatically. Smarter approaches avoid the repeated full scans: sweep-line methods reach $O(n \log n)$, and in 1991 Bernard Chazelle proved that any simple polygon can be triangulated in optimal $O(n)$, linear time. Ear clipping stays popular anyway, because $O(n^2)$ is plenty fast for the modest polygons — building outlines, map regions, font glyphs — that most software actually deals with, and the algorithm is short enough to implement correctly in an afternoon.

So unlike P vs NP-flavored problems, there is no wall of exponential brute force lurking here. The only real complexity is bookkeeping: convince yourself the ear you found is genuinely empty, snip, repeat, and the proof handles the rest.

Because it is short, robust, and needs no advanced data structures, ear clipping is often the triangulator that ships by default:

• 2D graphics libraries: filling an arbitrary polygon on a GPU usually means triangulating it first, and many rendering libraries reach for ear clipping because it is easy to get right.
• Font rendering: the curvy outlines of letters are approximated by polygons, then ear-clipped into triangles so the GPU can rasterize the glyph.
• Game engine tools: level editors and navigation-mesh generators triangulate hand-drawn floor plans and collision shapes with ear clipping before the physics engine ever sees them.
• GIS and mapping: administrative boundaries and lake shapes arrive as polygons; filling or shading them on a map means triangulating first.

Anywhere a jagged 2D outline needs to become triangles cheaply and reliably, this is usually the first algorithm reached for — and it sits right next to polygon triangulation in general and the art gallery theorem, which uses the very same triangulated structure to figure out how many guards a museum needs.

Ear clipping is a rare kind of algorithm: the idea is obvious enough to explain with scissors and paper, the proof that it works is a clean piece of 1970s geometry, and the running time is easy to bound. There is no open question here, no forced guess, no combinatorial explosion waiting in the wings.

That is exactly why it endures. Faster triangulators exist, down to Chazelle's optimal linear-time result, but for the polygons most software actually meets, snipping one honest ear at a time is still simple enough to trust — and fast enough that nobody bothers to replace it.