4

在尝试了一些三角测量工作后,我遇到了关于如何确定多边形是否有洞的问题?

我知道如何处理已知漏洞,但不确定如何确定是否存在。

例子:

给定以下顶点:

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

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

在此处输入图像描述

或非简单/复杂的多边形,例如:

在此处输入图像描述

我问是因为我必须使用的数据有可能是一个有洞的多边形,但我事先并不知道它是这样的。

注意:多边形永远不会复杂。我只需要知道多边形外部的顶点何时结束以及构成孔的顶点何时开始。

4

4 回答 4

5

仅从顶点无法推断多边形边缘的布局。您还需要保留边(例如作为顶点对)。

在您的示例中,另一个图形布局将是例如 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)。如果有一个洞,就会有两个或多个这样的组,不能再进一步组合在一起。然后,您可以找出谁的点在其他点包围的区域内,从而知道孔在哪里。

于 2011-07-24T06:48:19.090 回答
2

弄清楚两个不相邻的线段是否相交,你会发现孔和多边形之间的分割。是的,这个算法是 O(n 2 ),但是一点预知可以帮助减少测试的数量。

于 2011-07-24T06:46:59.323 回答
2

我的声誉太低,无法评论答案,但我想说我强烈建议遵循关于孔的数学惯例。外部多边形应逆时针方向,孔应始终顺时针方向。MATLAB 以相反的顺序执行此操作,但对于多边形(顺时针)和孔(逆时针)都是如此

于 2013-11-22T10:07:07.130 回答
0

您可以从一个圆圈“B”中选择一个点,并判断所选点是在另一个圆圈“A”的内部还是外部。如果是,那么你得到了这个洞。如果不是,则从圆A中选择一个点并判断该点是否在圆B内,如果是,则得到孔。

于 2018-10-10T03:36:48.223 回答