ポリゴンが他のポリゴンの内側にあるかどうかを調べる方法は？

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

パスを（x、y）ペアに変換し、この関数を2番目のポリゴンの各ポイントに適用します。

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

Answer 2

のでPython的回答の多くが、幾何algorithmicalなし：

ポリゴンBは、Bの各コーナーとBの各エッジIFF多角形Aの内側にあるポリゴンA.内部に完全に

コーナー（ポイント）がポリゴンの内側にあるかどうかを確認するには、ポリゴンからいわゆる「耳」を片付けるのが簡単です。 「耳」は凸状のコーナーであり、それを噛むことは単にこのコーナーを取り除くことを意味する。それぞれの噛んでいる行為で、その点が耳の内側にあるかどうかをチェックします。 （ループがないポリゴンごとに、少なくとも2つのそのような耳（凸コーナー）を見つけることができるという数学的証明があります）。

Bのエッジが完全にAかどうかを調べるには、ポリゴンAのエッジ。

もちろん、両方のポリゴンが完全に凸であれば、エッジをまったく確認する必要はありません。

これは、実行する必要がある基本的なジオメトリチェックの詳細がない単純なアプローチです。しかし、おそらくそれはあなたを助けます。