测试严格简单多边形（允许有洞）？

Question

我正在寻找一种算法，以测试多边形是否“严格”简单。通常，该测试涉及检查多边形线段之间的任何交点。但在此处，由于我想检查不总是属于边缘-边缘相交的情况，我不太确定要寻找什么。在上面的图像中，B C 和 D 不是简单的多边形，但只有 D 将失败于交叉测试。我的术语（以严格简单为例）可能有点不对，但我认为图片说明了我的意思。

- Prismatic

---

只需检查顶点-边缘交点以及边缘-边缘交点。 - Beta

如果实际存在交点，B 和 C 也应该未通过边缘相交检查。角点“非常接近”于一条边不算作相交，对吧？@Beta：一个点不能与任何东西相交。你是什么意思？ - Matti Virkkunen

你是在.NET/CLR框架中运行C++吗？ - Erik Philips

Matti：如果交点检查包括线段端点，那么所有的多边形都会失败吗？如果我忽略相邻的线段，那么它会起作用，但我不确定是否有任何我没有考虑到的情况会导致问题。Erik：不，使用gcc的c++。 - Prismatic

这不是一个真正的编程问题，是吗？在我看来，它应该属于math.SE。 - leftaroundabout

更好的答案在这里：https://math.stackexchange.com/q/80798/414894 - Cris Luengo

Answer 1

如果两条线有至少一个共同点，则它们相交。

取一条边并计算与任何其他边的交点。如果它有

• 2个交点，则它左侧有一条边，右侧有一条边，一切正常。
• 超过2个交点，则它可能有超过两条以端点为起点的边（情况B），中间有一条边的端点（情况C）或与另一条线相交（情况D）。

所以我认为你的担忧是没有根据的：

但是，在这里，由于我想检查不总是落在边缘交叉处的情况[...]

这种方法在这里也适用。

- ipc

Answer 2

情况 F：顶点形成一个封闭的环，按逆时针顺序给出。这可以通过循环遍历所有顶点并总结关节角度来完成。我选择以“旋转”为角度单位：（伪代码）

vertex_n_minus1 = [ x, y ]
vertex_n = ..
vertex_n_plus1 = ..
DirectionVector incomingDir = new DirectionVector(vertex_n_minus1, vertex_n)
DirectionVector outgoingDir = new DirectionVector(vertex_n, vertex_n_plus1)
DirectionVector dirChange = [ outgoingDir • incomingDir, outgoingDir • rot90CW(incomingDir) ]
double jointTurnAmountRevs = dirChange.toAngle() / (2*PI) (convert dirVec --> angle_radians -> revs)

如果你对变量jointTurnAmountRevs求和，一个逆时针的完全闭合的多边形路径将等于1.0（+- epsilon）。如果它是完全闭合但顺时针的，你会得到-1.0。

- pbierre

---

我认为这并没有说明多边形是否具有自交。对于非简单多边形，顶点角度的总和也是1。 - Cris Luengo

顶点角度总和不应被依赖，除非所有其他“简单多边形”测试都已通过。它用于验证顶点列表是否按逆时针遍历（如果是规范的）。例如，三角剖分算法（将简单多边形切割成凸子多边形）可能依赖于给定一个逆时针顶点列表，因此需要提前验证。 - pbierre

Answer 3

这三类无效的多边形需要分别进行检查。

情况B：

检查多边形中是否存在重复的顶点。

情况C：

检查多边形中是否有顶点落在任何一条边上。假设您使用的是浮点数，这可能会变得棘手，因为浮点数必须完全相等才能计算。这可以通过说它们不能相互靠近某个EPS来避免，但这可能会使一些其他几乎无效的多边形失效。我个人会使用EPS，除非我真的需要最高精度（此时我不知道我会怎么做）。

情况D：

正如您所说，这可以通过检查任何边是否相交来找到。

情况E：

两条边重叠（在无限多个点处相交），但它们的顶点不重叠。

我不确定这是否需要成为一个单独的情况，但是这种情况可能不会被情况D的检查捕获（我认为您最终会除以零）。因此，您还必须检查这两条边是否对应于完全相同的线。

我暂时想不到其他情况。

- SirGuy