Schnittfläche gedrehter Rechtecke
-
Hallo,
ich brauche einen Algorithmus der mir die Schnittfläche von zwei beliebigen Rechtecken ausrechnet. Beliebig heißt in diesem Kontext dass die Rechtecke auch gedreht sein können.
Ich hab das Ganze auch schon als allgemeine Polygon-Klasse geschafft zu implementieren indem ich einfach für jede Kante über jede Kante des jeweils anderen Rechtecks iteriere und etwaige Schnittpunkte berechne. Dann checke ich für jeden Punkt des einen Rechtecks ob er im anderen Rechteck liegt (und umgekehrt), was mir dann alle Punkte meines Polygons liefert.
Problem dabei ist dass dieser allgemeine Ansatz ziemlich aufwändig ist.
Da es sich bei den Polygonen ja nur um Rechtecke handelt meine Frage: Gibt es für diesen Spezialfall nicht eine effektivere Lösung?
-
http://www.sunshine2k.de/coding/java/SutherlandHodgman/SutherlandHodgman.html
effektivere Lösung
Die hast du bereits. Du suchst eine effiziente Loesung.
Du kannst anfangen, einzelne Teile zu optimieren. Beispiel 1: Test fuer Punkt in Polygon wird zu Punkt in Rechteck ... wesentlich einfacher. Beispiel 2: Wahl des Koordinatensystems: Waehle ein Koordinatensystem, so dass ein Rechteck immer "axis-aligned" ist. Test auf Punkt in Rechteck noch einfacher.
-
Du könntest vor der eigentlichen Kontrolle mit Boundingspheres oder -boxes entscheiden, ob ein Schnittpunkt überhaupt in Frage kommt und je nach Anzahl und Verteilung einen Großteil der Berechnungen sparen.