半平面
简介
一条在平面上的直线能将平面分成两个部分，半平面就是其中的一半。
表示方法
- 半平面可以表示成这样二维坐标系下的方程形式。
- 半平面可以由一条有向线段的左边（或右边）来表示。
半平面的交
半平面的交集就是由许多半平面组成的交集区域，通常是一个凸多边形。
应用
半平面的交有很多应用，如平面上的线性规划、求多边形的核等。
半平面交求法
常见的半平面求交的方法有增量法、分治法和排序增量法等。
增量法
分治法
排序增量法
我们用一个向量的左侧来描述一个半平面。首先将半平面按照极角排序，极角相同的则只保留最左侧的一个。然后用一个双端队列维护这些半平面：按照顺序插入，在插入半平面之前判断双端队列尾部的两个半平面的交点是否在半平面内，如果不是则删除最后一个半平面；判断双端队列尾部的两个半平面交是否在半平面内，如果不是则删除第一个半平面。插入完毕之后再处理一下双端队列两端多余的半平面，最后求出尾端和顶端的两个半平面的交点即可。
模板代码
// 计算半平面交
void halfplane_intersect(vector<HP> &v, Convex &output) {
sort(v.begin(), v.end(), cmp_HP);
deque<HP> q;
deque<Pt> ans;
q.push_back(v[0]);
int n = v.size();
for (int i = 1; i < n; ++i) {
if (sgn(arg(v[i].t-v[i].s) - arg(v[i-1].t-v[i-1].s)) == 0)
continue;
while (ans.size() > 0 && !satisfy(ans.back(), v[i])) {
ans.pop_back();
q.pop_back();
}
while (ans.size() > 0 && !satisfy(ans.front(), v[i])) {
ans.pop_front();
q.pop_front();
}
ans.push_back(crosspoint(q.back(), v[i]));
q.push_back(v[i]);
}
while (ans.size() > 0 && !satisfy(ans.back(), q.front())) {
ans.pop_back();
q.pop_back();
}
while (ans.size() > 0 && !satisfy(ans.front(), q.back())) {
ans.pop_front();
q.pop_front();
}
ans.push_back(crosspoint(q.back(), q.front()));
output = vector<Pt>(ans.begin(), ans.end());
}
经典题目
- POJ 2540 Hotter Colder
凸多边形交
算法简述
凸多边形的交可以直接通过使用半平面交的算法求得，将所有的凸多边形拆成多个半平面，并求这些半平面的交，就能求得凸多边形的交。
模板代码
// 凸多边形交
void convex_intersection(const Convex &v1, const Convex &v2, Convex &out) {
vector<HP> h;
for (int i = 0, n = v1.size(); i < n; ++i)
h.push_back(HP(v1[i], v1[nxt(i)]));
for (int i = 0, n = v2.size(); i < n; ++i)
h.push_back(HP(v2[i], v2[nxt(i)]));
halfplane_intersect(h, out);
}
多边形的核
平面简单多边形的核是该多边形内部的一个点集，该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。
算法简述
多边形的核可以直接通过求多边形的边所在的直线表示的半平面的交求得。
经典题目
- POJ 1279 Art Gallery
- POJ 2451 Uyuws Concert