ix. Half-Plane Intersection

Given $n$ half-planes (each “the left side of a directed line”), find their intersection — a convex region, possibly empty or unbounded.

The algorithm — $O(n\log n)$

1. Sort the half-planes by the angle of their direction vector.
2. Sweep with a deque, maintaining the half-planes that currently contribute to the boundary.
3. Before adding a new half-plane, pop from the back while the intersection point of the last two lies outside the new half-plane; pop from the front similarly.
4. After processing all of them, do a final cleanup pass on both ends (the region wraps around).

struct HP { PD p, d; };                              // point + direction; keep the LEFT side
bool outside(const HP& h, PD q) { return cross(h.d, q - h.p) < -1e-9; }
PD inter(const HP& a, const HP& b) {
    double t = cross(b.d, a.p - b.p) / cross(a.d, b.d);
    return a.p + a.d * t;
}
 
vector<PD> halfPlaneIntersection(vector<HP> h) {
    sort(h.begin(), h.end(), [](const HP& a, const HP& b) {
        if (half(a.d) != half(b.d)) return half(a.d) < half(b.d);
        double c = cross(a.d, b.d);
        return fabs(c) > 1e-9 ? c > 0 : cross(a.d, b.p - a.p) < 0;   // parallel: keep the inner one first
    });
    deque<HP> dq; deque<PD> pts;
    for (const HP& cur : h) {
        while (!pts.empty() && outside(cur, pts.back()))  { pts.pop_back();  dq.pop_back(); }
        while (!pts.empty() && outside(cur, pts.front())) { pts.pop_front(); dq.pop_front(); }
        if (!dq.empty() && fabs(cross(dq.back().d, cur.d)) < 1e-9) {  // exactly the same direction: inter() would divide by 0
            if (!outside(cur, dq.back().p)) continue;                 // old point still satisfies cur: cur is looser, drop it
            dq.pop_back();                                            // old point violates cur: cur is strictly tighter, replace
            if (!pts.empty()) pts.pop_back();
        }
        if (!dq.empty()) pts.push_back(inter(dq.back(), cur));
        dq.push_back(cur);
    }
    while (dq.size() > 2 && outside(dq.front(), pts.back()))  { pts.pop_back();  dq.pop_back(); }
    while (dq.size() > 2 && outside(dq.back(), pts.front())) { pts.pop_front(); dq.pop_front(); }
    if (dq.size() < 3) return {};                    // empty or degenerate
    pts.push_back(inter(dq.back(), dq.front()));
    return vector<PD>(pts.begin(), pts.end());
}

Two details do all the work: the angular sort with an inner/outer tiebreak for parallel half-planes (so a duplicate-direction constraint never produces a spurious intersection point), and the two-sided deque popping.

Proof: half-plane intersection by angular sweep

This is the direct analogue of monotone chain’s stack invariant, with “half-plane” in place of “point” and “angle of the direction vector” in place of “$x$-coordinate”.

Invariant. After processing a prefix of the angularly-sorted half-planes, dq holds exactly the half-planes whose constraint is active on the boundary of their intersection, in angular order, and pts holds the vertices between consecutive active constraints.

Why popping only the two ends suffices. Adding a new half-plane $H$ with the largest angle seen so far: by convexity of an intersection of half-planes, $H$‘s constraint can only invalidate a contiguous run of the current boundary — specifically, the run visible from “outside” $H$ closest to $H$‘s own angular position, which (since everything already in dq has a strictly smaller angle and the region built so far is convex) can only be at the two ends of the deque (the most recently added, highest-angle active constraint, and the very first, lowest-angle one, which is adjacent to $H$ once the sweep wraps around). A constraint buried in the middle of the deque is bounded on both sides by constraints with angles between its own and $H$‘s, so geometrically $H$ cannot cut it off without first cutting off everything between it and one end — the same “no mid-deque invalidation” argument as monotone chain’s stack, and for the same reason: the invalidated region is a contiguous arc in the angularly-ordered boundary.
Parallel ties. Two half-planes with exactly the same direction (possible both from true input duplicates and, as happens whenever two different input polygons happen to share an edge direction, from unrelated half-planes landing on the same angle) bound each other by simple inclusion — whichever is tighter makes the other redundant — and inter between two such parallel lines would divide by zero (cross(a.d,b.d)=0), so they must be special-cased rather than left to the general pop loop. The check decides tightness by testing the old half-plane’s own boundary point against the new constraint: if the old point still satisfies cur (!outside(cur, dq.back().p)), cur is the weaker (or equal) constraint and is dropped; if the old point violates cur, cur cuts deeper and replaces the old one (popping it, and the vertex that was computed from it, before proceeding to the general logic). Since two parallel half-planes have the same angle, the sort’s own tiebreak never needs to separate them for ordering purposes — this replacement happens entirely at sweep time.
Termination. Each half-plane is pushed once and popped at most once over the whole sweep, so the loop is $O(n)$ after an $O(n\log n)$ sort — $O(n\log n)$ total, and the final cleanup pass (popping from the back once more, and closing the polygon with inter(dq.back(), dq.front())) accounts for the wraparound between the highest- and lowest-angle active constraints. $■$

