Intersection von Rechtecken..?

[sirbender]

Hi,

ich will ueberpruefen ob 2 Rechtecke sich schneiden. Dabei gibt es 2 Faelle. Die Rechtecke sind rotiert bzw. unrotiert.


Ich muss diesen Test viele Milliarden Male durchfuehren. Bisher habe ich die Java-eigenen Methoden von Rectangle und Area benutzt aber die sind zu langsam fuer meinen Anwendungsfall.

Hat vielleicht jemand Java code fuer die 2 Faelle der schneller ist? Bin leider mathematisch sehr wenig bewandert und koennte es wohl auch wenn es jemand beschreibt nicht selbst umsetzten wenn es nicht total trivial ist.

Danke,
sb

 

[Ezra]

Meinst Du nicht, dass diejenigen, die die Java-Funktionen geschrieben haben, die bestmögliche Performance dafür herauszuholen versuchen?

Ich bezweifle, dass Du mit einer selbstgeschriebenen Methode weiterkommst. Viel mehr wundert es mich, warum Du überhaupt mehrere Milliarden Tests durchführen musst. Lässt sich das nicht optimieren?

Ansonsten kannst Du es gern mal so versuchen: Algorithm to detect intersection of two rectangles? - Stack Overflow

 

[sirbender]

Nein. Die Milliarden Tests sind gewollt. Die Algorithmen die Java bietet sind z.B. nicht identisch mit der Stackoverflow Methode. Was aber nicht heisst dass ich es selbst implementieren kann um die Performance beider zu vergleichen

 

[Marco13]

Was genau (!) sind die beiden Fälle? (Ist das andere Rechteck immer um 45° gedreht und so...?)

 

[newnoise]

ohne zu wissen wie Java es macht:

Fall unrotiert ist trivial. Wenn einer der 4 Eckpunkte von A in B liegt überschneiden sie sich.
Fall rotiert ist quasi genauso trivial, nur das Du sowohl prüfen musst ob von A ein Punkt in B liegt und ob von B ein Punkt in A liegt.

Ich denke aber, dass Java das genauso macht.

 

[Marco13]

Fall unrotiert ist trivial. Wenn einer der 4 Eckpunkte von A in B liegt überschneiden sie sich.

Für jedes Problem gibt es eine Lösung, die einfach, elegant ... und falsch ist Die Rechtecke können auch ein Kreuz bilden. Kein Eckpunkt liegt im anderen, aber sie überschneiden sich.

Deswegen das "(!)" bei der Frage "Was genau (!) sind die beiden Fälle?"...

 

[newnoise]

zu meiner Entschuldigung:
es war schon recht spät!

 

[Ezra]

Was aber nicht heisst dass ich es selbst implementieren kann um die Performance beider zu vergleichen

Warum? Die Methode ist recht gut beschrieben. Du kannst aber schon programmieren, oder?

Ansonsten schließe ich mich mit meinen Fragen Marco13 an. Sofern sich die Fälle eingrenzen lassen, kann man möglicherweise noch Laufzeit verbessern. Sind beispielsweise die Rechtecke immer gleich groß? Gibt es noch andere Besonderheiten?