如何確定一個多邊形是否在另一個內？

Question

我有一個簡單的例子（SVG source）看起來像你可以看到下面。所述路徑 ID爲 「rect2816」 在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。也許有一些庫容易解決？

Answer 1

將路徑變換爲（x，y）對並將該函數應用於第二個多邊形的每個點。

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

Answer 2

與其說是Python化的答案，但幾何-algorithmical：

多邊形B是多邊形A當且僅當B的每個角和B的每一個邊緣的內側完全是多邊形A.內部

要找出一個角落（點）是否在多邊形內，一個簡單的方法是從多邊形上咬掉所謂的「耳朵」。一個「耳朵」是一個凸角，咬掉它就意味着簡單地去掉這個角落。每次咬人時，檢查點是否在耳內（你咬掉的三角形）。 （有數學證明，對於每個裸露多邊形，至少可以找到兩個這樣的耳朵（凸角）。）

要找出B的邊緣是否完全位於A的內部，意味着您必須找出邊緣是否正在切割多邊形A的邊。

當然，如果兩個多邊形都是完全凸的，則根本不需要檢查邊。

這是一個直接的方法，沒有基本的幾何檢查的細節，你將不得不執行。但也許它可以幫助你。