Skip to content

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.

A half-plane

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.

\[ \begin{cases} A_1x+B_1y+C_1\ge 0\\ A_2x+B_2y+C_2\ge 0\\ \cdots \end{cases} \]

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.

Monotonic queue

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.

Effect on the front of the queue

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
friend bool operator<(seg x, seg y) {
  db t1 = atan2((x.b - x.a).y, (x.b - x.a).x);
  db t2 = atan2((y.b - y.a).y, (y.b - y.a).x);  // compute the polar angles
  if (fabs(t1 - t2) > eps)                      // if the polar angles differ
    return t1 < t2;
  return (y.a - x.a) * (y.b - x.a) >
         eps;  // determine which side of y the vector x is on; the leftmost one is put first
}
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
// pnt its(seg a,seg b) returns the intersection point of segments a and b
// s[] holds the vectors sorted by polar angle
// q[] is the queue of vectors
// t[i] is the intersection point of q[i-1] and q[i]
// [Coding style] the queue occupies the range (l,r]
// we want the half-plane to the left of each vector
int l = 0, r = 0;
for (int i = 1; i <= n; ++i)
  if (s[i] != s[i - 1]) {
    // check the back of the queue first
    while (r - l > 1 && (s[i].b - t[r]) * (s[i].a - t[r]) >
                            eps)  // pop the back if the previous intersection point is to the right of the vector
      --r;
    while (r - l > 1 && (s[i].b - t[l + 2]) * (s[i].a - t[l + 2]) >
                            eps)  // pop the front if the first intersection point is to the right of the vector
      ++l;
    q[++r] = s[i];
    if (r - l > 1) t[r] = its(q[r], q[r - 1]);  // compute the new intersection point
  }
while (r - l > 1 &&
       (q[l + 1].b - t[r]) * (q[l + 1].a - t[r]) > eps)  // remember to delete the redundant elements
  --r;
t[r + 1] = its(q[l + 1], q[r]);  // then compute one more intersection point
++r;
// careful: the ++r cannot be written inside t[...] here...

Practice problems

POJ 2451 Uyuw's Concert: watch the boundary

POJ 1279 Art Gallery: find the kernel of a polygon

[CQOI2006] Convex Polygon