Half-Plane Intersection
Definition
Half-plane
A line together with one side of it. A half-plane is a point set: the set of points formed by a line and one side of that line. If it contains the line, it is called a closed half-plane; if it does not, an open half-plane.
In analytic form it is usually written \(Ax+By+C\ge 0\).
In computational geometry a half-plane is represented by a vector. Throughout a problem, the half-plane is always the left side of its vector, or always the right side.
Half-plane intersection
The half-plane intersection is the intersection of several half-planes. Half-planes are point sets, and an intersection of point sets is again a point set; in the Cartesian plane it encloses a region.
This looks much like an ordinary linear programming problem: the half-plane intersection is the feasible region of the linear program. The half-plane intersection is usually bounded, and problems often ask for its area or similar quantities.
It can be viewed as the intersection of the right sides of all the vectors in a set of vectors, or as the solution of the system of equations below.
Kernel of a polygon
Take a set of points such that the segment from any of them to any point on the polygon has no other intersection with the polygon. This set is called the kernel of the polygon.
Regard the edges of the polygon as vectors joined head to tail. Each of these vectors has a half-plane on the side of the polygon's interior, and the intersection of these half-planes is the kernel of the polygon.
Solution: the S&I algorithm
Sorting by polar angle
C has a library function atan2(double y,double x) that returns \(\theta\in (-\pi,\pi]\) with \(\theta =\arctan \frac{y}{x}\).
Call this function with each vector as its argument and sort with the return value as the key. This gives a new set of edges (vectors).
If parallel vectors (pointing in the same direction) turn up during the sort, keep the one closer to the feasible region. For example, if two vectors have the same polar angle and we want the half-plane to the left of each vector, we only need to keep the vector on the left. To decide, take the tail or the head of one of the vectors and check whether it lies to the left or to the right of the other vector.
Maintaining the monotonic queue
The half-plane intersection is a convex polygon, so we have to maintain a hull. An edge added later can only affect the edges that were added first or last (the hull is connected at this point), so elements only ever need to be deleted at the front and the back of the queue. That calls for a monotonic queue.
We iterate over the sorted vectors and maintain a second array of intersection points. As soon as the monotonic queue holds 2 elements, they produce an intersection point.
For the current vector, if the previous intersection point lies on the opposite side from the half-plane that this vector represents, the previous edge has become useless.
In the figure above, suppose we take the half-plane to the left of each vector. After sorting by polar angle, the vectors are visited in the order \(\vec a\to\vec b\to\vec c\). When \(\vec a\) and \(\vec b\) are pushed, a point \(D\) appears in the intersection array (the array stores, at each index, the intersection point of the queue's vector at that index with the vector before it).
When we then reach \(\vec c\), we find that \(D\) lies to the right of \(\vec c\). Because the polar angle of the vector that produces \(D\) is always smaller than that of \(\vec c\), the vector that produces \(D\) (that is, \(\vec b\)) no longer affects the half-plane intersection.
Another case can arise near the end: a newly added vector may start to affect the queue from its front.
Again suppose we take the half-plane to the left of each vector. Once the vector \(\vec f\) is added, the first intersection point \(G\) lies to the right of \(\vec f\). Applying the criterion above the other way round, we see that the vector \(\vec a\), the one at the front of the queue, must now be deleted.
Finally, use the vector at the front of the queue to eliminate the redundant vectors at the back. The vector at the front gets constrained by the ones that follow it, but the vectors at the back do not. By now the vectors have closed up into a loop, so the vector at the front can constrain the vectors at the back.
Obtaining the half-plane intersection
If the half-plane intersection is a convex polygon with \(n\) sides, the intersection array ends up holding \(n\) points. Joining each to the next and the last back to the first gives a polygon with \(n\) sides and a consistent orientation (clockwise or counterclockwise).
Its area can now be computed by triangulation. (Computing the area is the most basic way this topic is tested.)
Occasionally the half-plane intersection does not exist or has area 0; pay attention to these boundary cases.
Caveats
When a vector comes along that can pop every point in the queue (that is, all the points in the queue lie to its right), we must handle the back of the queue first and the front afterwards. So in the loop, the --r; part must come before the ++l; part, or the result is wrong. Here is why.
In the general case, appending an edge (the vector \(\vec w\)) to the queue (which holds \(\left\{\vec{u},\vec{v}\right\}\), in this order) produces an intersection point \(N\) and narrows the region beyond \(\vec{v}\).
But not every operation is of the general kind, and the point \(M\) may get "squeezed out".
If a vector \(\vec a\) now comes along such that \(M\) lies to the right of \(\vec a\), then \(M\) has to leave the queue. Popping from the front with ++l here would clearly enlarge the region. In fact, \(M\) is formed by \(\vec u\) and \(\vec v\) together, so we have to ask which of \(\vec u\) and \(\vec v\) affects the construction so far. After sorting by polar angle the vectors are in counterclockwise order, so \(\vec v\) has the greater effect.
As in the figure above, once \(M\) is known to lie to the right of \(\vec a\), the effect of \(\vec v\) contributes nothing to the final half-plane intersection.
The reason for eliminating the front of the queue is that the current vector is more restrictive than the vector at the front. This presupposes that the queue holds more than two segments (vectors); otherwise we end up in the situation above.
So always eliminate at the back first, and only then at the front.
Code: comparison
1 2 3 4 5 6 7 8 | |
Code: incremental construction
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | |
Practice problems
POJ 2451 Uyuw's Concert: watch the boundary
POJ 1279 Art Gallery: find the kernel of a polygon
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: wjy-yy, Ir1d, Xeonacid, 24OI-bot, ouuan, GavinZhengOI, Henry-ZHR, H-J-Granger, sshwy, Enter-tainer, ksyx, Tiphereth-A, CCXXXI, Plastic-time (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.