Tested: half-planes taken as the CCW edges of a random convex polygon (p = h[i], d = h[i+1]-h[i], keeping the left/inside) reconstruct exactly that polygon; half-planes from two random convex polygons combined reconstruct their intersection, checked by area against Sutherland-Hodgman clipping run from scratch; and an over-constrained or infeasible set (e.g. two half-planes with incompatible directions) correctly returns empty.

Unbounded regions

If the true intersection is unbounded, the algorithm produces garbage or an empty result (the deque never acquires enough active constraints to close, or closes incorrectly across the “missing” side). The standard fix is to add four half-planes forming a large bounding box before running it. Choose the box large enough that it never clips the real answer — and remember that the reported area then includes the box if the region really was unbounded.

Uses

Problem	Formulation
Intersection of convex polygons	each edge is a half-plane
Feasibility of linear constraints in 2D	is the intersection non-empty
2D linear programming	Seidel’s algorithm is faster ($O(n)$ expected) — 04-linear-programming
Kernel of a polygon (points seeing the whole polygon)	intersect the inner half-planes of all edges
Area visible from a point	half-planes from the blocking edges
Voronoi cell of one site	intersect the perpendicular-bisector half-planes — 20-delaunay-and-voronoi
Region reachable under constraints	direct
Dual of a convex hull	half-plane intersection and convex hull are dual problems

Duality with convex hulls

Under the standard point-line duality $(a,b)\leftrightarrow y=ax-b$ (a point $(a,b)$ dualizes to the line $y=ax-b$, and vice versa, reading the line’s slope as the dual point’s $x$ and minus its intercept as the dual point’s $y$):

• the upper envelope of lines $\leftrightarrow$ the lower convex hull of points;
• half-plane intersection $\leftrightarrow$ convex hull.

Proof: the duality

The dual of line $\ell :y=ax-b$ through point $(x_0,y_0)$ — i.e. $y_0=a{x}_0-b$ — rearranges to $b=a{x}_0-y_0$, which as a function of $a$ with $x_0,y_0$ fixed is itself a line in the dual $(a,b)$-plane. So “a point lies below line $\ell$” ($y_0<a{x}_0-b$, i.e. $b<a{x}_0-y_0$) dualizes to “the dual point of $\ell$ lies below the dual line of $(x_0,y_0)$” — the relation “below” is preserved by the duality. The upper envelope of a set of lines at a given $x_0$ is the line maximizing $a{x}_0-b$ there, i.e. (dualizing) the point maximizing $a{x}_0-b$ over the dual points for that fixed “direction” $x_0$ — exactly the support-function/extreme-point characterization of the lower convex hull (a point is on the lower hull iff it minimizes $y$, equivalently here maximizes $-y=b$-ish quantity, for some direction — the standard hull-via-duality argument). Since every point of the upper envelope corresponds to a hull vertex and vice versa, an $O(n\log n)$ algorithm for one gives one for the other by applying the transform. Intersecting half-planes similarly dualizes to taking a convex hull (each half-plane’s boundary line dualizes to a point, and the intersection’s boundary — itself an envelope of lines — dualizes to that point set’s hull). $■$

So an $O(n\log n)$ hull algorithm gives an $O(n\log n)$ half-plane intersection and vice versa. It also explains why the convex hull trick (an upper envelope of lines) is called that.

When to use something else

Situation	Better tool
Only need feasibility	Seidel’s LP, $O(n)$ expected
Only need one extreme point	2D LP
Clipping a convex polygon by a few lines	Sutherland-Hodgman, $O(nk)$
Voronoi diagram of many sites	Fortune’s algorithm, $O(n\log n)$ total
$n$ small ($\le 100$)	intersect incrementally by clipping; simpler and fast enough

Precision

This is one of the more precision-sensitive routines in geometry: it constructs intersection points and then compares them against other lines. Use long double, keep $\epsilon$ consistent, and prefer the incremental-clipping approach when $n$ is small enough to afford $O(n^2)$.

Exactly-degenerate (zero-area) intersections are the hard case

When the true intersection has zero area — two input regions only touching along an edge or at a point — the algorithm’s behaviour right at the $\epsilon$ boundary is unreliable: a configuration that is “just barely” zero-area can report a spurious positive-area region or an incorrectly empty one, because the same floating-point comparisons that correctly resolve clearly-separated or clearly-overlapping inputs have no slack left when the true answer sits exactly on the decision boundary. If the problem can produce exactly-touching inputs and the distinction matters, treat the zero-area case specially (e.g. check the pairwise touching condition directly) rather than trusting the general sweep’s output region.