Introduction

Give a computer graphics engine, a mesh generator, or a robot's path planner a simple polygon — any closed shape with straight sides and no self-crossings — and sooner or later it needs to break that polygon into triangles. Triangles are the atoms of computational geometry: easy to render, easy to reason about, easy to feed into physics and rendering pipelines.

Any simple polygon with nn vertices can always be triangulated into exactly n−2n-2 triangles using only diagonals that stay inside the shape. The question is not whether it can be done — it's how fast.

The naive approach pokes around for a valid diagonal, cuts, and repeats, costing O(n2)O(n^2) or worse. But if you first slice the polygon into pieces that are y-monotone — pieces where a vertical sweep never has to backtrack — each piece can be triangulated in a single linear pass with nothing more than a stack. That two-stage idea, sweep-to-split then stack-to-triangulate, is one of the cleanest results in computational geometry.

Try the Sweep

Below is a y-monotone polygon: a horizontal line crosses its boundary at most twice at any height, so every vertex can be visited in order from top to bottom. Press Step to advance the sweep one vertex at a time and watch the stack fill up and empty out as diagonals get added.

<p class="hint">This polygon is <b>y-monotone</b>: a horizontal line crosses its boundary at most twice at any height. The sweep visits every vertex top to bottom, using a stack to decide exactly when a diagonal closes off a triangle.</p>
<svg id="stage" viewBox="0 0 320 320" class="stage"></svg>
<div class="panel">
  <div class="stackbox">
    <div class="stacklabel">Stack</div>
    <div id="stackview" class="stackview"></div>
  </div>
  <div class="status" id="status">Press Step to start the sweep.</div>
</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="auto" type="button">Auto-play</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: 320px; height: 260px; display: block; margin: 0 auto; background: #f7f9fb;
         border: 1px solid #dde3e9; border-radius: 8px; }
