多边形三角测量反射顶点

Question

嗨，我正在尝试执行多边形三角剖分。我了解简单多边形（ Concave 或 Convex ）的剪耳方法。我一直在寻找顶点是否是反射。我在多个地方读到的是关于顺时针和逆时针方向的内容，我无法理解。简而言之，这些方向指的是什么，请给我一些关于检查顶点是否反射的提示。 这是我正在关注的一篇文章的链接：

这是他们使用的公式：

  // Input
    VECTOR a, b, c; // the parts of our triangle.
    // if (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0
    // we are counter-clockwise

我无法理解这里有什么意义。

Answer 1

在大多数情况下，您的输入多边形是一系列连续顶点，它们以逆时针顺序表示您的多边形。这意味着当沿着多边形的边界行走时（如果没有洞），它的内部应该在遍历的每条边的左侧。如果想知道单个顶点是凸的还是反射的（凸表示内角小于 180°，否则为反射），那么有几种方法。最常用的是应用确定性。如果顶点形成左转，则确定给我们的结果是更大的零，这意味着三个连续的顶点 a、b 和 c 在 b 处形成一个凸角；否则小于零。现在公式：(b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0正是如此。它把三个顶点成两个方向矢量：b-a和c-b 那么确定性已经是给定的公式，并告诉我们在 b 上是否发生左转或右转。

编辑，由于评论中的问题：

让我们选择 a=(2 1)、b=(5 4) 和 c=(3 6)。因此，如右图所示的方向由 s=ba=(3 3) 和 t=cb=(-2 2) 给出。现在det(s t)给我们s.x*t.y - t.x*s.y = 3*2 - (-2)*3 = 12 > 0。因此，如果我们站在 a 点并走到 b 点，我们必须左转才能到达 c 点。