如何确定一个多边形是否在另一个多边形内部？

Question

我有一个简单的例子（SVG源代码），如下所示。带有id“rect2816”的path在d属性中描述：

m 140.53571,188.625 0,148.1875 273.9375,0 0,-148.1875 -273.9375,0 z 
m 132.25,42.03125 c 3.64586,0.0236 7.47296,0.12361 11.5,0.28125 36.65941,1.43507 57.84375,15.88072 57.84375,32.84375 0,7.41614 -1.94981,21.58652 -13.28125,24.09375 -14.58711,3.2276 -40.46224,-5.35276 -53.125,6.625 -26.65285,25.21104 -48.00843,-19.04537 -57.875,-32.84375 -12.16196,-17.00847 0.24962,-31.35357 54.9375,-31 z

这里，第一行描述了父多边形，第二行描述了洞（如您所见）。但是我该如何以编程方式找到此洞？我正在使用Python。也许有一些库可以提供简单的解决方案？

- art.zhitnik

---

一种可能性是检查第二个多边形的每个顶点是否在第一个多边形内，且第二个多边形的任何边都不会穿过第一个多边形。 - Vaughn Cato

Answer 1

将路径转换为（x，y）对，并将此函数应用于第二个多边形的每个点。

# determine if a point is inside a given polygon or not
# Polygon is a list of (x,y) pairs.

def point_inside_polygon(x,y,poly):

n = len(poly)
inside =False

p1x,p1y = poly[0]
for i in range(n+1):
    p2x,p2y = poly[i % n]
    if y > min(p1y,p2y):
        if y <= max(p1y,p2y):
            if x <= max(p1x,p2x):
                if p1y != p2y:
                    xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                if p1x == p2x or x <= xinters:
                    inside = not inside
    p1x,p1y = p2x,p2y

return inside

Source: http://www.ariel.com.au/a/python-point-int-poly.html

- mihai

---

要将任意路径转换为多边形，请参见http://phrogz.net/svg/convert_path_to_polygon.xhtml。 - Phrogz

@mihai，你提供的链接已经失效了。 - Federica Tomola

@FedericaTomola 我更新了答案，包括代码，原始页面仍可在archive.org上找到：https://web.archive.org/web/20140301111830/http://www.ariel.com.au/a/python-point-int-poly.html - mihai

Answer 2

这不是典型的Python解答，而是一种几何算法：

如果多边形B的每个角和每条边都完全在多边形A内，则多边形B在多边形A内部。

为了判断一个角（一个点）是否在多边形内部，可以通过“割耳朵”方法来简单实现。"耳朵"是一个凸角，割掉耳朵就意味着要移除这个角。每次割掉耳朵时，检查点是否在耳朵内（你割下的三角形）。数学上有证明，对于每个无环多边形，你至少可以找到两个这样的耳朵（凸角）。

为了确定B的一条边是否完全位于A内部，必须确定该边是否与多边形A的任何边相交。

当然，如果两个多边形都是完全凸的，那么你根本不需要检查边缘。

这是一种直接的方法，没有详细说明你必须执行的基本几何检查的细节。但也许会对你有所帮助。

- Alfe

---

mihai 给了我你建议的 Pythonic 实现。谢谢！ - art.zhitnik