.poly-fill { fill: #e8eef3; stroke: none; }
.edge { fill: none; stroke: #1d3557; stroke-width: 2; }
.diagonal { fill: none; stroke: #e63946; stroke-width: 2; stroke-dasharray: 5 4; }
.vtx { fill: #1d3557; }
.vtx.done { fill: #adb1b8; }
.vtx.current { fill: #e63946; }
.panel { display: flex; align-items: flex-start; justify-content: space-between; gap: .75rem;
         margin: .6rem 0; flex-wrap: wrap; }
.stackbox { background: #fff; border: 1px solid #dde3e9; border-radius: 8px; padding: .4rem .6rem; min-width: 110px; }
.stacklabel { font-size: .75rem; font-weight: 700; color: #1d3557; text-transform: uppercase; letter-spacing: .03em; margin-bottom: .3rem; }
.stackview { display: flex; flex-direction: column-reverse; gap: 3px; min-height: 1.4em; }
.stackitem { font: 700 13px ui-monospace, monospace; background: #e8eef3; color: #1d3557; border-radius: 5px;
             padding: .1rem .4rem; text-align: center; }
.status { font-size: .95rem; font-weight: 600; flex: 1; min-width: 160px; }
.status.ok { color: #0a7d33; }
.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 fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// The 8 vertices of a y-monotone polygon, each tagged with which chain (Left or Right) it belongs to.
const V = [
  { x: 150, y: 20,  chain: 'L' },
  { x: 90,  y: 90,  chain: 'L' },
  { x: 230, y: 110, chain: 'R' },
  { x: 60,  y: 160, chain: 'L' },
  { x: 260, y: 180, chain: 'R' },
  { x: 120, y: 230, chain: 'L' },
  { x: 200, y: 250, chain: 'R' },
  { x: 150, y: 300, chain: 'L' },
];
// Vertex indices walked around the polygon boundary, used only for drawing the outline.
const BOUNDARY = [0, 1, 3, 5, 7, 6, 4, 2];
// Vertices sorted top to bottom by y — this is the order the sweep algorithm processes them in.
const ORDER = [0, 1, 2, 3, 4, 5, 6, 7];

function cross(o, a, b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }

// Runs the full stack-sweep once up front so the step count and diagonal total can be checked/reported.
function computeDiagonals() {
  const diagonals = [];
  const stack = [ORDER[0], ORDER[1]];
  for (let j = 2; j < ORDER.length - 1; j++) {
    const vi = ORDER[j];
    const top = stack[stack.length - 1];
    if (V[vi].chain !== V[top].chain) {
      while (stack.length > 1) diagonals.push([vi, stack.pop()]);
      stack.pop();
      stack.push(top);
      stack.push(vi);
    } else {
      let last = stack.pop();
      while (stack.length > 0) {
        const prev = stack[stack.length - 1];
        const turn = cross(V[prev], V[last], V[vi]);
        const isValid = V[vi].chain === 'L' ? turn > 0 : turn < 0;
        if (isValid) { diagonals.push([vi, prev]); last = stack.pop(); } else break;
      }
      stack.push(last);
      stack.push(vi);
    }
  }
  const last = ORDER[ORDER.length - 1];
  for (let k = 1; k < stack.length - 1; k++) diagonals.push([last, stack[k]]);
  return diagonals;
}
const ALL_DIAGONALS = computeDiagonals(); // For n vertices a y-monotone polygon triangulates into exactly n-3 diagonals and n-2 triangles.

const NS = 'http://www.w3.org/2000/svg';
const svg = document.getElementById('stage');
let stepIdx = 0;      // Index into ORDER of the next vertex the sweep will process.
let stack = [];
let drawnDiagonals = [];
let autoTimer = null;

function poly(el, cls) { el.setAttribute('class', cls); return el; }

function render() {
  svg.innerHTML = '';
  const fillPts = BOUNDARY.map(i => V[i].x + ',' + V[i].y).join(' ');
  const fillPoly = document.createElementNS(NS, 'polygon');
  fillPoly.setAttribute('points', fillPts);
  poly(fillPoly, 'poly-fill');
  svg.appendChild(fillPoly);

  const edgePath = document.createElementNS(NS, 'polygon');
  edgePath.setAttribute('points', fillPts);
  poly(edgePath, 'edge');
  svg.appendChild(edgePath);

  for (const [a, b] of drawnDiagonals) {
    const line = document.createElementNS(NS, 'line');
    line.setAttribute('x1', V[a].x); line.setAttribute('y1', V[a].y);
    line.setAttribute('x2', V[b].x); line.setAttribute('y2', V[b].y);
    poly(line, 'diagonal');
    svg.appendChild(line);
  }

  for (let i = 0; i < V.length; i++) {
    const circ = document.createElementNS(NS, 'circle');
    circ.setAttribute('cx', V[i].x); circ.setAttribute('cy', V[i].y); circ.setAttribute('r', 5);
    const seenPos = ORDER.indexOf(i);
    let cls = 'vtx';
    if (seenPos < stepIdx) cls += ' done';
    if (seenPos === stepIdx - 1) cls += ' current';
    poly(circ, cls);
    svg.appendChild(circ);
  }

  const stackview = document.getElementById('stackview');
  stackview.innerHTML = '';
  for (const idx of stack) {
    const d = document.createElement('div');
    d.className = 'stackitem'; d.textContent = 'v' + idx;
    stackview.appendChild(d);
  }
}

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

// One step of the classic stack-sweep triangulation (Garey, Johnson, Preparata, Tarjan 1978).
function doStep() {
  if (stepIdx >= ORDER.length) return false;
  if (stepIdx === 0) { stack = [ORDER[0]]; stepIdx = 1; setStatus(fmt('Pushed v%v% onto the stack (same chain ahead, nothing to cut yet).', { v: ORDER[0] })); render(); return true; }
  if (stepIdx === 1) { stack.push(ORDER[1]); stepIdx = 2; setStatus(fmt('Pushed v%v% onto the stack (same chain ahead, nothing to cut yet).', { v: ORDER[1] })); render(); return true; }

  const vi = ORDER[stepIdx];
  const top = stack[stack.length - 1];
  let addedCount = 0;
  if (stepIdx === ORDER.length - 1) {
    for (let k = 1; k < stack.length - 1; k++) { drawnDiagonals.push([vi, stack[k]]); addedCount++; }
    stack = [stack[0], vi];
    setStatus(fmt('Final vertex: connected to the %n% remaining stack vertex/vertices.', { n: addedCount }), 'ok');
  } else if (V[vi].chain !== V[top].chain) {
    while (stack.length > 1) { drawnDiagonals.push([vi, stack.pop()]); addedCount++; }
    stack.pop();
    stack.push(top);
    stack.push(vi);
    setStatus(fmt('v%v% is on the opposite chain: cut %n% diagonal(s) to every vertex left on the stack.', { v: vi, n: addedCount }));
  } else {
    let last = stack.pop();
    while (stack.length > 0) {
      const prev = stack[stack.length - 1];
      const turn = cross(V[prev], V[last], V[vi]);
      const isValid = V[vi].chain === 'L' ? turn > 0 : turn < 0;
      if (isValid) { drawnDiagonals.push([vi, prev]); last = stack.pop(); addedCount++; } else break;
    }
    stack.push(last);
    stack.push(vi);
    setStatus(addedCount > 0 ? fmt('v%v% is on the same chain: popped and cut %n% diagonal(s) while the turn stayed convex.', { v: vi, n: addedCount }) : fmt('v%v% is on the same chain, but no valid diagonal yet — just pushed.', { v: vi }));
  }
  stepIdx++;
  render();
  if (stepIdx >= ORDER.length) {
    setStatus(fmt('Done — %n% diagonals drawn, splitting the polygon into n-2 triangles.', { n: drawnDiagonals.length }), 'ok');
    document.getElementById('step').disabled = true;
    stopAuto();
  }
  return true;
}

function stopAuto() { if (autoTimer) { clearInterval(autoTimer); autoTimer = null; document.getElementById('auto').textContent = 'Auto-play'; } }

document.getElementById('step').addEventListener('click', doStep);
document.getElementById('auto').addEventListener('click', () => {
  if (autoTimer) { stopAuto(); return; }
  document.getElementById('auto').textContent = 'Stop';
  autoTimer = setInterval(() => { if (!doStep()) stopAuto(); }, 700);
});
document.getElementById('reset').addEventListener('click', () => {
  stopAuto();
  stepIdx = 0; stack = []; drawnDiagonals = [];
  document.getElementById('step').disabled = false;
  setStatus('Press Step to start the sweep.');
  render();
});

render();
Result
Console

Each step does one of two cheap things: push a vertex onto the stack, or pop vertices off it while drawing diagonals, testing only whether a turn is convex. There is no searching for "the next valid cut" — the stack always tells you exactly which diagonal is safe to draw next. That is why the whole pass costs O(n): every vertex is pushed once and popped once.

The Real Complexity

The complexity story here comes in two very different halves.

  • Triangulating a y-monotone polygon is O(n)O(n). Sweep the nn vertices top to bottom, keeping a stack of vertices that still need diagonals. At each step you either push the current vertex or pop a chain of vertices while drawing a diagonal to each — every vertex is pushed and popped exactly once, so the total work is linear (Garey, Johnson, Preparata & Tarjan, 1978).
  • Splitting an arbitrary simple polygon into y-monotone pieces is O(nlog⁡n)O(n \log n). A sweep line finds "merge" and "split" vertices — the places where the boundary folds back on itself — and connects each one to a partner below or above it with a diagonal, using a balanced search structure to find that partner quickly.
  • Putting both phases together still costs O(nlog⁡n)O(n \log n), dominated by the splitting phase — and for decades this was believed to be unavoidable, on par with the Ω(nlog⁡n)\Omega(n \log n) lower bound for comparison-based sorting.
  • Bernard Chazelle broke that ceiling in 1991, showing that any simple polygon can be triangulated in O(n)O(n) time using a far more intricate scheme built on hierarchical partitioning ideas that echo the divide-and-conquer style behind algorithms like Closest Pair of Points — a landmark result, though the constant hidden in the big-O is large enough that the O(nlog⁡n)O(n \log n) sweep is what most real systems actually run.

So the monotone case is not a toy simplification — it is the linear-time core that the general algorithm is built around, whether you stop at O(nlog⁡n)O(n \log n) or push all the way to Chazelle's optimal O(n)O(n).

Where It Matters

Turning a polygon into triangles is one of the most quietly ubiquitous operations in applied computing:

  • Computer graphics: GPUs only know how to rasterize triangles, so every polygon drawn on screen — from a font glyph to a game character's silhouette — gets triangulated first.
  • Finite-element analysis: engineers simulating stress, heat, or airflow break a 2D domain into a triangular mesh, then solve equations on each small piece.
  • Geographic information systems: maps represent countries, lakes, and parcels as polygons; triangulating them enables area computation, terrain modeling, and fast point-in-region queries.
  • Robotics and games: navigation meshes for pathfinding and collision-detection routines both rely on decomposing complex shapes into simple triangular cells.

Any time software needs to reason about an irregular 2D shape numerically, triangulation is usually the first translation step — turning geometry into algebra it can compute with.

Conclusion

A polygon triangulation problem that looks like it should require constant backtracking turns out to have a beautifully local solution: sweep from top to bottom, keep a stack of unresolved vertices, and let convexity tests tell you exactly when to cut a diagonal. That is enough to triangulate any y-monotone shape in O(n)O(n), and with an O(nlog⁡n)O(n \log n) splitting step it handles any simple polygon at all.

The lesson generalizes well beyond geometry: many hard-looking problems become easy once you find the right decomposition — much like how a well-chosen structure sets a hard floor on comparison sorting, or how Longest Common Subsequence falls to the right subproblem split.

Share this article

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

Comments

Loading comments...

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