C++半平面交算法怎么求解凸多边形核-C++-PHP中文网

凸多边形核是其内部所有能“看见”整个边界的点构成的区域，等价于按逆时针顺序取每条边左侧半平面（法向量指向内侧）的交集；因凸多边形各边左侧半平面交必非空且为凸集，故可用半平面交求解。

c++半平面交算法怎么求解凸多边形核

什么是凸多边形核，为什么半平面交能求它

凸多边形核是原多边形内部所有能“看见”整个边界（即与任意边界点连线不穿出多边形）的点构成的区域。它等价于：对多边形每条有向边 e_i，取其左侧半平面（即满足该边法向量指向内侧的半空间），所有这些半平面的交集。

注意：必须按逆时针顺序给出多边形顶点，否则边的“左侧”会反向，导致半平面方向错误；核为空时说明多边形无核（比如星形凹多边形），但题设已限定为凸多边形，所以核一定非空且仍是凸多边形（可能退化为点或线段）。

用S&G算法实现半平面交的实操要点

S&G（Shamos & Hoey / O’Rourke 改进版）是处理半平面交最常用、稳定、可手写的方案，核心是用双端队列维护当前有效半平面，并按极角排序后增量裁剪。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

半平面需统一表示为 ax + by + c 形式，其中 <code>(a,b) 是指向多边形内部的法向量
对每条边 v[i]→v[i+1]，计算其左法向量：a = -(y_{i+1} - yi), b = x{i+1} - x_i，再代入任一顶点（如 v[i]）解出 c = -ax_i - by_i
所有半平面按 atan2(b, a) 排序（避免除零和象限判断错误）
排序后需去重：极角差 abs(angle1 - angle2) 且常数项同向的半平面只留更“内侧”的那个（即 <code>c 更小的那个，因 ax+by+c 要求更紧约束）
双端队列裁剪时，每次用队首/队尾两个半平面求交点，检查该交点是否在待加入半平面内；若不在，弹出队首/队尾，重复直到满足

// 示例：从边 p0->p1 构造左半平面
Point p0 = poly[i], p1 = poly[(i+1)%n];
double a = -(p1.y - p0.y);
double b = p1.x - p0.x;
double c = -a * p0.x - b * p0.y;

常见错误：精度、退化与边界处理

半平面交对浮点精度极其敏感，尤其在核接近退化（点、线段）或多个边近似平行时：

不要用 == 判断两半平面平行，改用叉积绝对值 fabs(a1b2 - a2b1)
求两直线交点时，分母为零（平行）必须提前跳过，否则 nan 会污染整个队列
核的顶点可能由两个半平面交点构成，但该点未必落在原始多边形内——S&G本身不保证这点，但因输入是凸多边形且半平面取自其边，只要排序和裁剪无误，结果天然在内部
最终队列中半平面数

要不要用CGAL或Boost.Geometry

可以，但没必要。CGAL 的 halfspace_intersection_3 是为三维设计的，二维需降维包装；Boost.Geometry 没有直接半平面交接口，得靠 intersection 多次裁剪，复杂度高且易累积误差。手写 S&G 约 150 行，逻辑清晰、可控性强，调试时能直接打印每个交点和裁剪步骤——遇到核形状异常，第一反应应是检查法向量方向和极角排序稳定性，而不是换库。

半平面交的“正确性”往往卡在第 3 步：你以为排好序了，其实两条半平面极角相同但常数项冲突，没合并；或者交点计算用了单精度、中间变量未设足够 EPS=1e-9，导致本该保留的顶点被裁掉。