17.12 Half-Plane Intersection

Problem

Given a collection of half-planes, compute their common intersection.

A half-plane is one side of a line. For example:

x ≥ 0
y ≥ 0
x + y ≤ 5

each describes an infinite region of the plane.

The goal is to find the region satisfying all constraints simultaneously.

Applications include:

Linear programming in two dimensions
Visibility problems
Motion planning
Convex clipping
Computational optimization
Voronoi diagram construction
Geometric feasibility testing

The intersection may be:

empty
a point
a line segment
an unbounded region
a bounded convex polygon

A correct algorithm must handle all possibilities.

Solution

Represent each constraint as a directed line and keep only the points lying to its left.

After sorting the half-planes by angle, process them using a deque while maintaining the intersection of all constraints seen so far.

This is one of the most elegant applications of geometric predicates and convexity.

The resulting algorithm runs in:

O(n log n)

time.

Understanding Half-Planes

Consider the directed line:

A ----------> B

The corresponding half-plane is:

all points on the left side

Using the orientation test from Section 17.2:

orientation(A, B, P)

A point belongs to the half-plane if:

orientation(A, B, P) >= 0

This representation is extremely convenient because it reduces geometric feasibility to repeated orientation tests.

Representing a Half-Plane

A common implementation stores:

from dataclasses import dataclass
from math import atan2

@dataclass
class HalfPlane:
    a: Point
    b: Point

    @property
    def angle(self):
        return atan2(
            self.b.y - self.a.y,
            self.b.x - self.a.x
        )

Each half-plane is represented by a directed boundary line.

The valid region lies to the left of that line.

Why the Intersection Is Convex

Each half-plane is convex.

If two points satisfy:

x + y ≤ 5

then every point on the segment joining them also satisfies the inequality.

The intersection of convex sets remains convex.

Therefore:

intersection of half-planes

is always convex.

This property makes efficient algorithms possible.

Naive Approach

One possible strategy:

Compute all line intersections.
Test each intersection against every half-plane.
Keep the valid points.
Construct a convex hull.

This works conceptually but requires:

O(n³)

or worse.

The half-plane intersection algorithm exploits convexity to do much better.

Geometric Interpretation

Imagine clipping the plane repeatedly.

Start with:

entire plane

Apply:

x ≥ 0

Result:

right half-plane

Apply:

y ≥ 0

Result:

first quadrant

Apply:

x + y ≤ 5

Result:

bounded triangle

Each new constraint removes a portion of the current feasible region.

The half-plane intersection algorithm performs this clipping efficiently.

Sorting by Angle

The first step is sorting the half-planes.

halfplanes.sort(
    key=lambda hp: hp.angle
)

Why?

Because the boundary directions appear in the same order as the edges of the final convex polygon.

Sorting converts a geometric problem into an ordered sweep around the boundary.

This ordering is the foundation of the deque-based algorithm.

Line Intersections

Two boundary lines define a vertex of the feasible region.

Represent lines parametrically:

P + tr
Q + us

Using the line intersection method from Section 17.3:

def line_intersection(h1, h2):
    ...

The result is a point where the two boundary lines meet.

The algorithm repeatedly computes these intersections.

The Deque Invariant

Maintain a deque of half-planes.

from collections import deque

dq = deque()

Invariant:

all half-planes in dq
have a nonempty intersection

When a new half-plane arrives:

Remove invalid constraints from the back.
Remove invalid constraints from the front.
Insert the new half-plane.

This resembles maintaining a convex hull.

The same geometric idea appears repeatedly throughout computational geometry.

Detecting Invalid Constraints

Suppose:

H1
H2
H3

are consecutive half-planes.

Compute the intersection of:

H1 and H2

If that point lies outside:

H3

then:

H2

can never contribute to the final solution.

Remove it.

Implementation sketch:

