Wie kann man feststellen, ob ein Polygon in einem anderen liegt?

Question

Ich habe ein einfaches Beispiel (SVG source) sieht aus wie Sie unten sehen können. Der Weg mit der ID "rect2816" beschrieben in d Attribut:

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 

Hier ist die erste Zeile beschreibt verwandtes Polygon, das zweite - das Loch (wie Sie sehen können). Aber wie kann ich dieses Lochprogramm so finden? Ich benutze Python. Vielleicht gibt es eine Bibliothek für eine einfache Lösung?

Answer 1

Wandeln Sie die Pfade in (x, y) -Paare um und wenden Sie diese Funktion für jeden Punkt des zweiten Polygons an.

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

Answer 2

nicht so viel von einer Pythonic Antwort, aber ein geometrischer-algorithmischen:

Polygon B innerhalb des Polygons A ist genau dann, wenn jede Ecke B und jeder Kante B ist vollständig innerhalb Polygon A.

Um herauszufinden, ob sich eine Ecke (ein Punkt) innerhalb eines Polygons befindet, besteht ein einfacher Ansatz darin, sogenannte "Ohren" von dem Polygon abzubeißen. Ein "Ohr" ist eine konvexe Ecke und das Abbeißen bedeutet, diese Ecke einfach zu entfernen. Prüfen Sie bei jedem Beißvorgang, ob sich der Punkt im Ohr befindet (das abgebissene Dreieck). (Es gibt einen mathematischen Beweis, dass für jedes unregelmäßige Polygon mindestens zwei solcher Ohren (konvexe Ecken) vorhanden sind.)

Um herauszufinden, ob eine Kante von B vollständig innerhalb von A liegt, müssen Sie herausfinden, ob die Kante schneidet Kante des Polygons A.

Wenn beide Polygone vollständig konvex sind, müssen Sie die Kanten natürlich nicht überprüfen.

Das ist ein unkomplizierter Ansatz ohne die Details der grundlegenden geometrischen Prüfungen, die Sie durchführen müssen. Aber vielleicht hilft es dir.