geometry - 删除多边形中的孔

Question

我有一个由点数组确定的多边形。

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

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

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

提前致谢，

/罗杰

Answer 1

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

Answer 2

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

执行此操作的一种算法是复杂度为 O(nlgn) 的 Graham-Scan。从科门：

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 现在包含多边形的所有外部点。你必须做一些极地数学，但这很简单。要按极坐标排序，将所有点与您的最底点的余切点进行排序。我忘记了检查右转的代码，但如果你只是搜索 Graham-Scan，它就在互联网上。希望这可以帮助！