确定多边形是否有孔？

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).如果有一个洞,将会有两个或更多这样的组,这些组不能再组合在一起.然后,您可以找到其他点周围的区域内的哪些点,以了解孔的位置.