521 字
3 分钟
半平面交 (Half-Plane Intersection)

半平面交 (Half-Plane Intersection)#

1. 核心思想#

每条有向直线左侧(或右侧)定义一个半平面。所有半平面的公共交集是一个凸多边形(或空集、无界区域)。 常用 Sutherland-Hodgman / 极角排序增量法 (双端队列) 在 O(Nlog⁡N)O(N \log N) 内求解。

2. 算法步骤#

  1. 极角排序:计算每条有向直线的极角 atan2(dy, dx),按极角排序。同极角平行向量保留最靠内侧的一条。
  2. 双端队列维护:
    • 依次考虑每条直线,若队列尾部两直线的交点在该直线右侧(外侧),弹出队尾。
    • 同样检查队首两直线的交点是否在当前直线外侧,弹出队首。
    • 当前直线入队。
  3. 闭合收尾:用队首约束更新队尾,最后计算相邻直线两两交点即得凸多边形顶点。

3. 核心模板代码 (C++)#

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
struct Point {
double x, y;
Point operator+(const Point &o) const { return {x + o.x, y + o.y}; }
Point operator-(const Point &o) const { return {x - o.x, y - o.y}; }
Point operator*(double k) const { return {x * k, y * k}; }
};
double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
double cross3(Point a, Point b, Point c) {
return cross(b - a, c - a);
}
struct Line {
Point p, v; // p + t * v
double ang;
Line() {}
Line(Point p, Point v) : p(p), v(v), ang(atan2(v.y, v.x)) {}
bool operator<(const Line &o) const { return ang < o.ang; }
};
Point line_intersection(Line a, Line b) {
Point u = a.p - b.p;
double t = cross(b.v, u) / cross(a.v, b.v);
return a.p + a.v * t;
}
bool on_right(Line l, Point p) {
return cross(l.v, p - l.p) < -EPS;
}
vector<Point> half_plane_intersection(vector<Line> &lines) {
sort(lines.begin(), lines.end());
vector<Line> q(lines.size() + 5);
int head = 0, tail = 0;
q[0] = lines[0];
for (int i = 1; i < (int)lines.size(); i++) {
while (head < tail && on_right(lines[i], line_intersection(q[tail], q[tail - 1])))
tail--;
while (head < tail && on_right(lines[i], line_intersection(q[head], q[head + 1])))
head++;
q[++tail] = lines[i];
}
while (head < tail && on_right(q[head], line_intersection(q[tail], q[tail - 1])))
tail--;
while (head < tail && on_right(q[tail], line_intersection(q[head], q[head + 1])))
head++;
if (tail - head + 1 < 3)
return {}; // 空集或退化
vector<Point> poly;
for (int i = head; i < tail; i++)
poly.push_back(line_intersection(q[i], q[i + 1]));
poly.push_back(line_intersection(q[tail], q[head]));
return poly;
}
半平面交 (Half-Plane Intersection)
https://sanzenin.top/posts/obsidian/半平面交/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取