如何判断一个多边形是否在另一个多边形内部？

Question

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

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。也许有一些库可以轻松解决？

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

来源： https://web.archive.org/web/20140301111830/http://www.ariel.com.au/a/python-point-int-poly.html

Answer 2

与其说是Python式的答案，不如说是几何算法：

多边形 B 位于多边形 A 内部，当且仅当 B 的每个角和 B 的每条边完全位于多边形 A 内部。

要判断一个角（点）是否在多边形内部，一个简单的方法就是从多边形上咬掉所谓的“耳朵”。 “耳朵”就是一个凸角，咬掉就是简单地去掉这个角。每次咬住动作时，检查该点是否在耳朵内部（您咬掉的三角形）。 （有数学证明，对于每个无环多边形，您可以找到至少两个这样的耳朵（凸角）。）

要判断 B 的一条边是否完全在 A 内，就必须判断该边是否与多边形 A 的任何边相切。

当然，如果两个多边形都是完全凸的，则根本不必检查边缘。

这是一种直接的方法，无需您必须执行的基本几何检查的详细信息。但也许它对你有帮助。