删除多边形中的孔

Question

我有一个由点阵列确定的多边形。

这个多边形正在交叉自己在多边形本身上做一些洞。

我的问题是：我怎样才能省略这个孔，只是得到多边形的外部点？

或者什么会是相同的，可能更容易：我应该使用哪种算法检查点是否在多边形内部，以检测多边形孔中的点作为内点？

由于提前，

/罗杰

Answer 1

首先，找到边缘的所有交叉点，这些交叉点添加到顶点列表，并在这些交叉点边缘分裂。然后，从一个显然是外部顶点（例如“最右边的”）的顶点开始，并追踪轮廓，将边和顶点添加到结果集中。追踪轮廓仅仅沿着边缘以最小角度到最后边缘。

Answer 2

您可能想要找到多边形中所有点的凸包。

这样做的一种算法是复杂度为O（nlgn）的Graham-Scan。来自Cormen：

Let Q be the set of all points in your polygon 
Graham-Scan(Q) 

1 let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie 
2 let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0 
     if more than one point shares the same polar angle, keep the farthest point 

3 let S be an empty stack 
4 PUSH(p0, S) 
5 PUSH(p1, S) 
6 PUSH(p2, S) 
7 for i = 3 to m 
8 while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn 
9  POP(S) 
10 PUSH(pi, S) 
11 return S 

S现在包含您的多边形的所有外部点。你必须做一些极坐标数学，但这很简单。按极坐标排序按照您最底部的点排列其余切点上的所有点。我忘记了检查右转的代码，但是如果你只是从格雷厄姆扫描中搜索，它就在互联网上。希望这可以帮助！