半平面交

定义

半平面：直线 $A x + B y + C \geq 0$ 及其一侧的点集。多个半平面的交集称为 半平面交。

多边形的核：多边形内部点集，满足该点与多边形上任一点连线都在多边形内。其等于每条边所在直线内侧半平面的交。

S&I 算法

极角排序后双端队列维护凸壳， $O (n lo g n)$ 。

struct Seg {
  Point a, b;
  double ang;
  Seg(Point a = {}, Point b = {}) : a(a), b(b) { ang = atan2((b - a).y, (b - a).x); }
  bool operator<(const Seg &s) const {
    if (fabs(ang - s.ang) > 1e-9) return ang < s.ang;
    return (s.a - a).cross(s.b - a) > 1e-9;  // 靠左优先
  }
};
 
Point inter(Seg p, Seg q) { /* 求两直线交点 */ }
 
vector<Point> halfPlane(vector<Seg> s) {
  sort(s.begin(), s.end());
  deque<Point> pt;
  deque<Seg> dq;
  for (auto &x : s) {
    while (pt.size() && (x.b - pt.back()).cross(x.a - pt.back()) > 1e-9)
      pt.pop_back(), dq.pop_back();
    while (pt.size() && (x.b - pt.front()).cross(x.a - pt.front()) > 1e-9)
      pt.pop_front(), dq.pop_front();
    dq.push_back(x);
    if (dq.size() > 1) pt.push_back(inter(dq[dq.size() - 2], dq.back()));
  }
  while (pt.size() && (dq.front().b - pt.back()).cross(dq.front().a - pt.back()) > 1e-9)
    pt.pop_back(), dq.pop_back();
  if (dq.size() > 2) pt.push_back(inter(dq.front(), dq.back()));
  return {pt.begin(), pt.end()};
}

算法流程详解：

极角排序：每条半平面（有向直线）按极角排序。极角相同者只保留最靠左（约束最强）的一条
双端队列维护凸壳：
- 依次加入排序后的半平面
- 加入前检查队尾交点是否在新半平面右侧（不满足则弹出队尾）
- 再检查队首交点是否在新半平面右侧（不满足则弹出队首）
- 将新半平面加入队尾，计算新队尾与前一队尾的交点
首尾收束：用队首半平面约束队尾多余交点，用队尾半平面约束队首多余交点
最后队列中的半平面两两相交得到凸多边形

!
!
!
!
!
!
!

核心步骤

极角排序：atan2 求极角，同向保留最靠左
双端队列维护：先弹队尾（上一交点在新向量右侧），再弹队首
首尾收束：用队首向量排除队尾多余向量

平行线处理

当两条半平面平行时，它们的极角相同。排序后相邻的平行半平面，应保留约束更强（更靠左）的那条：

if (fabs(s.ang - dq.back().ang) < 1e-9) {
  if ((s.b - dq.back().a).cross(s.a - dq.back().a) > 1e-9) {
    dq.pop_back(); // 新半平面更靠左，替换
    if (pt.size()) pt.pop_back();
  } else continue; // 新半平面无贡献
}

此外，若某半平面将队列中所有半平面都”切”掉，则交集为空（无解）。

应用

多边形的核（能看到多边形所有位置的区域）
线性规划（每个约束是一个半平面，求可行域）
求两个凸多边形的交

题目	说明
P4196 凸多边形	半平面交模板
路径D-DSA算法刷题	更多练习

相关笔记：二维几何基础, 凸包

多平台练习

RootStack

探索

半平面交

半平面交

定义

S&I 算法

核心步骤

平行线处理

应用

相关链接

多平台练习

关系图谱

目录

反向链接