Schnittfläche zweier Dreiecke oder einer Menge von Halbebenen oder Fläche einer konvexen Punktmenge
Ich muss den Bereich der Überlappung zwischen zwei Dreiecken in der 2D-Ebene berechnen. Seltsamerweise habe ich @ geschriebCod für das Dreieck-Kreis-Problem, und das funktioniert recht gut und robust, aber ich habe Probleme mit dem Dreieck-Dreieck-Problem.
Ich überprüfe bereits zuerst, ob einer den anderen vollständig enthält oder ob der andere den ersten enthält und erhalte alle kantenweisen Schnittpunkte. Diese Schnittpunkte (bis zu 6, wie im Davidstern) bilden zusammen mit den Dreieckscheitelpunkten, die im anderen Dreieck enthalten sind, die Scheitelpunkte des Schnittbereichs. Diese Punkte müssen ein konvexes Polygon bilden.
ie Lösung, die ich suche, ist die Antwort auf eine der folgenden Frage
Gab eine Reihe von Punkten, die @ bekannt siall Liegen Sie auf der konvexen Hülle des eingestellten Punktes, berechnen Sie die Fläche der konvexen Hülle. Beachten Sie, dass sie in zufälliger Reihenfolge sind.Bestimmen Sie den Schnittbereich, indem Sie eine Reihe von Halbebenen angeben. Dies entspricht der Beschreibung beider Dreiecke als Schnittpunkt dreier Halbebenen und der Berechnung der Lösung als direkter Schnittpunkt dieser BeschreibunIch habe für Frage 1 überlegt, einfach alle Bereiche aller möglichen Dreiecke zu addieren und dann beim Zählen durch die Multiplizität zu dividieren, aber das scheint dumm zu sein, und ich bin mir nicht sicher, ob es richtig ist. Ich habe das Gefühl, dass es eine Art Sweep-Line-Algorithmus gibt, der den Trick macht. Die Lösung muss jedoch auch numerisch relativ robust sein.
Ich habe einfach keine Ahnung, wie Frage 2 zu lösen ist, aber eine allgemeine Antwort wäre sehr nützlich, und die Bereitstellung von Code würde meinen Tag verlängern. Dies würde die direkte Berechnung von Schnittbereichen von konvexen Polygonen ermöglichen, anstatt eine Dreieckzerlegung an ihnen durchführen zu müsse
Bearbeite: Ich bin mir bewusst, dassDieser Artike beschreibt den allgemeinen Fall zum Auffinden des Schnittpolygons zweier konvexer Polygone. Es scheint eher für Dreiecke beteiligt zu sein, und außerdem brauche ich das resultierende Polygon selbst nicht wirklich. Vielleicht wird diese Frage an dieser Stelle nur faul gestellt.