确定多边形是否有孔？

Question

在尝试了一些三角剖分工作后，我遇到了如何确定多边形是否有孔的问题？

我知道如何处理已知孔，但不确定如何确定是否存在。

例子：

给定以下顶点：

0 ( 0, 0)
1 ( 0,20)
2 (20,20)
3 ( 0,20)
4 ( 2, 2)
5 ( 6, 2)
6 ( 6, 6)
7 ( 2, 6)

我怎么知道它是否是一个简单的多边形，例如：

或非简单/复杂多边形，例如：

我之所以问，是因为我必须使用的数据有可能成为带有一个洞的多边形，但是我不知道这是这样的。

笔记： 多边形将 绝不 要复杂。我只需要知道多边形外部的顶点何时开始，包括孔的顶点开始。

Answer 1

仅从顶点就无法推断多边形边缘的布局。您也需要保留边缘（例如，作为顶点对）。

在您的示例中，例如，另一个图的布局将是0-1-5-6-2-3-7-4-0，其中所得多边形根本没有孔。

如果有边缘，则可以对齐它们，以使它们形成圆，即将其分组为常见的第二/第一个元素：（0，1），（1，2），（2，3），（3，0） （4，5），（5，6），（6，7），（7，4）。如果有一个洞，将会有两个或更多此类组，这些组不能再将其分组在一起。然后，您可以找出谁的点在其他点所包围的区域内，以了解孔在哪里。

Answer 2

弄清楚 如果两个非贴线段相交, ，您会发现孔和多边形之间的分裂。是的，此算法为O（n²），但是一些预知可以帮助减少测试次数。

Answer 3

我的声誉仍然太低，无法评论答案，但我想说我强烈建议遵循有关孔的数学惯例。外多边形应逆时针旋转，孔应始终顺时针方向。 MATLAB以相反的顺序进行此操作，但这对于多边形（顺时针）和孔（逆时针）都进行了

Answer 4

您可以从一个圆“ B”中选择一个点，并判断所选点是在另一个圆圈内或外部“ A”。如果是，那么您就会得到洞。如果不是，那么您从圆A中选择一个点，然后判断该点是否在圆B内部，如果是，则得到孔。