Introduction

Every linear inequality you have ever written down — ax+by≤cax + by \le c — draws a straight line across the plane and keeps everything on one side of it. That surviving side is a half-plane: an infinite region bounded by one straight edge.

Now stack up many of these constraints at once. A factory that needs 2x+y≤402x + y \le 40 of labor, x+3y≤30x + 3y \le 30 of material, and x,y≥0x, y \ge 0 of common sense is really asking: where do all these half-planes overlap? The answer is always a single convex region — possibly empty, possibly unbounded, but never with a dent in it.

That region is the feasible set behind every linear program. The question this article asks is simple: given nn half-planes, how fast can you actually compute the shape of their intersection?

Shrink the Region

Start with a big bounding square — the "universe" before any constraint is applied. Every time you add a half-plane, the polygon gets clipped against it.

<p class="hint">The teal shape starts as a big square — the whole plane, boxed in for drawing. Each <b>constraint</b> is a straight line with an arrow-free side that must be kept; every click slices the shape down to what still satisfies <b>all</b> constraints so far.</p>
<svg id="canvas" class="canvas" viewBox="0 0 300 300"></svg>
<div class="status" id="status">No constraints yet — the full square is feasible.</div>
<div class="btns">
  <button id="add" type="button">Add constraint</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; }
.canvas { width: 100%; max-width: 300px; height: 260px; background: #f4f6f8; border: 1px solid #cdd9e3;
           border-radius: 8px; display: block; }
.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:disabled { opacity: .5; cursor: default; }

// Half-plane intersection demo: clip a convex polygon against a sequence of
const SIZE = 300;
const MAX_CONSTRAINTS = 7;

// random half-planes, exactly as an incremental (non-angle-sorted) implementation would.
let polygon = [[20, 20], [280, 20], [280, 280], [20, 280]];
let constraints = []; // Starting polygon is a bounding square; each add() clips it against one more half-plane.

// Sutherland-Hodgman clip of a convex polygon against a single half-plane.
// half-plane: points p with (p - point) . normal <= 0 survive
function clipPolygon(poly, point, normal) {
  const inside = (p) => (p[0] - point[0]) * normal[0] + (p[1] - point[1]) * normal[1] <= 1e-9;
  const intersect = (a, b) => {
    const da = (a[0] - point[0]) * normal[0] + (a[1] - point[1]) * normal[1];
    const db = (b[0] - point[0]) * normal[0] + (b[1] - point[1]) * normal[1];
    const t = da / (da - db);
    return [a[0] + t * (b[0] - a[0]), a[1] + t * (b[1] - a[1])];
  };
  const out = [];
  for (let i = 0; i < poly.length; i++) {
    const cur = poly[i], nxt = poly[(i + 1) % poly.length];
    const curIn = inside(cur), nxtIn = inside(nxt);
    if (curIn) out.push(cur);
    if (curIn !== nxtIn) out.push(intersect(cur, nxt));
  }
  return out;
}

// Pick a random line direction and offset from the center, so each constraint visibly cuts a chunk off.
function randomHalfPlane() {
  const angle = Math.random() * Math.PI * 2;
  const normal = [Math.cos(angle), Math.sin(angle)];
  const cx = SIZE / 2, cy = SIZE / 2;
  const r = 60 + Math.random() * 90;
  const point = [cx + normal[0] * r, cy + normal[1] * r];
  return { point, normal };
}

function polygonArea(poly) {
  let a = 0;
  for (let i = 0; i < poly.length; i++) {
    const [x1, y1] = poly[i], [x2, y2] = poly[(i + 1) % poly.length];
    a += x1 * y2 - x2 * y1;
  }
  return Math.abs(a) / 2;
}

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

function render() {
  const svg = document.getElementById('canvas');
  svg.innerHTML = '';
  const ns = 'http://www.w3.org/2000/svg';

  // Draw each constraint's boundary line as a long dashed segment across the canvas.
  for (const cst of constraints) {
    const { point, normal } = cst;
    const dir = [-normal[1], normal[0]];
    const p1 = [point[0] - dir[0] * 400, point[1] - dir[1] * 400];
    const p2 = [point[0] + dir[0] * 400, point[1] + dir[1] * 400];
    const line = document.createElementNS(ns, 'line');
    line.setAttribute('x1', p1[0]); line.setAttribute('y1', p1[1]);
    line.setAttribute('x2', p2[0]); line.setAttribute('y2', p2[1]);
    line.setAttribute('stroke', '#c9ccd1');
    line.setAttribute('stroke-width', '1.5');
    line.setAttribute('stroke-dasharray', '4 3');
    svg.appendChild(line);
  }

  if (polygon.length > 0) {
    const pts = polygon.map((p) => p.join(',')).join(' ');
    const poly = document.createElementNS(ns, 'polygon');
    poly.setAttribute('points', pts);
    poly.setAttribute('fill', '#a8dadc');
    poly.setAttribute('fill-opacity', '0.55');
    poly.setAttribute('stroke', '#1d3557');
    poly.setAttribute('stroke-width', '2');
    svg.appendChild(poly);
  }
}

