521 字
3 分钟
半平面交 (Half-Plane Intersection)
半平面交 (Half-Plane Intersection)
1. 核心思想
每条有向直线左侧(或右侧)定义一个半平面。所有半平面的公共交集是一个凸多边形(或空集、无界区域)。 常用 Sutherland-Hodgman / 极角排序增量法 (双端队列) 在 内求解。
2. 算法步骤
- 极角排序:计算每条有向直线的极角
atan2(dy, dx),按极角排序。同极角平行向量保留最靠内侧的一条。 - 双端队列维护:
- 依次考虑每条直线,若队列尾部两直线的交点在该直线右侧(外侧),弹出队尾。
- 同样检查队首两直线的交点是否在当前直线外侧,弹出队首。
- 当前直线入队。
- 闭合收尾:用队首约束更新队尾,最后计算相邻直线两两交点即得凸多边形顶点。
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/半平面交/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时