C++半平面交算法详解（从零开始掌握计算几何核心技巧）

什么是半平面交？

当我们有多个半平面时，它们的公共交集区域就叫做半平面交。这个交集可能是空集、一个点、一条线段、一个多边形，甚至是一个无界区域。我们的目标就是通过算法求出这个交集区域的边界顶点。

算法思路概述

实现半平面交实现最常用的方法是使用双端队列（deque）进行增量构造。基本步骤如下：

1. 将所有半平面按极角排序（避免平行线干扰）；
2. 用双端队列维护当前交集的边界；
3. 依次加入每个半平面，并检查队首/队尾是否仍属于新交集；
4. 最后处理队列首尾可能存在的冗余。

C++ 实现细节

为了实现该算法，我们需要定义点（Point）和直线（Line）结构体，并实现一些辅助函数，如叉积、判断点是否在半平面内等。

#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <deque>const double eps = 1e-9;struct Point {    double x, y;    Point() {}    Point(double x, double y) : x(x), y(y) {}    Point operator - (const Point& b) const {        return Point(x - b.x, y - b.y);    }    double cross(const Point& b) const {        return x * b.y - y * b.x;    }};struct Line {    Point p, v; // p 是直线上一点，v 是方向向量    double ang; // 极角    Line() {}    Line(Point p, Point v) : p(p), v(v) {        ang = atan2(v.y, v.x);    }    bool operator < (const Line& L) const {        return ang < L.ang;    }    // 判断点 a 是否在半平面左侧（含边界）    bool isLeft(const Point& a) const {        return v.cross(a - p) > -eps;    }};// 求两直线交点Point intersect(const Line& a, const Line& b) {    Point u = a.p - b.p;    double t = b.v.cross(u) / a.v.cross(b.v);    return Point(a.p.x + a.v.x * t, a.p.y + a.v.y * t);}// 半平面交主函数std::vector<Point> halfPlaneIntersection(std::vector<Line>& lines) {    std::sort(lines.begin(), lines.end());    std::deque<Line> dq;    std::deque<Point> pts;    for (const auto& L : lines) {        // 移除队尾无效半平面        while (pts.size() >= 2 && !L.isLeft(pts.back())) {            dq.pop_back();            pts.pop_back();        }        // 移除队首无效半平面        while (pts.size() >= 2 && !L.isLeft(pts.front())) {            dq.pop_front();            pts.pop_front();        }        if (dq.empty()) {            dq.push_back(L);        } else {            // 处理平行线情况            if (fabs(dq.back().v.cross(L.v)) < eps) {                if (L.isLeft(dq.back().p))                    dq.pop_back();                else                    continue;            }            dq.push_back(L);            pts.push_back(intersect(dq[dq.size()-2], dq.back()));        }    }    // 处理首尾闭合    while (pts.size() >= 2 && !dq.front().isLeft(pts.back())) {        dq.pop_back();        pts.pop_back();    }    while (pts.size() >= 2 && !dq.back().isLeft(pts.front())) {        dq.pop_front();        pts.pop_front();    }    if (dq.size() <= 2) return {};    pts.push_back(intersect(dq.front(), dq.back()));    return std::vector<Point>(pts.begin(), pts.end());}

使用示例

下面是一个简单的使用例子，构建一个正方形区域的半平面交：

int main() {    std::vector<Line> lines;    // 添加四个边界半平面（构成 [0,1]×[0,1] 正方形）    lines.emplace_back(Point(0, 0), Point(1, 0));   // 下边界 y ≥ 0    lines.emplace_back(Point(1, 0), Point(0, 1));   // 右边界 x ≤ 1    lines.emplace_back(Point(1, 1), Point(-1, 0));  // 上边界 y ≤ 1    lines.emplace_back(Point(0, 1), Point(0, -1));  // 左边界 x ≥ 0    auto res = halfPlaneIntersection(lines);    if (res.empty()) {        std::cout << "交集为空！\n";    } else {        std::cout << "交集顶点数: " << res.size() << "\n";        for (auto& p : res) {            std::cout << "(" << p.x << ", " << p.y << ")\n";        }    }    return 0;}

常见问题与优化

在实际应用中，你可能会遇到浮点精度问题、平行线处理、退化情况（如交集为线段或点）等挑战。建议：

• 使用合适的 eps 值（如 1e-9）；
• 对输入半平面做预处理，去除冗余或矛盾约束；
• 若需更高精度，可考虑使用分数类或任意精度库。

结语

通过本教程，你应该已经掌握了C++几何编程中半平面交算法的基本原理与实现方法。无论是参加算法竞赛还是开发图形软件，这项技能都非常实用。继续练习不同输入场景，你将更加熟练地运用这一强大的计算几何算法工具！