Polygon Clipping

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.

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">{{hint_para}}</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">{{status_default}}</div>
<div class="btns">
  <button id="toggleCrossings" type="button">{{btn_show_crossings}}</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 .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; }

// Code not found

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.

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)$ time for an $n$-gon against an $m$-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)$ for an $n$-vertex and $m$-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.

"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.

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.