#1 16.08.2007 11:34:26

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Abstand zweier Rechtecke

Schon wieder ich tongue

Ich bräuchte einen Ansatz wie man den Abstand von 2 Rechtecken ( in 3D ) ausrechnet.

Soweit ich mir das überlegt habe liegt der eine Punkt immer auf einer Kante von einem der Rechtecke.
Weiter komme ich aber nicht wirklich.

Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#2 16.08.2007 12:07:21

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand zweier Rechtecke

Zuerst wäre mal sinnvoll:
Wie definierst du den Abstand zweier Rechtecke in 3D ? Vielleicht die Länge der Linie zwischen den beiden sich am nächsten liegenden Punkten?


My software never has bugs. It just develops random features.

Offline

 

#3 16.08.2007 12:19:05

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Re: Abstand zweier Rechtecke

Wenn die Rechtecke parallel zueinander entfernt sind ist schonmal ein Sonderfall.
Der zweite Sonderfall ist wenn sie aufeinander liegen, aber das ist ja ein Sonderfall von parallel.

Meine Überlegung ist, dass die Strecke der kürzesten Verbindung stets senkrecht auf einem der Rechtecke steht und geht von einer Ecke aus. (Das mit der Ecke nur wenn nicht parallel!)
Wie wärs also wenn du von den Ecken von Rechteck A eine Strecke legst, die senkrecht auf Rechteck B steht und das mit allen Ecken von Rechteck A. Dann nemmst due die kürzeste Strecke.

Und jetzt fallt über mich her, ich hatte nicht wirklich viel Zeit zum Überlegen, aber vieleicht isses nen Ansatz wink

Ah wenn sie sich schneiden vielleicht noch beachten...

Beitrag geändert von Dreamworld (16.08.2007 12:21:35)

Offline

 

#4 16.08.2007 12:35:09

Chris
ExtremeMember
Ort: Erlangen, Bay
Registriert: 24.01.2005
Beiträge: 694
Web-Seite

Re: Abstand zweier Rechtecke

[quote=Coolcat]Zuerst wäre mal sinnvoll:
Wie definierst du den Abstand zweier Rechtecke in 3D ? Vielleicht die Länge der Linie zwischen den beiden sich am nächsten liegenden Punkten?

Jo, das hab ich mit Abstand gemeint. Mein Problem ist dann eigentlich ein ClosestPoint Problem.

@Dreamworld:
Ich glaub der punkt muss nicht unbedingt eine ecke sein. Stell dir zwei lange rechtecke vor. Eines ist mit der langen Seite in Z richtung ausgerichtet die Normale in Y. Das andere 'zeigt' in y-richtung die Normale ist richtung X. Das erste Liegt über dem anderen und sie schneiden sich nicht.

wenns unverständlich ist, muss ich was malen wink

mfg Chris


Nimm meinen Rat an - ich brauch ihn sowieso nicht

Offline

 

#5 16.08.2007 12:49:59

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Re: Abstand zweier Rechtecke

hmm naja, aber in deinem Fall ist eine mögliche Lösung doch auch eine Ecke? Gesamtlösung wäre die gesamte Kante?
Und das findest ja heraus, wenn die Länge der unteren beiden Ecken zum anderen Rechteck gleich lang sind.
Ich merke nur grad, dass ich Porbleme bekomme, wenn die Rechtecke weit versetzt zueinander liegen, dann kann ich ja keine senkrechte Strecke bilden. Allerdings wäre dann ja die kürzeste Verbindung Ecke-Ecke.
Ich überlegs mir bei Gelegenheit mal ncoh genauer, aber bin mir relativ sicher, dass das so möglich ist...
Falls ich dein Bsp falsch verstanden hab, mals doch besser mal auf wink

Beitrag geändert von Dreamworld (16.08.2007 12:50:59)

Offline

 

#6 16.08.2007 13:08:55

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand zweier Rechtecke

Ich denke eine Method die den minimalen Abstand zwischen zwei Geraden berechnet dürfte schon mal helfen:

Gegeben sind zwei Geraden: a*g + b und c*h + d
1. Sonderfall abfangen das die Gerade parallel sind. Also prüfen ob a*x = c eine Lösung hat. Wenn die Geraden parallel sind aus Normale a und Punkt b eine Ebene E aufstellen. Den Schnittpunkt s der Geraden c*h + d der Ebene E berechnen. Ergebnis ist der Abstand von b zu s. ENDE.
2. Kreuzprodukt e aus a und c berechnen.
3. Jeweils aus a,e und c,e eine Ebene E1 bzw. E2 aufstellen. (zwei Vektoren spannen ja eine Ebene auf)
4. Schnittpunkt s1 zwischen Ebene E1 und Gerade c*h + d berechnen.
5. Schnittpunkt s2 zwischen Ebene E2 und Gerade a*g + b berechnen.
6. Ergebnis ist Abstand von s1 zu s2. ENDE.

Diese Methode könnte man jetzt benutzen um jeweils alle 16 Kombinationen von Geraden aus beiden Rechtecken durchzutesten. Davon nimmt man dann das Minimum.
Jetzt fehlt nur noch der Sonderfall, dass der nächste Punkt bei einem der Dreiecke mitten in der Ebene liegt. Dazu baut man aus Rechteck 1 eine Ebene E1 mit Normale n und Stützpunkt s. Nun testet man nach einander alle Punkte p des anderen Rechtecks durch:
Berechne Gerade mit Richtung n und Stützpunkt p. Berechne Schnittpunkt t mit E1. Teste ob t innerhalb des Rechtecks liegt. Wenn ja berechne Abstand zwischen p und t. Wenn nein, setze Abstand gleich unendlich.
Das gleiche macht man analog mit dem anderen Rechteck.

Insgesamt ist das Ergebnis dann das Minimum aus allen 24 berechneten Abständen....also reichlich aufwendig wink
Kann man aber sicher noch optimieren.

Edit: Der Sonderfall wenn beide Rechtecke sich schneiden ist nicht berücksichtigt. Müsste man also auch noch testen.

Das ganze ist insgesamt verdammt aufwendig. Du solltest dir ernsthaft überlegen ob du das so wirklich brauchst.

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#7 16.08.2007 13:19:42

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Abstand zweier Rechtecke

Vielleicht reicht dir auch ein nicht ganz so exaktes Ergebnis? Also eine Approximation?
Berechne eine Boundingsphere für beide Rechtecke:
1. Mittelpunkt ist das arithmetische Mittel aus allen vier Eckpunkten. Also alle addieren und durch 4 teilen.
2. Radius ist der maximale Abstand der vier Eckpunkte zum Mittelpunkt.

Dann kannst du einfach den Abstand der Kugeln berechnen (Abstand der Mittelpunkte, ggf. Radius berücksichtigen)

Wenn sich die Rechtecke verschieben, brauchst du nur den Mittelpunkt neu berechnen oder einfach ebenfalls mit der Transformationsmatrix multiplizieren. Der Radius ändert sich ja nur, wenn du skalieren tust.


My software never has bugs. It just develops random features.

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson