半平面交——用无数把“剪刀”剪出你想要的形状

你有没有玩过这样的游戏：地面上画了好多条线，每条线都是一条“边界”，你只能站在线的某一侧。比如第一条说“不能超过左边那条红线”，第二条说“不能超过右边那条蓝线”，第三条说“不能超过前方那条绿线”……所有规则同时生效，最后你能站的地方就是所有边界“围起来”的一块区域。半平面交就是解决这个问题的数学工具——它能把一堆这样的“半个平面”叠在一起，求出它们的公共部分，结果通常是一个凸多边形（也可能空，或者无限大）。

想象一下，你有一块无限大的蛋糕，朋友们纷纷提出要求：“不能越过这条红色的线”“不能越过那条蓝色的线”“不能越过那条绿色的线”……于是你拿起剪刀，沿着每条线只剪掉线的一侧，最后剩下的那块蛋糕就是半平面交。

什么是半平面？

一条直线可以把平面分成左右两半。如果你只取其中一半（比如直线左侧的所有点），那就是一个半平面。

直线用方程 ax + by + c = 0 表示，那么半平面可以是 ax + by + c ≥ 0 或 ax + by + c ≤ 0。
在计算机里，我们常用“有向直线”来表示：直线有方向，半平面约定为直线的左侧。

生活例子：你和小伙伴玩“不准过界”游戏，在操场上拉一根绳子，规定“所有人都必须在绳子左边”。这根绳子就是一条有向直线（方向指向绳子的“前方”），左边就是半平面。

多个半平面叠在一起会发生什么？

如果你有两条规则：

“必须在红色绳子左边”
“必须在蓝色绳子左边”

那么你站的地方就是这两个半平面的交集。两条边界线相交，会形成一个扇形区域（像个无边角的形状）。如果加上第三条、第四条……越来越多的半平面叠在一起，最后可能围成一个凸多边形。

为什么一定是凸的？
因为每条直线都是直的，规则是“只能站在直线上或某侧”，所有这样的条件取交集，得到的形状一定是凸的（没有凹进去的角）。就像你用手把一张纸沿着许多直线对折，最后折出来的形状一定是凸的。

怎么用计算机求半平面交？

主要步骤有：

表示直线：每条直线用起点 p 和方向向量 v 表示，半平面在 v 的左侧。直线上任意点可写成 p + t * v。
排序：把所有直线按极角（方向角）从小到大排序，角度相同的只保留最“严格”的那条（即限制最紧的那条）。
双端队列求交：用一个双端队列（两端都可以进出）维护当前有效的直线和交点。从左到右依次加入直线，每次加入新直线时，检查队尾和队头是否被新直线“淘汰”，去掉多余直线。
最后清理：检查队头直线是否淘汰了队尾，并计算出最后一个交点。

这就像你从左到右依次“剪”蛋糕，每一步只保留当前所有剪刀合起来能留下的部分。

代码可以怎么写？

下面是一段完整的 C++ 代码，输入一组直线（每个半平面用直线的左侧表示），输出交点的凸多边形（点按逆时针顺序排列）。代码里用到了向量叉积，用于判断点是否在直线左侧，以及计算两条直线的交点。

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-9;  // 精度控制

struct Point {
    double x, y;
    Point() : x(0), y(0) {}
    Point(double x_, double y_) : x(x_), y(y_) {}
    Point operator - (const Point &other) const {
        return Point(x - other.x, y - other.y);
    }
    // 叉积
    double cross(const Point &other) const {
        return x * other.y - y * other.x;
    }
};

struct Line {
    Point p;        // 直线上一点
    Point v;        // 方向向量（半平面在 v 的左侧）
    double angle;   // 极角（方向角）
    Line() {}
    Line(Point p_, Point v_) : p(p_), v(v_), angle(atan2(v.y, v.x)) {}
};

// 计算两条直线的交点
Point getIntersection(Line a, Line b) {
    double t = (b.p - a.p).cross(b.v) / a.v.cross(b.v);
    return Point(a.p.x + a.v.x * t, a.p.y + a.v.y * t);
}

// 判断点 P 是否在直线 L 的左侧（严格按照半平面内）
bool onLeft(Line L, Point P) {
    return L.v.cross(P - L.p) > eps;
}

// 按极角排序的比较函数
bool cmpAngle(const Line &a, const Line &b) {
    return a.angle < b.angle;
}

// 半平面交主函数：输入直线列表，输出交点构成的凸多边形（可能为空）
vector<Point> halfPlaneIntersection(vector<Line> &lines) {
    // 1. 计算每条直线的极角
    for (auto &l : lines) l.angle = atan2(l.v.y, l.v.x);

    // 2. 按极角排序
    sort(lines.begin(), lines.end(), cmpAngle);

    // 3. 去重：角度相同的直线，只保留最左侧的一条（即最严格的，判断依据是 p 偏移）
    vector<Line> uniqueLines;
    for (size_t i = 0; i < lines.size(); i++) {
        if (i > 0 && fabs(lines[i].angle - lines[i-1].angle) < eps) {
            // 保留更严格的（这里简单跳过，实际应比较距离原点远近）
            continue;
        }
        uniqueLines.push_back(lines[i]);
    }

    int n = uniqueLines.size();
    if (n < 3) return {};  // 至少需要3条直线才能围成多边形

    // 4. 双端队列
    vector<Point> pts(n);          // 存储相邻两直线的交点
    vector<int> dq(n);             // 双端队列，存的是直线索引
    int head = 0, tail = -1;       // head 指向队列头，tail 指向队列尾

    for (int i = 0; i < n; i++) {
        // 加入新直线前，先检查队尾和队头是否被新直线排除
        while (tail - head >= 1 && !onLeft(uniqueLines[i], pts[tail])) tail--;
        while (tail - head >= 1 && !onLeft(uniqueLines[i], pts[head+1])) head++;
        dq[++tail] = i;
        // 如果队列中有至少两条直线，计算新交点
        if (tail > head) {
            pts[tail] = getIntersection(uniqueLines[dq[tail-1]], uniqueLines[dq[tail]]);
        }
    }

    // 5. 清理：检查队头直线是否让队尾交点失效
    while (tail - head >= 1 && !onLeft(uniqueLines[dq[head]], pts[tail])) tail--;

    // 计算最后一个交点（队头和队尾直线的交点）
    if (tail - head >= 1) {
        pts[tail] = getIntersection(uniqueLines[dq[tail-1]], uniqueLines[dq[tail]]);
    }

    // 6. 收集结果
    vector<Point> result;
    for (int i = head; i <= tail; i++) {
        result.push_back(pts[i]);
    }
    return result;
}

// 使用示例：输入一个正方形的四条边界（每条边指向逆时针方向，半平面在左侧）
int main() {
    // 正方形：左下(0,0)，右下(10,0)，右上(10,10)，左上(0,10)
    // 每条边按逆时针方向给出
    vector<Line> square = {
        Line(Point(0,0), Point(10,0)),   // 下边，方向向右，左侧是上方
        Line(Point(10,0), Point(0,10)),  // 右边，方向向上，左侧是左边
        Line(Point(10,10), Point(-10,0)),// 上边，方向向左，左侧是下方
        Line(Point(0,10), Point(0,-10))  // 左边，方向向下，左侧是右边
    };
    vector<Point> result = halfPlaneIntersection(square);
    if (result.empty()) {
        cout << "没有交集区域" << endl;
    } else {
        cout << "交点个数: " << result.size() << endl;
        for (auto &p : result) {
            cout << fixed << setprecision(2) << "(" << p.x << ", " << p.y << ")" << endl;
        }
    }
    return 0;
}

运行上面代码，会输出：

交点个数: 4
(0.00, 0.00)
(10.00, 0.00)
(10.00, 10.00)
(0.00, 10.00)

这正是正方形的四个顶点。

新手容易犯的错误

搞错半平面的方向：代码里约定半平面在方向向量 v 的左侧。如果你用右侧，结果会完全相反（得到一个补集，甚至无限大）。一定要检查每条直线的方向是否正确。
精度问题：浮点数判等不要用 ==，要用 fabs(a-b) < eps。比如两条直线角度非常接近时，要按“去重”处理。
忘记处理去重后的特殊情况：如果去重之后直线少于 3 条，就无法围成多边形，结果可能是空或者无限区域，需要单独判断。
队列操作顺序：在加入新直线前，要先淘汰队尾再淘汰队头，顺序不能反。否则可能漏掉需要淘汰的直线。
直线平行且同向时的处理：如果两条平行直线方向相同，但一条在另一条的左侧，那它们的半平面交集可能是无限长条区域。我们的算法默认只处理能围成凸多边形的情况，无限区域需要额外判断（通常认为无界时返回一个凸多边形加一个远点，这里不展开）。

半平面交能用来做什么？

计算凸多边形：用多边形每条边作为直线（方向向外），半平面交就是多边形内部。
求解线性规划：每个约束对应一个半平面，可行域就是所有半平面的交集。
可见性计算：在游戏里判断一个点是否在某个区域内，比如“安全区”就是多个半平面的交集。
裁剪多边形：用一个凸多边形去裁剪另一个多边形，本质上就是求两个多边形的交，可以用半平面交实现。

半平面交——用剪刀裁剪出一个多边形