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) < -EPS; }
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) > EPS ? c > 0 : cross(a.d, b.p - a.p) < 0;   // keep the inner one
    });
    // remove duplicates by angle, keeping the most restrictive
    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()) pts.push_back(inter(dq.back(), cur));
        dq.push_back(cur);
    }
    while (!pts.empty() && outside(dq.front(), pts.back())) { pts.pop_back(); dq.pop_back(); }
    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, and the two-sided deque popping.

Unbounded regions

If the true intersection is unbounded, the algorithm produces garbage or an empty result. 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)
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
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$:

• the upper envelope of lines ↔ the lower convex hull of points;
• half-plane intersection ↔ convex 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)$.

See also: Seidel’s LP Algorithm · Convex Hull · Voronoi Diagram