如何计算两个向量的角度以确定耳朵剪切算法中的顶点凹度

Question

我正在尝试实现这个耳朵裁剪算法（来自伪代码）这里目前在算法中我试图计算多边形中每个顶点的角度。我还了解了如何在这里用向量计算角度：here这样我还可以确定凸度/凹度。我的顶点也是逆时针顺序的。

这是我编写的一个辅助函数，用于帮助计算每个顶点的角度：

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;
        
        // Calculating angle (in radians)
    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));

        // Convert to degrees
    curr->Angle = (180 / 3.141592653589793238463) * curr->Angle;

    if (curr->Angle < 180.0f)
        curr->isConvex = true; // The vertex is convex
    else
        curr->isConvex = false;
}

我原以为大部分角度都会在 0 到 360 之间，但事实并非如此。我不确定我需要进行哪些进一步的计算或更正。另外，在节点类中，我有一个名为 isConvex 的布尔属性。我知道发生了错误，因为每个顶点的 isConvex 属性都设置为 true，即使度数大于 180.0f（在下面的示例中）。

这也是一个实际的示例输出： （蓝色箭头应该面向节点，我只是无法更新此处的图片） 以及每个节点的 isConvex 值： 和角度：

我尝试过面对不同方向的向量以及使用 GLM 库进行向量运算。

如果我提供的任何内容令人困惑，我深表歉意，这是我第一次搞乱计算几何。所以我只是想知道我的 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;

    float CrossProduct = ((u.x * v.y) - (u.y * v.x));
    
    if (CrossProduct < 0)
        curr->isConvex = true; // The vertex is convex
    else
        curr->isConvex = false; // Otherwise concave
     
    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));
}

所以我想出的解决方案是这样的： 我使用叉积来确定凸度，然后使用略有不同的角度公式：cos(curr->Angle) = (u.b) / (|u||v|) 我的主要问题是带 sin 的公式输出在 -90 到 90 之间，而带 cos 的公式输出在 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; // The vertex is convex
    else
        curr->isConvex = false; // Otherwise concave

    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);
}

Answer 1

获取角度最安全的方法是使用函数

atan2

，它返回四个象限上的值（通常在

(-π, π]

中）。

使用复数表示法，向量 u 到 v 形成的角度由 u*v 的参数给出，其中 * 表示共轭。

无论如何，我想为了确定三角测量的凹/凸，考虑三角形的有符号面积（两条边的叉积）而不是角度就足够了。这告诉你三角形是否是顺时针的。

Answer 2

curr->Angle

似乎从

sin(Angle)

到

u

设置为

v

。因此，凹/凸由

((u.x * v.y) - (u.y * v.x))

的符号决定，因为分母始终为正。

特别是，如果从尾部到头部穿过矢量

u

，多边形的内部位于右侧，则

((u.x * v.y) - (u.y * v.x))

的正号对应于凸角。

Answer 3

更好的解决方案是计算角点到边缘之间的叉积并查看它的符号。 例如，我们希望知道在 p1 处哪里转弯，那么我们必须计算：

a = p1 - p0 b = p2 - p1

查找叉积

交叉 = a.x * b.y - a.y * b.x

如果 cross == 0 则不转弯 // 180 度

如果交叉< 0 then turn clockwise

如果 cross > 0 则逆时针旋转

请记住，多边形点的顺序很重要。 根据它们是顺时针还是逆时针方向，规则可以颠倒。