Half-plane Intersection

Definition

Half-plane

A half-plane is defined by a line and one of its sides. It is a set of points, specifically the set of points on one side of a line. When the line itself is included, it is called a closed half-plane; when the line is excluded, it is called an open half-plane.

The analytic expression is generally \(Ax+By+C\ge 0\).

In computational geometry, it is represented using vectors, and the entire problem is unified by considering the left or right side of the vector as the half-plane.

Half-plane Intersection

The half-plane intersection refers to the intersection of multiple half-planes. Since a half-plane is a set of points, the intersection of point sets remains a point set. In the Cartesian coordinate system, it forms a region.

This is similar to ordinary linear programming problems, where the half-plane intersection corresponds to the feasible region. Typically, the half-plane intersection is bounded, and problems often involve calculating its area.

It can be interpreted as the intersection of the right sides of each vector in a vector set, or as the solution to the following system of equations:

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

Kernel of a Polygon

If for every point in a set, the line segment connecting it to any point on the polygon does not intersect the polygon elsewhere, then the set is called the kernel of the polygon.

Treating each edge of the polygon as a vector connected end-to-end, the half-plane intersection in the direction of these vectors inside the polygon is the kernel of the polygon.

Solution - S&I Algorithm

Polar Angle Sorting

In C, there is a library function atan2(double y,double x) that returns \(\theta\in (-\pi,\pi]\), where \(\theta =\arctan \frac{y}{x}\).

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

During sorting, if collinear vectors (with the same direction) are encountered, keep the one closer to the feasible region. For example, if two vectors have the same polar angle and we want the left half-plane of the vectors, we only keep the leftmost vector. The method is to take the start or end point of one vector and compare it with the other to check whether it lies on the left or right side.

Maintaining a Monotonic Queue

Since the half-plane intersection is a convex polygon, a convex hull must be maintained. Because newly added vectors can only affect the earliest or latest added edges (when the convex hull is connected), only the head and tail of the queue need to be removed, so a monotonic queue is used.

We iterate through the sorted vectors and maintain another array of intersection points. When there are more than 2 elements in the queue, they will produce intersection points.

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

As shown above, assume the left half-plane of the vectors is taken. After polar angle sorting, the traversal order should be \(\vec a\to\vec b\to\vec c\). When \(\vec a\) and \(\vec b\) are enqueued, a point \(D\) is generated in the intersection array (the intersection array stores the intersection of the vector at the same index in the queue with the previous vector).

When enumerating \(\vec c\), it is found that \(D\) lies on the right side of \(\vec c\). Since the polar angle of the vector that generated \(D\) is smaller than \(\vec c\), the vector that generated \(D\) (i.e., \(\vec b\)) no longer affects the half-plane intersection.

Another possible scenario occurs near the end, where newly added vectors start affecting the head of the queue.

Still assuming the left half-plane of the vectors is taken. After adding vector \(\vec f\), the first intersection point \(G\) lies on the right side of \(\vec f\). Reversing the judgment criteria above, we know that vector \(\vec a\), i.e., the head of the queue, should be removed.

Finally, use the vector at the head to eliminate redundant vectors at the tail. Because the head vector is constrained by later vectors, while the tail vector is not. At this point, they form a closed loop, so the head vector can constrain the tail vector.

Obtaining the Half-plane Intersection

If the half-plane intersection is a convex \(n\)-gon, the intersection array will contain \(n\) points. Connecting them end-to-end forms an \(n\)-gon with a consistent orientation (clockwise or counterclockwise).

At this point, triangulation can be used to calculate the area. (Calculating area is the most basic type of problem.)

Occasionally, the half-plane intersection may not exist or have zero area. Pay attention to boundary cases.

Notes

When a vector appears that can pop all points in the queue (i.e., all points in the queue lie on the right side of this vector), we must process the tail first, then the head. Therefore, in the loop, we enumerate the --r; part first, then the ++l; part, to avoid errors. The reason is as follows.

Generally, when adding an edge (vector \(\vec w\)) to the queue (with queue order \(\left\{\vec{u},\vec{v}\right\}\)), an intersection point \(N\) is generated, reducing the range behind \(\vec{v}\).

However, since each operation is general, there may be cases where point \(M\) is "squeezed out."

If vector \(\vec a\) appears such that \(M\) lies on the right side of \(\vec a\), then \(M\) must be dequeued. If we enumerate ++l from the head at this time, the range is obviously expanded. In fact, point \(M\) is formed by \(\vec u\) and \(\vec v\), so we need to consider whether \(\vec u\) or \(\vec v\) affects the current process. Because after polar angle sorting, the vectors are in counterclockwise order, \(\vec v\) has a greater influence.

As shown in the figure, if \(M\) is confirmed to lie on the right side of \(\vec a\), then \(\vec v\) certainly does not contribute to the half-plane intersection answer.

The reason we remove the head is that the current vector imposes stricter constraints than the head vector, but this condition assumes there are more than two segments (vectors) in the queue; otherwise, the above situation occurs.

Therefore, always remove the tail before removing the head.

Code - Comparison Part

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);  // Calculate polar angle
  if (fabs(t1 - t2) > eps)                      // If polar angles differ
    return t1 < t2;
  return (y.a - x.a) * (y.b - x.a) >
         eps;  // Determine which side of y vector x lies on, keep the leftmost at the leftmost
}

Code - Incremental Part

// pnt its(seg a,seg b) calculates the intersection of segments a and b
// s[] is the polar-angle-sorted vector array
// q[] is the vector queue
// t[i] is the intersection of s[i-1] and s[i]
// 【Coding Style】Queue range is (l,r]
// Seeking the left half-plane of vectors
int l = 0, r = 0;
for (int i = 1; i <= n; ++i)
  if (s[i] != s[i - 1]) {
    // Note: check tail first
    while (r - l > 1 && (s[i].b - t[r]) * (s[i].a - t[r]) >
                            eps)  // If the previous intersection lies on the right side of the vector, pop tail
      --r;
    while (r - l > 1 && (s[i].b - t[l + 2]) * (s[i].a - t[l + 2]) >
                            eps)  // If the first intersection lies on the right side of the vector, pop head
      ++l;
    q[++r] = s[i];
    if (r - l > 1) t[r] = its(q[r], q[r - 1]);  // Calculate new intersection
  }
while (r - l > 1 &&
       (q[l + 1].b - t[r]) * (q[l + 1].a - t[r]) > eps)  // Note: remove redundant elements
  --r;
t[r + 1] = its(q[l + 1], q[r]);  // Calculate new intersection again
++r;
// Note: cannot ++r inside t here...

Practice Problems

POJ 2451 Uyuw's Concert Pay attention to boundaries

POJ 1279 Art Gallery Find the kernel of a polygon

「CQOI2006」Convex Polygons

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用