用叉积符号变化判断凹凸性最直接的方法是遍历所有连续三顶点，计算相邻边的二维叉积（z分量），若出现严格异号则为凹多边形，否则为凸或退化；需处理浮点容差、共线点及顶点顺序未知等情况。
用叉积符号变化判断凹凸性
最直接的方法是遍历所有连续三顶点，计算相邻边的二维叉积（即 z 分量），观察符号是否一致。凸多边形所有顶点处的转向（左转或右转）必须相同；一旦出现符号翻转，说明存在内角 > 180°，即为凹多边形。
关键点在于：对顶点序列 v[0], v[1], ..., v[n-1]（假设按顺时针或逆时针顺序排列且首尾不闭合），对每个 i 计算：
cross = (v[i+1].x - v[i].x) * (v[i+2].y - v[i+1].y) - (v[i+1].y - v[i].y) * (v[i+2].x - v[i+1].x)
注意边界：i 取到 n-3，且需确保输入是简单多边形（无自交）——否则叉积符号变化可能由自交引起，而非凹性。
- 若所有
cross≥ 0（或全部 ≤ 0），且至少有一个非零，则为凸多边形 - 若出现正负混合（严格异号），则为凹多边形
- 允许
cross == 0（三点共线），但不能全为零（退化为线段）
处理顶点顺序未知的情况
实际输入常不保证顶点是顺时针还是逆时针排列。此时不能直接看符号是否“全正”或“全负”，而应先确定整体绕向，再统一判断。
立即学习“C++免费学习笔记（深入）”；
推荐做法：用 std::abs 避免符号误判，改用「是否出现与多数符号相反的叉积」：
- 先计算所有非零叉积，统计正数个数
pos和负数个数neg - 若
pos > 0 && neg > 0，直接判定为凹 - 若仅一侧非零（如
pos > 0 && neg == 0），再检查是否所有非零值同号（可省略，因已满足） - 若大量
cross == 0，需单独剔除共线点再重算，否则可能漏判
绕向本身可用多边形有向面积（shoelace 公式）快速判断，但此处仅需区分符号混合与否，无需显式归一化方向。
浮点精度下的叉积比较陷阱
用 double 或 float 坐标时，cross == 0 几乎不可能成立，直接比较会误判共线或导致符号抖动。
必须引入容差（tolerance）：
- 定义
const double eps = 1e-9; - 判断符号时用：
if (cross > eps) { /* positive */ } else if (cross - 容差不能设太大（如
1e-3），否则小尺度凹陷会被平滑掉 - 若坐标范围很大（如 1e6 量级），建议先归一化或使用相对误差：
std::abs(cross)
完整判断函数的典型结构
一个鲁棒的 is_concave 函数需涵盖顺序、精度、退化三种情况：
- 先验证顶点数
n >= 4（三角形必凸） - 预处理：去重相邻点、剔除连续共线三点（保留首尾）
- 遍历
i = 0到n-3，对每组(i, i+1, i+2)计算带容差的叉积 - 记录第一个非零符号，后续任一叉积符号相反即返回
true（是凹的） - 循环结束未触发，则返回
false（凸或退化）
注意：该方法不适用于自交多边形（如五角星），此时应先调用 is_simple_polygon ——但这属于另一类问题，超出凹性判断范畴。
