Kollisionsberechnung bei zwei Rechtecken

[Katsumi]

Hi.

Ich habe zwei verdrehte(Winkel) Rechtecke und von beiden Rechtecken die Koordinaten der 4 Eckpunkte.

Ich möchte gern eine rechenfreundliche Methode finden wie man kontrollieren kann, ob sich die Rechtecke irgendwie berühren oder überlappen(Kreuz).

Das sollte ohne sin/cos auskommen wenn man Vektorechnung benutzt, aber auf dem Gebiet bin ich nicht mehr so fit, kann da wer helfen oder kennt eine sichere schnelle Mothode?

 

[ghettokn00b]

Du kannst wenn du die Eckpunkte hast doch eine Ebenengleichung aufstellen

stützvektor+r* richtungsvektor1+s*richtungsvektor2

Die richtungsvektoren sind ja die eckpunkte minus stückvektor, also dem nullvektor zu einem eckpunkt. wenn r oder s jetzt über 1 sind, um einen schnitt mit einer anderen würfelfläche zu erzeugen, dann berühren sie sich nicht, weil die Ebenenfläche für r und s >1 ja größer als die würfelfläche ist, somit der schnittpuntk außerhalb des Würfels liegt. so kannst du mit allen Flächen verfahren, und immer überprüfen ob sich die Flächen mit denen des anderen Würfels überschneiden

 

[Kampfgnom]

In wie vielen Dimensionen befinden sich denn die Rechtecke? 2, 3 oder gleich n-Dimensional?

 

[ghettokn00b]

ich denke mal im R3 oder?

 

[Katsumi]

Im einfachem 2D System.

 

[ghettokn00b]

das vereinfacht das ganze ja natürlich noch, weil du dann für ein rechteck auch nur eine fläche hast. Dann brauchst du ja auch nur eine Abfrage

 

[Katsumi]

Wäre sehr lieb wenn das vielleicht bissle näher ausführen könntest. Mathe ist nicht mehr so meine Stärke und ein Beispiel würde mir unheimlich helfen

Ich habe mir hier mehrere Beispiele aufgezeichnet.

Rechteck1 P1(3;6) P2(4;6) P3(4;1) P4(3;1) dieses Rechteck steht senkrecht

Rechteck2 P1(3;3) P2(3;4) P3(6;2) P4(5;1) dieses Rechteck ist 45° nach rechts unten gekippt

Gemeinsame Schnittpunkte wären (gemessen): (3;4) (4;3.5) (4;1.75) (3;3.35)


Falls nicht zu aufwendig ist, wie müsste die Formel dann ausschauen, damit ich eine Schnittmenge erhalte oder eben keine falls sie keien haben.

 

[ghettokn00b]

äh sorry aber zeichne dir das 2te rechteck mal in ein koordinatensystem das ist kein rechteck. die schnittpunkt können auch nicht stimmen, z.B. 3;3.35
Hast du da nen Tippfehler? Korrigier das mal sonst kann ich dir nur schwer helfen

P3(4;4) wäre ok

 

[Katsumi]

Argh, ja dumm vertan.

Rechteck1 P1(1;6) P2(5;10) P3(9;6) P4(5;2) ein Rechteck das auf der Spitze steht (45°)

Rechteck2 P1(7;11) P2(11;11) P3(11;1) P4(7;1) steht Hochkannt auf der rechten Hälfte von Rechteck1

Schittpunkte A(7;8) und B(7;4)

 

[ghettokn00b]

brauchst du denn nur die schnittpunkte?

wofür ist das genau

 

[Katsumi]

Ich habe beliebige (verdrehte) Rechtecke und möchte nur wissen ob diese eine gemeinsame Schnittmenge haben. Also nur ein true oder false

 

[ghettokn00b]

ist also ne boolsche funktion bei dir
machst du das mit delphi?

 

[Katsumi]

Jaein.. ich nutze hier parallel mehrere System zum testen. DevC++, Delphi und PHP Grad wonach mir ist

 

[ghettokn00b]

So sieht deine Ebenengleichung aus(unten angehängt)
die richtungsvektoren ergeben sich aus den punkten rechts und links des stützvektors(der vorne in der gleichung)- des Stützvektors
also (1;6)-(5;2)=(-4;4) und (9;6)-(5;2)=(4;4)
denk dir für die untere mal l und m ich hab das übersehen


Wenn du die jetzt gleichsetzt dann kommt folgendes raus:

r=(10*n*5+4*n*6+1)/8 s=(10*5-4*n*6-3)/8 l=n*6 m= n*5


für r, s, l und m müssen n existieren, sodass r,s,l und m im -bereich {0;1} liegen
Ist das der fall schneiden sie sich. Wie du das jetzt umsetzt ist dein problem

 

[Katsumi]

Ähm danke, das versuch ich mal morgen zu verstehen, momentan ist eher Bahnhof

 

[TomyLight]

omg das hatte ich grad in der 12. ...
is eigentlich nicht sonderlich schwer....