Introduction

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.

Snip an Ear

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">Corners are numbered 0-6. The <b>yellow</b> triangle is the next ear: three consecutive corners whose triangle stays fully inside the shape and traps no other corner. Clip it, and the polygon shrinks by one corner.</p>
<svg id="stage" class="stage" viewBox="0 0 300 190" xmlns="http://www.w3.org/2000/svg"></svg>
<div class="status" id="status">Ready to clip the first ear.</div>
<div class="btns">
  <button id="clip" type="button">Clip one ear</button>
  <button id="auto" type="button">Auto-clip</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The demo polygon is a fixed 7-corner shape with two inward notches (reflex corners).
const SCALE = 24, OX = 20, OY = 165;
const RAW = [[0,0],[10,0],[10,6],[7,3],[5,6],[3,3],[0,6]]; // Vertex coordinates in a simple integer grid, listed counterclockwise.
const N0 = RAW.length;
const toScreen = ([x,y]) => [OX + x*SCALE, OY - y*SCALE];

// cross(): signed area x2 of o-a-b; signedArea(): polygon orientation; pointInTriangle(): barycentric-sign test.
function cross(o,a,b){ return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]); }
function signedArea(poly){ let s=0; for(let i=0;i<poly.length;i++){ const [x1,y1]=poly[i], [x2,y2]=poly[(i+1)%poly.length]; s += x1*y2 - x2*y1; } return s/2; }
function pointInTriangle(p,a,b,c){
  const d1=cross(a,b,p), d2=cross(b,c,p), d3=cross(c,a,p);
  const neg = d1<0||d2<0||d3<0, pos = d1>0||d2>0||d3>0;
  return !(neg && pos);
}
const CCW = signedArea(RAW) > 0;

// A corner is an ear iff its triangle turns the same way as the polygon (convex) and contains no other vertex.
function isEarAt(poly, i){
  const n = poly.length;
  const prev = poly[(i-1+n)%n].pt, cur = poly[i].pt, next = poly[(i+1)%n].pt;
  const cr = cross(prev, cur, next);
  if (CCW ? cr <= 0 : cr >= 0) return false; // Reflex (concave) corners can never be ears — skip them immediately.
  for(let j=0;j<n;j++){
    if (j===i || j===(i-1+n)%n || j===(i+1)%n) continue;
    if (pointInTriangle(poly[j].pt, prev, cur, next)) return false; // If any other vertex sits inside this candidate triangle, clipping it would cut through the polygon — reject it.
  }
  return true;
}
function findFirstEar(poly){
  for(let i=0;i<poly.length;i++) if (isEarAt(poly, i)) return i;
  return -1;
}

let poly = RAW.map((p, idx) => ({ pt: p, idx }));
let triangles = []; // Accumulates the triangles produced so far, in clip order.
let done = false;

function render(){
  const svg = document.getElementById('stage');
  svg.innerHTML = '';
  const ns = 'http://www.w3.org/2000/svg';
  // Render every triangle already clipped so far, in the accent fill color.
  triangles.forEach(([a,b,c]) => {
    const pts = [a,b,c].map(idx => toScreen(RAW[idx])).map(p => p.join(',')).join(' ');
    const el = document.createElementNS(ns, 'polygon');
    el.setAttribute('points', pts);
    el.setAttribute('class', 'tri');
    svg.appendChild(el);
  });
  // Render the still-uncut remaining polygon on top.
  if (poly.length >= 3) {
    const pts = poly.map(v => toScreen(v.pt)).map(p => p.join(',')).join(' ');
    const el = document.createElementNS(ns, 'polygon');
    el.setAttribute('points', pts);
    el.setAttribute('class', 'remaining');
    svg.appendChild(el);
  }
  // Find and highlight the next ear that would be clipped, if any.
  const earIdx = !done ? findFirstEar(poly) : -1;
  if (earIdx >= 0) {
    const n = poly.length;
    const prev = poly[(earIdx-1+n)%n].pt, cur = poly[earIdx].pt, next = poly[(earIdx+1)%n].pt;
    const pts = [prev,cur,next].map(toScreen).map(p => p.join(',')).join(' ');
    const el = document.createElementNS(ns, 'polygon');
    el.setAttribute('points', pts);
    el.setAttribute('class', 'ear-candidate');
    svg.appendChild(el);
  }
  // Draw a dot and index label at every remaining corner.
  poly.forEach((v, i) => {
    const [sx, sy] = toScreen(v.pt);
    const dot = document.createElementNS(ns, 'circle');
    dot.setAttribute('cx', sx); dot.setAttribute('cy', sy); dot.setAttribute('r', 3.4);
    dot.setAttribute('class', 'vertex' + (i === earIdx ? ' candidate-pt' : ''));
    svg.appendChild(dot);
    const label = document.createElementNS(ns, 'text');
    label.setAttribute('x', sx + 5); label.setAttribute('y', sy - 5);
    label.setAttribute('class', 'vlabel');
    label.textContent = v.idx;
    svg.appendChild(label);
  });
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function clipOne(){
  if (done) return;
  const i = findFirstEar(poly);
  if (i < 0) { setStatus('No ear candidate found (this should never happen on a simple polygon).', 'info'); return; }
  const n = poly.length;
  const prev = poly[(i-1+n)%n], cur = poly[i], next = poly[(i+1)%n];
  triangles.push([prev.idx, cur.idx, next.idx]);
  poly.splice(i, 1);
  if (poly.length === 3) {
    triangles.push([poly[0].idx, poly[1].idx, poly[2].idx]);
    done = true;
  }
  render();
  if (done) {
    setStatus(i18nFmt('Done — the polygon is fully triangulated into %n% triangles.', { n: triangles.length }), 'ok');
    document.getElementById('clip').disabled = true;
    document.getElementById('auto').disabled = true;
    console.log('Triangulation complete. Triangles:', triangles.length, 'expected (n-2):', N0 - 2);
  } else {
    setStatus(i18nFmt('%left% corners left, %tri% triangle(s) cut so far.', { left: poly.length, tri: triangles.length }), 'info');
  }
}

function autoClip(){
  let guard = 0;
  while (!done && guard < 100) { clipOne(); guard++; }
}

function reset(){
  poly = RAW.map((p, idx) => ({ pt: p, idx }));
  triangles = [];
  done = false;
  document.getElementById('clip').disabled = false;
  document.getElementById('auto').disabled = false;
  setStatus('Ready to clip the first ear.', 'info');
  render();
}

document.getElementById('clip').addEventListener('click', clipOne);
document.getElementById('auto').addEventListener('click', autoClip);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

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−2n - 2 triangles, and never fewer.

The Real Complexity

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)O(n) scan. You do that scan for (in the worst case) every one of the roughly nn corners you clip, one after another, giving the classic O(n2)O(n^{2}) running time.
  • Can it be faster? Yes, dramatically. Smarter approaches avoid the repeated full scans: sweep-line methods reach O(nlog⁡n)O(n \log n), and in 1991 Bernard Chazelle proved that any simple polygon can be triangulated in optimal O(n)O(n), linear time. Ear clipping stays popular anyway, because O(n2)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/ear-clipping-triangulation/Content licensed under CC BY-NC 4.0.