logo标签列表

判断多边形是否有洞？

mathgraphicspolygontriangulation
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)

我如何知道它是一个简单的多边形，例如： enter image description here 还是一个非简单/复杂的多边形，例如： enter image description here 我问这个问题是因为我将要处理的数据可能是带有洞的多边形，但我事先不知道是否存在。
注意：该多边形永远不会是复杂的。我只需要知道外部多边形的顶点何时结束，孔的组成顶点何时开始。
1
如果您只需要检测多边形是否已经闭合，那么只需检查该点是否已经出现过，这不就是一个简单的问题吗？ - gordy
一个多边形是封闭的，当线段在起点和终点连接时。也就是说，你开始在一个点画线，并在同一点结束。 - Johnathan Enslin
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)。如果存在孔，将会有两个或更多这样的不能进一步组合的组。你可以找出在其他点所包围区域内的点来知道孔的位置。
3

我目前的声誉还不足以在回答下发表评论，但我想说我强烈建议遵循数学惯例关于空洞的规定。外多边形应该按逆时针方向，而内部的空洞应始终顺时针方向。MATLAB则采用相反的顺序，但这适用于多边形（顺时针）和空洞（逆时针）。

哦，我不知道这个。我会记住的！你有关于这个特定问题的进一步阅读材料吗？ - ssell
这是基本数学，许多定理都基于这个事实。有几种非常简单的方法可以找出曲线是孔还是外边界，其中之一就是利用孔具有另一种方向的事实。在维基百科上搜索“曲线方向”(¤)。要确定一个多边形是孔还是另一个相邻的多边形，例如可以计算每对相邻节点所涵盖的面积之和。如果总和为正，则存在外边界；如果总和为负，则表示它是一个孔。您还可以将顶点向量化，并像(¤)中描述的那样求它们的叉积之和。 - patrik
2
找出如果两条非相邻的线段相交，你就能找到洞和多边形之间的分裂点。是的，这个算法是O(n2)的，但一些预先知识可以帮助减少测试的数量。
1
只有当他拥有多边形线段的集合时，这才有帮助。 - Neowizard
这假设相邻的顶点形成边，这并不是很难理解。 - Ignacio Vazquez-Abrams
相邻顶点是什么？据我所知，顶点的相邻关系是通过边来建立的...如果您对相邻性的定义是“靠近的点”，那么绿色多边形将永远不会形成（因为4比任何其他点都更接近0，所以会有一条边（0, 4）。） - Felix Dombek
@Felix：如果你看一下问题，你会注意到提问者已经将顶点从0到7编号了。相邻的顶点是指它们的索引差为1，或者是序列中的第一个和最后一个顶点。 - Ignacio Vazquez-Abrams
在这种情况下，会有一条边（3,4），但该边在示例中不存在... - Felix Dombek
当然它不存在。使用我的算法会确定它与 (0, 7) 相交，这意味着这些对将外部与孔分开，正如我所说的那样。 - Ignacio Vazquez-Abrams
0

你可以从圆“B”中选择一个点，并判断所选点是否在另一个圆“A”内。如果是，则得到孔洞。如果不是，则从圆“A”中选择一个点，并判断该点是否在圆“B”内，如果是，则得到孔洞。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接