Half-plane intersection

Definition

Half-plane

A half-plane is the point set consisting of a line and one side of that line. If the line is included, it is called a closed half-plane; if the line is not included, it is called an open half-plane.

Its analytic form is generally $Ax+By+C\ge 0$.

In computational geometry, half-planes are represented by vectors. Throughout a problem, we consistently take either the left side or the right side of a vector as the half-plane.

Intersection of half-planes

A half-plane intersection is the intersection of multiple half-planes. Because a half-plane is a point set, the intersection of point sets is also a point set, forming a region in the Cartesian coordinate system.

This is much like an ordinary linear-programming problem: the resulting half-plane intersection is the feasible region in linear programming. In general, a half-plane intersection is bounded, and problems often ask us to compute its area or other quantities.

It can be understood as the intersection of the right sides of all vectors in a set, or as the solution set of the following system of equations.

Kernel of a polygon

If the segment joining a point in a point set to any point on a polygon has no other intersection with the polygon, that point set is called the kernel of the polygon.

If every edge of a polygon is regarded as a vector joined head to tail, the intersection of the half-planes on the interior side of these vectors is the kernel of the polygon.

Method - S&I algorithm

Sorting by polar angle

The C language has a library function called atan2(double y,double x), which returns $\theta\in (-\pi,\pi]$, where $\theta =\arctan \frac{y}{x}$.

Use the vectors directly as the arguments, call this function, and sort by its return value as the key to obtain a new set of edges (vectors).

When sorting, if two collinear vectors point in the same direction, keep the one closer to the feasible region. For example, if two vectors have the same polar angle and we need the half-plane to the left of the vector, we only need to retain the vector on the left. To decide which one to keep, compare an endpoint of one vector with the other and check whether it lies to the left or right.

Maintaining a monotone queue

Because a half-plane intersection is a convex polygon, we need to maintain a convex hull. A newly added vector can affect only the edge added first or the edge added last (the convex hull is connected at this point), so only the front and back elements need to be deleted. This is why a monotone queue is needed.

We traverse the vectors in sorted order and maintain another array of intersection points. When the queue contains more than 2 elements, intersections are formed between them.

For the current vector, if the previous intersection point lies on the opposite side of the half-plane represented by this vector, the preceding edge is meaningless.

As in the figure, suppose that we take the left half-plane of each vector. After sorting by polar angle, the traversal order should be $\vec a\to\vec b\to\vec c$. When $\vec a$ and $\vec b$ enter the queue, they produce a point $D$ in the intersection-point array (the intersection-point array stores the intersection of the vector at each queue index with the preceding vector).

When we next reach $\vec c$, we find that $D$ is to the right of $\vec c$. Because the polar angle of the vector that produced $D$ is necessarily smaller than that of $\vec c$, the vector that produced $D$ (namely $\vec b$) has no effect on the half-plane intersection.

Another possible situation is that, near the end, a newly added vector causes an effect starting from the front of the queue.

Again suppose that we take the left half-plane of each vector. After adding vector $\vec f$, the first intersection point $G$ lies to the right of $\vec f$. Reversing the criterion above shows that we should delete vector $\vec a$, namely the front vector.

Finally, use the front vector to remove redundant vectors at the back. The front vector is constrained by the later vectors, while the back vector is not. They now form a cycle, so the front vector can also constrain the back vector.

Obtaining the half-plane intersection

If the half-plane intersection is a convex $n$-gon, the intersection-point array will contain $n$ points at the end. Connecting them head to tail gives an $n$-gon with a consistent orientation (clockwise or counterclockwise).

We can then use triangulation to calculate its area. (Computing the area is the most basic type of question.)

Sometimes the half-plane intersection does not exist or has area 0, so remember to handle boundary cases.

Notes

When a vector appears that can eject all points in the queue (that is, all points in the queue lie to the right of that vector), we must process the back before the front. Therefore, in the loop, we must process the --r; part before the ++l; part. The reason is as follows.

In the usual case, we append an edge after a queue whose order is $\left\{\vec{u},\vec{v}\right\}$ (the edge is the vector $\vec w$), producing an intersection point $N$ and shrinking the region after $\vec{v}$.

However, every operation is not necessarily ordinary, so it is possible for point $M$ to be pushed out.

If vector $\vec a$ appears and $M$ lies to the right of $\vec a$, then $M$ must leave the queue. If we enumerate from the front with ++l, the range is obviously enlarged. In fact, point $M$ is jointly formed by $\vec u$ and $\vec v$, so we need to consider whether $\vec u$ or $\vec v$ affects the current process. Since the vectors are in counterclockwise order after sorting by polar angle, $\vec v$ has the greater effect.

As shown in the figure, if $M$ is confirmed to be on the right side of $\vec a$, then the effect of $\vec v$ can no longer contribute anything to the answer for the half-plane intersection.

The reason we remove the front is that the current vector imposes a stronger restriction than the front vector. This condition presupposes that there are more than two line segments (vectors) in the queue; otherwise, the situation above can occur.

Therefore, the back must always be removed before the front.

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 angle
  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 vector y vector x is on; put the leftmost first
}

// pnt its(seg a,seg b) computes the intersection of segments a and b
// s[] contains the vectors sorted by polar angle
// q[] is the vector queue
// t[i] is the intersection of s[i-1] and s[i]
// [coding style] the queue range is (l,r]
// compute the half-plane on the left side of each vector
int l = 0, r = 0;
for (int i = 1; i <= n; ++i)
  if (s[i] != s[i - 1]) {
    // check the back first
    while (r - l > 1 && (s[i].b - t[r]) * (s[i].a - t[r]) >
                            eps)  // pop the back if the previous intersection 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 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
  }
while (r - l > 1 &&
       (q[l + 1].b - t[r]) * (q[l + 1].a - t[r]) > eps)  // remove redundant elements
  --r;
t[r + 1] = its(q[l + 1], q[r]);  // compute the new intersection
++r;
// note that ++r cannot be written inside t here...

Exercises

POJ 2451 Uyuw's Concert Pay attention to boundary cases.

POJ 1279 Art Gallery Find the kernel of the polygon.

CQOI2006 Convex Polygon