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

Question

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

在上图中，BC 和 D 不是简单的多边形，但只有 D 会通过交集测试。我的术语（就严格简单而言）可能也有点偏离，但我认为图片说明了我的意思。

Answer 1

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

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

• 2个交叉点，然后它有一个左边缘和一个右边缘，一切都很好。
• 超过 2 个交点，则它具有两个以上从端点开始的边（案例 B）、中间边的端点（案例 C）或与另一条线的交点（案例 D）。

所以在我看来，你的担心是没有根据的：

但是在这里，因为我想检查并不总是属于边缘交叉点的情况 [...]

这种方法在这里也适用。

Answer 2

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

案例B：

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

案例C：

检查以确保没有顶点落在任何边上。假设您使用的是浮点数，这可能会变得很棘手，因为浮点数必须计算为完全相等。这可以通过说它们不能在EPS彼此之间来规避，但这可能会使其他一些几乎无效的多边形无效。EPS除非我真的需要最大的精确度（此时我不知道我会做什么），否则我会亲自使用我自己。

案例 D：

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

案例E：

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

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

我暂时想不出其他情况

Answer 3

案例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)。如果它完全关闭但 CW，您将得到 -1.0。