凹包多边形如何判断内角大于180度？

Question

在处理凹包多边形时，如何准确判断某个顶点的内角大于180度是一个常见技术难题。由于凹多边形存在至少一个内角大于180度的顶点（即“凹点”），直接使用凸包算法会遗漏这些特征。常见的方法是利用向量叉积判断相邻边的转向：若连续三条点构成的两个向量叉积为负，说明该顶点为右转，对应内角大于180度（假设多边形按顺时针方向存储）。但实际应用中，易因点序方向不一致或浮点精度误差导致误判。因此，关键在于正确获取点序方向并结合叉积符号稳定识别凹点。

Answer 1

一、问题背景与基本概念

在计算几何中，处理多边形时常常需要判断其是否为凸多边形或凹多边形。凹多边形至少存在一个内角大于180度的顶点，这类顶点被称为“凹点”。识别凹点是许多应用（如碰撞检测、路径规划、图形简化）中的关键步骤。

常见方法是利用向量叉积来判断三个连续顶点的转向关系。设多边形顶点按顺序存储为 \( P_0, P_1, ..., P_{n-1} \)，对任一顶点 \( P_i \)，构造两个向量：

• \( \vec{v_1} = P_{i-1} \to P_i \)
• \( \vec{v_2} = P_i \to P_{i+1} \)

通过计算叉积 \( \vec{v_1} \times \vec{v_2} \) 的符号可判断转向：若为负，则为右转；若为正，则为左转。假设多边形为顺时针方向存储，右转对应内角大于180度。

二、技术难点分析

尽管叉积法理论清晰，但在实际工程中面临以下挑战：

1. 点序方向未知：输入多边形可能为顺时针或逆时针，直接影响叉积符号解释。
2. 浮点精度误差：当三点几乎共线时，叉积接近零，易因舍入误差导致误判。
3. 边界情况处理：首尾顶点连接时需模运算处理索引越界。
4. 非简单多边形干扰：自相交多边形可能导致逻辑混乱。

因此，稳定识别凹点的前提是先确定整体点序方向，并结合容差机制提升鲁棒性。

三、解决方案设计流程

以下是系统化判断凹点的技术流程：

graph TD
            A[输入多边形顶点序列] --> B{是否闭合?}
            B -- 否 --> C[自动补全首尾]
            B -- 是 --> D[计算多边形有向面积]
            D --> E[判断点序方向: 顺/逆时针]
            E --> F[遍历每个顶点Pi]
            F --> G[构建前后向量v1, v2]
            G --> H[计算叉积cross = v1 × v2]
            H --> I{cross ≈ 0?}
            I -- 是 --> J[视为共线，跳过或标记]
            I -- 否 --> K[根据方向和符号判断凹凸]
            K --> L[输出凹点列表]

四、核心算法实现

以下为Python伪代码示例，展示如何准确识别凹点：

def is_concave_vertex(poly):
    n = len(poly)
    if n < 3:
        return []

    # 计算有向面积以判断点序
    area = 0.0
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        area += (x1 * y2 - x2 * y1)
    clockwise = (area < 0)

    concave_points = []
    eps = 1e-10  # 浮点容差

    for i in range(n):
        prev = poly[(i - 1) % n]
        curr = poly[i]
        next_pt = poly[(i + 1) % n]

        # 构造向量
        v1 = (curr[0] - prev[0], curr[1] - prev[1])
        v2 = (next_pt[0] - curr[0], next_pt[1] - curr[1])

        # 叉积
        cross = v1[0]*v2[1] - v1[1]*v2[0]

        if abs(cross) < eps:
            continue  # 共线，忽略

        # 判断是否为凹点
        if (cross < 0 and clockwise) or (cross > 0 and not clockwise):
            concave_points.append(i)

    return concave_points
    

五、增强策略与工业级优化

问题类型	检测方式	修复策略
点序混乱	有向面积法	统一转为顺时针
浮点误差	设置eps阈值	使用高精度库或投影归一化
数据噪声	曲率变化率检测	预滤波平滑
自相交	线段交叉检测	分割为简单多边形
退化边	边长阈值过滤	合并近似点
大规模数据	空间索引加速	R-tree预处理
实时性要求	增量更新	局部重计算
拓扑错误	欧拉公式验证	重建连通性
坐标系差异	单位一致性检查	标准化变换
内存限制	流式处理	分块加载

六、应用场景扩展

该技术不仅限于二维平面，在三维网格处理中也有延伸应用。例如，在三角网格中识别“凹棱”可用于特征提取或LOD生成。此外，在GIS系统中，行政区划常含复杂凹形结构，精确识别凹点有助于空间分析与可视化优化。

现代图形引擎（如Unity、Unreal）在导航网格（NavMesh）生成时，也依赖此类几何判断进行区域划分。自动驾驶路径规划中，障碍物轮廓的凹点识别直接影响避障策略的安全性与效率。