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

Question

我正在寻找一种算法来测试多边形是否“严格”简单。通常该测试涉及检查任何多边形段之间的交集。但在这里，因为我想检查并不总是处于边缘交叉点的情况，所以我不太确定要查找什么。

在上图中，B C和D不是简单的多边形，但只有D会使相交测试失败。我的术语（绝对简单）也许稍微不合适，但我认为这幅图解释了我的意思。

Answer 1

说两线相交做，如果他们至少有一个共同点。

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

• 2个十字路口，那么它有一个边缘和一个边缘的权利，一切都很好。如果超过2个交点，则它在终点（情况B）开始有两个以上的边，中间的一个边的终点（情形C）或与另一行（情形D）的交点。
在我看来

所以，你的担心是毫无根据的：

但在这里，因为我要检查不总是落在下边缘的边缘相交的情况下[...]

这种方法也适用于此。

Answer 2

这三类无效多边形必须单独检查。

案例B：

检查，以确保没有在您的多边形没有重复的顶点。

案例C：

检查以确保没有顶点落在任何边缘上。假设你使用浮点数，这可能会变得棘手，因为浮点数必须估计为完全相等。这可以通过说他们不能在对方的某个EPS之内来绕过，但是这可能使其他一些几乎无效的多边形失效。我自己亲自使用EPS，除非我真的需要最高精度（在这一点上，我不知道我会做什么）。

案例d：

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

案例E： 两条边重叠（相交于无限多个点）并且它们的顶点不重合。

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

我想不出任何其他情况下暂时