Introduction

Drag a selection box over a map and only the streets inside it should stay visible. Zoom a camera in a game and only the part of the world inside the view frustum gets drawn. Both are the same question in disguise: given two polygons, what shape is their intersection?

If the two shapes were simple rectangles aligned to the axes, this would be nothing — compare four numbers and you're done. But real shapes are irregular: coastlines, building footprints, camera frustums, a lasso the user just drew freehand. Any edge of one polygon can cross any edge of the other, sometimes many times, and the boundary of the answer is stitched together from pieces of both shapes.

The problem is called polygon clipping, and turning "trace where they overlap" into a precise, always-correct algorithm took computer scientists real effort — mostly in the 1970s and 90s.

Drag the Window

Below is a star-shaped subject polygon and a rectangular clipping window. Drag the window around (or resize it with the handle) and watch the highlighted intersection region recompute itself.

<p class="hint">Drag the red window to move it, or drag its bottom-right handle to resize it. The teal region is the <b>intersection</b> — the part of the star that falls inside the window right now.</p>
<svg id="scene" class="scene" viewBox="0 0 320 260" xmlns="http://www.w3.org/2000/svg">
  <g id="fillLayer"></g>
  <polygon id="subject" class="subject"></polygon>
  <rect id="window" class="window"></rect>
  <g id="crossings"></g>
  <rect id="handle" class="handle" width="14" height="14"></rect>
</svg>
<div class="status" id="status">Drag the window to see the intersection update.</div>
<div class="btns">
  <button id="toggleCrossings" type="button">Show crossings</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 .7rem; line-height: 1.45; }
.scene { width: 100%; max-width: 420px; height: auto; background: #f4f6f8; border: 1px solid #d7dee5;
         border-radius: 10px; touch-action: none; }
