凸多边形核是其内部所有能“看见”整个边界的点构成的区域，等价于按逆时针顺序取每条边左侧半平面（法向量指向内侧）的交集；因凸多边形各边左侧半平面交必非空且为凸集，故可用半平面交求解。
什么是凸多边形核，为什么半平面交能求它
凸多边形核是原多边形内部所有能“看见”整个边界（即与任意边界点连线不穿出多边形）的点构成的区域。它等价于：对多边形每条有向边 e_i，取其左侧半平面（即满足该边法向量指向内侧的半空间），所有这些半平面的交集。
注意：必须按逆时针顺序给出多边形顶点，否则边的“左侧”会反向，导致半平面方向错误；核为空时说明多边形无核（比如星形凹多边形），但题设已限定为凸多边形，所以核一定非空且仍是凸多边形（可能退化为点或线段）。
用S&G算法实现半平面交的实操要点
S&G（Shamos & Hoey / O’Rourke 改进版）是处理半平面交最常用、稳定、可手写的方案，核心是用双端队列维护当前有效半平面，并按极角排序后增量裁剪。
- 半平面需统一表示为
ax + by + c <= 0形式，其中(a,b)是指向多边形内部的法向量 - 对每条边
v[i]→v[i+1]，计算其左法向量：a = -(y_{i+1} - y<em>i)</em>,b = x{i+1} - x_i，再代入任一顶点（如v[i]）解出c = -a<em>x_i - b</em>y_i - 所有半平面按
atan2(b, a)排序（避免除零和象限判断错误） - 排序后需去重：极角差
abs(angle1 - angle2) < EPS且常数项同向的半平面只留更“内侧”的那个（即c更小的那个，因ax+by+c<=0要求更紧约束） - 双端队列裁剪时，每次用队首/队尾两个半平面求交点，检查该交点是否在待加入半平面内；若不在，弹出队首/队尾，重复直到满足
// 示例：从边 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;
常见错误：精度、退化与边界处理
半平面交对浮点精度极其敏感，尤其在核接近退化（点、线段）或多个边近似平行时：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 不要用
==判断两半平面平行，改用叉积绝对值fabs(a1<em>b2 - a2</em>b1) < EPS - 求两直线交点时，分母为零（平行）必须提前跳过，否则
nan会污染整个队列 - 核的顶点可能由两个半平面交点构成，但该点未必落在原始多边形内——S&G本身不保证这点，但因输入是凸多边形且半平面取自其边，只要排序和裁剪无误，结果天然在内部
- 最终队列中半平面数 < 3 时，核为空（但凸多边形不会发生）；恰好为 3 时核是三角形；需手动闭合：取相邻半平面交点作为顶点，顺序与原多边形一致
要不要用CGAL或Boost.Geometry
可以，但没必要。CGAL 的 halfspace_intersection_3 是为三维设计的，二维需降维包装；Boost.Geometry 没有直接半平面交接口，得靠 intersection 多次裁剪，复杂度高且易累积误差。手写 S&G 约 150 行，逻辑清晰、可控性强，调试时能直接打印每个交点和裁剪步骤——遇到核形状异常，第一反应应是检查法向量方向和极角排序稳定性，而不是换库。
半平面交的“正确性”往往卡在第 3 步：你以为排好序了，其实两条半平面极角相同但常数项冲突，没合并；或者交点计算用了单精度、中间变量未设足够 EPS=1e-9，导致本该保留的顶点被裁掉。
