Half-Plane Intersection — Interactive Visualization

Controls

Slow Fast

Active Deque (sorted by angle)

empty

Complexity

Operation	Time
Sort by angle	O(m log m)
Deque sweep	O(m) amort.
Side test	O(1)
Two-line corner	O(1)
Total (standard)	O(m log m)
Incremental clip	O(m²)
Space	O(m)

Press Step to add one half-plane at a time, or Run to animate the whole intersection. Each half-plane shades its allowed side; the green region is the running feasible area.

Half-plane: 0 / 0

Deque size: 0

Pops: 0

Region corners: 0

Status: —

feasible region new half-plane (allowed side) boundary line region corner

Half-Plane Intersection — angle-sort + deque sweep

Operation Log