while len(dq) >= 2:
    p = line_intersection(
        dq[-2],
        dq[-1]
    )

    if inside(new_halfplane, p):
        break

    dq.pop()

A symmetric test applies at the front.

Parallel Half-Planes

Parallel constraints require special handling.

Consider:

x ≥ 0
x ≥ 1

The second constraint dominates the first.

Only the more restrictive constraint matters.

Now consider:

x ≥ 1
x ≤ 0

These constraints are incompatible.

The feasible region is empty.

Parallel lines are detected using cross products:

cross(direction1, direction2)

A zero result indicates parallelism.

Example

Consider:

x ≥ 0
y ≥ 0
x ≤ 4
y ≤ 3

Geometrically:

+---------+
|         |
|         |
|         |
+---------+

The algorithm processes four half-planes.

The resulting polygon contains:

(0,0)
(4,0)
(4,3)
(0,3)

The feasible region is the rectangle.

Empty Intersection

Consider:

x ≥ 3
x ≤ 1

No point satisfies both.

The deque eventually becomes inconsistent.

The algorithm reports:

empty intersection

Many optimization and feasibility problems reduce to detecting exactly this condition.

Recovering the Polygon

After processing all half-planes, the deque contains the constraints defining the boundary.

Compute intersections between consecutive half-planes:

H0 and H1
H1 and H2
...
Hk and H0

These intersections form the vertices of the feasible polygon.

The vertices appear automatically in counterclockwise order.

No additional sorting is required.

Numerical Robustness

Half-plane intersection is sensitive to floating-point error.

Near-parallel lines produce:

very small denominators

during intersection calculations.

Use:

EPS = 1e-9

for comparisons:

abs(cross) < EPS

Robust computational geometry libraries frequently use exact arithmetic for these predicates.

Applications

Linear Programming in Two Dimensions

Constraints:

ax + by ≤ c

define half-planes.

The feasible region is a half-plane intersection.

Convex Polygon Clipping

Clipping a polygon against a convex window is equivalent to intersecting half-planes.

Visibility Problems

Visibility regions can be represented as half-plane intersections.

Motion Planning

Obstacle constraints generate forbidden half-planes.

Voronoi Diagrams

Voronoi cells are intersections of many half-planes.

Correctness Argument

The half-planes are processed in angular order.

The deque always contains a sequence of constraints whose intersection remains nonempty.

Whenever a newly inserted half-plane invalidates a previously stored boundary, that boundary can no longer appear in the final feasible region and is removed.

Because every constraint is processed exactly once and invalid boundaries are discarded immediately, the final deque contains precisely the half-planes defining the boundary of the feasible region.

Their consecutive intersections therefore form the desired polygon.

Complexity Analysis

Sorting:

O(n log n)

Deque processing:

O(n)

Each half-plane enters and leaves the deque at most once.

Total:

O(n log n)

Space:

O(n)

for the deque and resulting polygon.

Common Pitfalls

Incorrect Line Orientation

The algorithm assumes the feasible side lies to the left of each directed line.

Reversing a line reverses the half-plane.

Ignoring Parallel Constraints

Parallel half-planes require explicit handling.

Failing to do so often causes division-by-zero errors.

Forgetting Final Cleanup

After all half-planes are processed, front and back consistency checks must still be performed.

Using Exact Equality

Floating-point geometry should not rely on:

value == 0

Use an epsilon threshold.

Assuming a Bounded Region

The intersection may be unbounded.

Applications must decide whether this is acceptable.

Discussion

Half-plane intersection occupies an important position in computational geometry because it transforms a set of linear constraints into an explicit geometric object. The algorithm combines ideas that have appeared throughout this chapter: orientation tests, line intersections, convexity, and deque-based maintenance of a geometric invariant. The result is a powerful tool for optimization, clipping, feasibility testing, and the construction of more advanced geometric structures.

The next section builds on these ideas by examining one of the most influential structures in computational geometry: the Voronoi diagram.