Ich habe eine Reihe einfacher Polygone (keine Löcher, keine Selbstüberschneidungen), und ich muss prüfen, ob sie sich nicht überschneiden (eines kann vollständig in einem anderen enthalten sein; das ist in Ordnung). Ich kann dies überprüfen, indem ich einfach die Scheitelpunkt-Innerlichkeit eines Polygons im Vergleich zu anderen Polygonen überprüfe.

Ich muss auch den Containment-Baum bestimmen. Dies ist die Menge von Beziehungen, die besagen, welches Polygon ein bestimmtes Polygon enthält. Da kein Polygon ein anderes schneiden kann, hat jedes enthaltene Polygon einen eindeutigen Container. der "nächstgrößere". Mit anderen Worten, wenn A B enthält, das C enthält, dann ist A der Elternteil von B und B der Elternteil von C, und wir betrachten A nicht als Elternteil von C.

Die Frage: Wie kann ich die Containment-Beziehungen effizient bestimmen und das Nicht-Schnitt-Kriterium überprüfen? Ich stelle dies als eine Frage, weil ein kombinierter Algorithmus möglicherweise effizienter ist, als jedes Problem einzeln zu lösen. Der Algorithmus sollte eine Liste von Polygonen als Eingabe verwenden, die durch eine Liste ihrer Scheitelpunkte gegeben ist. Es sollte einen Booleschen Wert B erzeugen, der angibt, ob keines der Polygone ein anderes Polygon schneidet, und auch, wenn B = true, eine Liste von Paaren (P, C), wobei das Polygon P das übergeordnete Element von Kind C is

Dies ist keine Hausaufgabe. Dies ist für ein Hobbyprojekt, an dem ich arbeite.