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

Question

我有一个简单的示例（SVG 源代码），如下所示。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

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

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

Answer 2

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

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

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

要确定 B 的边是否完全在 A 内，意味着您必须确定该边是否正在切割多边形 A 的任何边。

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

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