polygon - 剪耳有问题

Question

我遇到的问题正在出现，因为我无法识别三角形凹陷的耳朵和实际上应该被切掉的耳朵。

如何区分凸三角形和凹三角形？

Answer 1

三角形不能是凹的。你的意思是你的网格是凹的？

---

我没有意识到你在谈论一种特殊的技术。在做了一些研究之后，我想我理解你的问题足以尝试回答。

假设您以逆时针顺序遍历多边形的顶点。如果我们按此顺序遍历它们，多边形的主体将始终位于左侧。我们正在考虑三个顶点：A、B和C。想象一下，我们从A到B射出一条射线。如果C位于该射线的左侧，则这是一个结构良好的三角形，它是多边形的一部分。如果C在该射线的右侧，则它表示负空间。

好的，让我们创建向量v（即A → B）和w（即B → C）。另外，让我们构造v'，它是v但逆时针旋转了 90 度。v' = < -v[y], v[x] >

为了找出C是在v的左边还是右边，我们只需要测量v'和w之间的角度。如果它在 (0, 90) 或 (270, 360) 之内，那么它在左边。如果它在 (90, 270) 之内，那么它在右边。这很方便，因为这分别对应于 cos(Θ) > 0 和 cos(Θ) < 0 的位置。因此，如果 cos(Θ) > 0，则 C 在左侧，如果 cos(Θ) < 0，则 C 在右侧。

我们可以使用点积来帮助我们确定 cos(Θ)。请记住 cos(Θ) = ( v' • w ) / (mag( v' ) ⋅ mag( w ))。然而，我们实际上并不需要 cos(Θ)，我们只需要 sign(cos(Θ))。由于 mag( v' ) 和 mag( w ) 必须都是正数，我们可以忽略它们。因此，如果v' • w > 0，则 C 位于左侧，三个点对应于一个三角形，该三角形是多边形的一部分。另一方面，如果v' • w < 0，则 C 向右，三个点对应多边形外的负空间。

除了简单的测试之外，我实际上还没有尝试过，但我相信它（或接近它的东西）会起作用。

哦，对于其他（像我一样）从未听说过这种技术的人，你可以在这里阅读。