function updateStatus() {
  const s = document.getElementById('status');
  if (constraints.length === 0) {
    s.textContent = 'No constraints yet — the full square is feasible.';
    return;
  }
  if (polygon.length === 0) {
    s.textContent = 'The constraints are contradictory — nothing satisfies them all.';
    return;
  }
  s.textContent = fmt('%n% constraint(s) applied — the feasible region has %edges% edges and area %area%.', {
    n: constraints.length,
    edges: polygon.length,
    area: Math.round(polygonArea(polygon)),
  });
}

function addConstraint() {
  if (constraints.length >= MAX_CONSTRAINTS) return;
  const hp = randomHalfPlane();
  constraints.push(hp);
  polygon = clipPolygon(polygon, hp.point, hp.normal);
  render();
  updateStatus();
  if (constraints.length >= MAX_CONSTRAINTS) document.getElementById('add').disabled = true;
  console.log('Constraints so far:', constraints.length, '| polygon edges:', polygon.length);
}

function reset() {
  polygon = [[20, 20], [280, 20], [280, 280], [20, 280]];
  constraints = [];
  document.getElementById('add').disabled = false;
  render();
  updateStatus();
}

document.getElementById('add').addEventListener('click', addConstraint);
document.getElementById('reset').addEventListener('click', reset);
render();
updateStatus();
Result
Console

Click Add constraint to throw in a fresh random half-plane; the demo clips the current polygon against it edge by edge, in the same way the sweep does it for real. Click Reset to start over from the full square. Watch how the region only ever shrinks and stays convex — it can never grow a notch or split in two.

The Real Complexity

The naive approach clips the current polygon against each new half-plane, one at a time. Clipping a polygon with kk edges against one half-plane costs O(k)O(k), and after nn constraints the polygon can have up to O(n)O(n) edges — so the total cost of adding them in an arbitrary order is O(n2)O(n^2) in the worst case.

The fix is to stop adding constraints in a random order. Every half-plane's boundary line has a direction: sort the nn half-planes by the angle of that boundary (an O(nlog⁡n)O(n \log n) sort), then sweep through them in angular order, maintaining the current intersection as a deque of edges. Because consecutive half-planes in angle order interact predictably with the growing hull, each half-plane gets pushed and popped from the deque at most once — so the whole sweep after the sort is only O(n)O(n).

  • Sort by angle: O(nlog⁡n)O(n \log n), dominates the whole algorithm.
  • Deque sweep: each half-plane inserted once, popped at most a constant number of times — amortized O(1)O(1) per half-plane.
  • Total: O(nlog⁡n)O(n \log n), matching the lower bound for the problem (you must at least sort, since the output edges appear in angular order around the region).

This is the same "sort first, then sweep linearly" pattern that powers convex hull algorithms — angular order is doing the heavy lifting in both.

Where It Matters

Any time a system is described by "all of these linear limits must hold simultaneously," you are looking at a half-plane intersection in disguise:

  • Linear programming: the feasible region of an LP is exactly the intersection of its constraint half-planes (in 2D) or half-spaces (in higher dimensions); the optimum sits at one of its corners.
  • Robot motion and visibility: computing the region a robot can safely occupy, or the area visible from a point among straight obstacles, reduces to intersecting half-planes.
  • Kinetic and dynamic geometry: as constraints move over time, maintaining their intersection incrementally is a core building block for real-time planning.
  • Computer graphics: clipping a polygon against a viewing frustum or a clip window is literally intersecting it with a handful of half-planes.

Learn this one sweep and you have the mechanism behind the corner of every linear program and the silhouette behind every convex clipping window.

Conclusion

Half-plane intersection looks, at first glance, like it should cost you O(n2)O(n^2): clip a growing polygon against nn constraints, one at a time, and the edges pile up. But order the half-planes by the angle of their boundary first, sweep once with a deque, and the whole computation collapses to O(nlog⁡n)O(n \log n) — as fast as sorting itself.

It is a small, elegant reminder that in computational geometry the hard part is rarely the geometry: it is finding the right order to process things in. Get the order right, and a quadratic-looking problem turns linearithmic — the same trick that makes convex hull construction fast.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/half-plane-intersection/Content licensed under CC BY-NC 4.0.