耳切算法中顶点凹凸性判断的向量角度计算问题及解决

我正在实现耳切算法，当前阶段需要计算多边形各顶点的角度，以此判断顶点的凸性/凹性，多边形顶点按逆时针排列。

初始代码及问题 #

我编写了以下calcConvexity辅助函数：

void calcConvexity(Node&* prev, Node&* curr, Node&* next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;
        
    // 计算角度（弧度制）
    curr->Angle =
        ((u.x * v.y) - (u.y * v.x))        
        /
        std::sqrt((std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) * 
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f));

    // 转换为角度制
    curr->Angle = (180 / 3.141592653589793238463) * curr->Angle;

    if (curr->Angle < 180.0f)
        curr->isConvex = true; // 顶点为凸
    else
        curr->isConvex = false;
}

但运行后发现计算出的角度不符合预期（本应处于0-360°区间），且所有顶点的isConvex属性都被设为true，即便实际角度大于180°。我尝试调整向量方向、使用GLM库，都没能解决问题。

中间尝试的更新代码 #

之后我调整了代码，改用叉积判断凸凹性，但角度计算仍有问题：

void calcConvexity(Node&* prev, Node&* curr, Node&* next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;

    float CrossProduct = ((u.x * v.y) - (u.y * v.x));
    
    if (CrossProduct < 0)
        curr->isConvex = true; // 顶点为凸
    else
        curr->isConvex = false; // 否则为凹
     
    curr->Angle =
        (CrossProduct)        
        /
        std::sqrt((std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) * 
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f));

    curr->Angle = glm::degrees(std::asin(curr->Angle));
}

最终解决方案 #

最终我找到了解决方法：

• 通过叉积判断顶点的凸凹性
• 改用点积结合acos计算角度，公式为：$\cos(\text{curr->Angle}) = \frac{\mathbf{u} \cdot \mathbf{v}}{|\mathbf{u}| |\mathbf{v}|}$

原问题在于用asin计算角度时，输出范围仅为-90°到90°，无法覆盖0-180°的需求；而acos的输出范围正好是0-180°，符合顶点内角的判断要求。

可行代码如下：

void Graph::calcConvexity(Node*& prev, Node*& curr, Node*& next) {
    glm::vec2 u(0.0f), v(0.0f);
    u.x = curr->x - prev->x;
    u.y = curr->y - prev->y;
    v.x = curr->x - next->x;
    v.y = curr->y - next->y;

    float CrossProduct = ((u.x * v.y) - (u.y * v.x));

    if (CrossProduct < 0)
        curr->isConvex = true; // 顶点为凸
    else
        curr->isConvex = false; // 否则为凹

    float dotProduct = (u.x * v.x) + (u.y * v.y);

    curr->Angle =
        std::acos(dotProduct /
                (std::sqrt(std::pow(u.x, 2.0f) + std::pow(u.y, 2.0f)) *
                std::sqrt(std::pow(v.x, 2.0f) + std::pow(v.y, 2.0f))));

    curr->Angle = glm::degrees(curr->Angle);
}

内容的提问来源于stack exchange，提问作者user18900864