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

Question

我有一个简单的例子（SVG source）看起来像你在下面看到的。d属性中描述的id为“rect2816”的路径：

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

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

当B的每个角和B的每一条边都完全在多边形A内时，多边形B在多边形A的内部

要找出一个角（一个点）是否在多边形内，一个简单的方法是咬掉多边形上所谓的“耳朵”。“耳朵”是一个凸角，咬掉它意味着简单地去掉这个角。每次咬人的时候，都要检查这个点是否在耳朵里面（你咬掉的三角形）。（有数学证明，对于每个无环多边形，至少可以找到两个这样的耳朵（凸角）

要找出B的一条边是否完全在A内，就意味着你必须找出这条边是否正在切割多边形A的任何一条边

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

这是一种直接的方法，没有你将要执行的基本几何检查的细节。但也许这对你有帮助。在

Answer 2

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

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