.subject { fill: #cdd9e3; stroke: #1d3557; stroke-width: 1.5; }
.window { fill: rgba(230,57,70,.12); stroke: #e63946; stroke-width: 1.5; cursor: move; }
.handle { fill: #e63946; stroke: #fff; stroke-width: 1; cursor: nwse-resize; }
#fillLayer polygon { fill: #2a9d8f; fill-opacity: .55; stroke: #21867a; stroke-width: 1.5; }
.cross-dot { fill: #ffb703; stroke: #7a5200; stroke-width: 1; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; 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.active { background: #ffb703; border-color: #a9760a; color: #3a2a00; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// A 5-point star as the "subject" polygon to be clipped.
function starPolygon(cx, cy, rOuter, rInner, points) {
  const pts = [];
  for (let i = 0; i < points * 2; i++) {
    const r = i % 2 === 0 ? rOuter : rInner;
    const ang = -Math.PI / 2 + (i * Math.PI) / points;
    pts.push({ x: cx + r * Math.cos(ang), y: cy + r * Math.sin(ang) });
  }
  return pts;
}
const SUBJECT = starPolygon(150, 130, 95, 40, 5);

// Sutherland-Hodgman clip against the rectangular (convex) window, edge by edge — the special case of Weiler-Atherton that a convex clip window allows.
function clipPolygon(subject, win) {
  const { x1, y1, x2, y2 } = win;
  const edges = [
    { inside: p => p.x >= x1, cross: (a, b) => ({ x: x1, y: a.y + (b.y - a.y) * (x1 - a.x) / (b.x - a.x) }) },
    { inside: p => p.x <= x2, cross: (a, b) => ({ x: x2, y: a.y + (b.y - a.y) * (x2 - a.x) / (b.x - a.x) }) },
    { inside: p => p.y >= y1, cross: (a, b) => ({ x: a.x + (b.x - a.x) * (y1 - a.y) / (b.y - a.y), y: y1 }) },
    { inside: p => p.y <= y2, cross: (a, b) => ({ x: a.x + (b.x - a.x) * (y2 - a.y) / (b.y - a.y), y: y2 }) },
  ];
  let output = subject;
  for (const edge of edges) {
    const input = output;
    output = [];
    if (input.length === 0) break;
    for (let i = 0; i < input.length; i++) {
      const curr = input[i];
      const prev = input[(i + input.length - 1) % input.length];
      const currIn = edge.inside(curr);
      const prevIn = edge.inside(prev);
      if (currIn) {
        if (!prevIn) output.push(edge.cross(prev, curr));
        output.push(curr);
      } else if (prevIn) {
        output.push(edge.cross(prev, curr));
      }
    }
  }
  return output;
}

// Find every point where a subject edge crosses a window edge, purely for the visualization toggle.
function boundaryCrossings(subject, win) {
  const { x1, y1, x2, y2 } = win;
  const segs = [
    [{ x: x1, y: y1 }, { x: x2, y: y1 }],
    [{ x: x2, y: y1 }, { x: x2, y: y2 }],
    [{ x: x2, y: y2 }, { x: x1, y: y2 }],
    [{ x: x1, y: y2 }, { x: x1, y: y1 }],
  ];
  const pts = [];
  const n = subject.length;
  for (let i = 0; i < n; i++) {
    const a = subject[i], b = subject[(i + 1) % n];
    for (const [c, d] of segs) {
      const hit = segmentIntersect(a, b, c, d);
      if (hit) pts.push(hit);
    }
  }
  return pts;
}
function segmentIntersect(p1, p2, p3, p4) {
  const d = (p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x);
  if (Math.abs(d) < 1e-9) return null;
  const t = ((p3.x - p1.x) * (p4.y - p3.y) - (p3.y - p1.y) * (p4.x - p3.x)) / d;
  const u = ((p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x)) / d;
  if (t < 0 || t > 1 || u < 0 || u > 1) return null;
  return { x: p1.x + t * (p2.x - p1.x), y: p1.y + t * (p2.y - p1.y) };
}

function polygonArea(pts) {
  let a = 0;
  for (let i = 0; i < pts.length; i++) {
    const p = pts[i], q = pts[(i + 1) % pts.length];
    a += p.x * q.y - q.x * p.y;
  }
  return Math.abs(a) / 2;
}

let win = { x1: 90, y1: 60, x2: 230, y2: 190 };
let showCrossings = false;
let drag = null; // Tracks whether we're moving the window or resizing it from its handle.

const svg = document.getElementById('scene');
const subjectEl = document.getElementById('subject');
const windowEl = document.getElementById('window');
const fillLayer = document.getElementById('fillLayer');
const crossingsG = document.getElementById('crossings');
const handleEl = document.getElementById('handle');
const statusEl = document.getElementById('status');
const toggleBtn = document.getElementById('toggleCrossings');

subjectEl.setAttribute('points', SUBJECT.map(p => p.x + ',' + p.y).join(' '));

function render() {
  windowEl.setAttribute('x', win.x1);
  windowEl.setAttribute('y', win.y1);
  windowEl.setAttribute('width', win.x2 - win.x1);
  windowEl.setAttribute('height', win.y2 - win.y1);
  handleEl.setAttribute('x', win.x2 - 7);
  handleEl.setAttribute('y', win.y2 - 7);

  const clipped = clipPolygon(SUBJECT, win);
  fillLayer.innerHTML = '';
  if (clipped.length > 0) {
    const poly = document.createElementNS('http://www.w3.org/2000/svg', 'polygon');
    poly.setAttribute('points', clipped.map(p => p.x + ',' + p.y).join(' '));
    fillLayer.appendChild(poly);
  }

  crossingsG.innerHTML = '';
  if (showCrossings) {
    const pts = boundaryCrossings(SUBJECT, win);
    for (const p of pts) {
      const c = document.createElementNS('http://www.w3.org/2000/svg', 'circle');
      c.setAttribute('cx', p.x); c.setAttribute('cy', p.y); c.setAttribute('r', 3.4);
      c.setAttribute('class', 'cross-dot');
      crossingsG.appendChild(c);
    }
    statusEl.textContent = i18nFmt('%n% boundary crossing point(s) — where the algorithm switches between tracing the star and tracing the window.', { n: pts.length });
  } else {
    const area = polygonArea(clipped);
    const pct = Math.round(100 * area / polygonArea(SUBJECT));
    statusEl.textContent = i18nFmt('Intersection area ≈ %pct%% of the star.', { pct: pct });
  }
}

function svgPoint(evt) {
  const pt = svg.createSVGPoint();
  const t = evt.touches && evt.touches[0] ? evt.touches[0] : evt;
  pt.x = t.clientX; pt.y = t.clientY;
  const loc = pt.matrixTransform(svg.getScreenCTM().inverse());
  return { x: loc.x, y: loc.y };
}

function startDrag(mode) {
  return (evt) => {
    evt.preventDefault();
    const p = svgPoint(evt);
    drag = { mode: mode, startX: p.x, startY: p.y, win: { ...win } };
  };
}
function onMove(evt) {
  if (!drag) return;
  const p = svgPoint(evt);
  const dx = p.x - drag.startX, dy = p.y - drag.startY;
  if (drag.mode === 'move') {
    const w = drag.win.x2 - drag.win.x1, h = drag.win.y2 - drag.win.y1;
    win.x1 = drag.win.x1 + dx; win.x2 = drag.win.x1 + dx + w;
    win.y1 = drag.win.y1 + dy; win.y2 = drag.win.y1 + dy + h;
  } else if (drag.mode === 'resize') {
    win.x2 = Math.max(win.x1 + 20, drag.win.x2 + dx);
    win.y2 = Math.max(win.y1 + 20, drag.win.y2 + dy);
  }
  render();
}
function endDrag() { drag = null; }

windowEl.addEventListener('mousedown', startDrag('move'));
windowEl.addEventListener('touchstart', startDrag('move'), { passive: false });
handleEl.addEventListener('mousedown', (e) => { e.stopPropagation(); startDrag('resize')(e); });
handleEl.addEventListener('touchstart', (e) => { e.stopPropagation(); startDrag('resize')(e); }, { passive: false });
window.addEventListener('mousemove', onMove);
window.addEventListener('touchmove', onMove, { passive: false });
window.addEventListener('mouseup', endDrag);
window.addEventListener('touchend', endDrag);

toggleBtn.addEventListener('click', () => {
  showCrossings = !showCrossings;
  toggleBtn.classList.toggle('active', showCrossings);
  toggleBtn.textContent = showCrossings ? 'Hide crossings' : 'Show crossings';
  render();
});
document.getElementById('reset').addEventListener('click', () => {
  win = { x1: 90, y1: 60, x2: 230, y2: 190 };
  showCrossings = false;
  toggleBtn.classList.remove('active');
  toggleBtn.textContent = 'Show crossings';
  render();
});

render();
Result
Console

The intersection is not just "whichever polygon is smaller" — its outline is stitched from arcs of the subject's boundary and arcs of the window's boundary, joined at the points where the two boundaries cross. Click Show crossings to see exactly those junction points: they are where the algorithm switches from tracing one polygon to tracing the other.

The Real Complexity

Polygon clipping is solved — not open, not NP-hard — but "solved" hides decades of careful casework.

  • Naive idea: just test if each vertex of one polygon lies inside the other. This fails immediately: the intersection can have brand-new vertices that exist in neither original polygon — they only appear at edge crossings.
  • Sutherland-Hodgman (1974) clips a subject polygon against a convex window, one edge of the window at a time, in O(nm)O(nm) time for an nn-gon against an mm-gon. Fast and simple, but it silently breaks if the clipping shape is non-convex.
  • Weiler-Atherton (1977) handles arbitrary (even non-convex, even multi-piece) polygons. The idea: find every point where an edge of the subject crosses an edge of the window, insert those crossing points into both boundaries as shared vertices, and then walk the combined graph — alternating between tracing the subject's boundary and the window's boundary — every time you hit a crossing, you switch which polygon you're following. Follow "entering" crossings to build the intersection, or flip the rule to get the union or the difference instead.
  • Greiner-Hormann (1998) simplifies the bookkeeping further and, crucially, also handles polygons with holes and self-intersections correctly, still without needing a general convexity assumption.
  • Degenerate cases are the real difficulty: an edge that just grazes a vertex, two edges that overlap along a segment, or a crossing that lands exactly on an existing vertex. Production implementations spend most of their code on these edge cases (pun intended), because floating-point arithmetic makes "exactly touching" genuinely ambiguous.

The running time stays polynomial — roughly proportional to the number of crossing points, which is at most O(nm)O(nm) for an nn-vertex and mm-vertex polygon by a counting argument similar to the one behind line segment intersection. The hard part was never the asymptotics; it was getting the casework exactly right.

Where It Matters

"What shape remains after I cut this region with that one" turns out to be everywhere once you start looking:

  • Computer graphics: clipping objects against the camera's view frustum, or against a window's viewport, so nothing off-screen wastes time being rendered.
  • Geographic information systems (GIS): overlaying a zoning boundary on a set of land parcels, or intersecting two map layers, is exactly polygon clipping at country scale.
  • CAD and manufacturing: computing the toolpath left after a milling operation, or the region a laser cutter should trace, both start from clipping one outline against another.
  • Collision and visibility: determining the visible or overlapping region between two shapes is a building block for shadow computation and 2D physics engines.

Every one of these systems, underneath its polish, is running some descendant of Weiler-Atherton or Greiner-Hormann — the same "walk the crossings" idea you just dragged around, related in spirit to how convex hull algorithms sweep a boundary to find structure in a set of points.

Conclusion

Polygon clipping shows a pattern common across computational geometry: the idea — find where the boundaries cross, then walk them — is almost obvious once stated. The difficulty lives entirely in making that idea bulletproof against every awkward, boundary-hugging special case real coordinates throw at it.

Next time a map, a game or a CAD tool shows you exactly the piece of a shape that overlaps another, you're watching a fifty-year-old idea from Weiler and Atherton still doing the quiet work underneath.

Share this article

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

Comments

Loading comments...

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