Schnitttest(Gerde, Gerade) im R^3 und Schittpunktberechnung

12/06/2009 - 13:15 von Robert Hartmann | Report spam
Hallo zusammen,

Der Test, ob sich zwei beliebige Geraden im R^3 schneiden,
ist recht einfach implementiert.

Gegeben zwei Geraden A und B.

A: A.origin + lambda* A.direction
B: B.origin + kappa * B.direction

A.origin, B.origin, A.direction, B.direction sind Vektoren des R^3,
lambda und kappa sind aus R.

Weiterhin gilt, dass weder A.direction noch B.direction
identisch mit dem Nullvektor sind.

Der Test auf Existenz eines Schnittpunktes müsste sein:

Falls
Richtungsvektoren der Geraden sind linear unabhàngig, d.h.
crossProd(A.direction, B.direction)
!= (0,0,0)
und
Strahlen sind nicht windschief, d.h.
spatProd(A.direction, B.direction, (B.origin - A.origin))
= dotProd(crossProd(A.direction, B.direction),(B.origin - A.origin))
== 0
dann
schneiden sich die Strahlen
sonst
nicht.


Implementation mit C++

bool Ray3D::isIntersecting(const Ray3D& A, const Ray3D& B)
{
assert((A.direction!=Vector3D(0,0,0))&&(B.direction!=Vector3D(0,0,0)));
Vector3D cP = crossProd(A.direction, B.direction);
Vector3D oD = B.origin - A.origin;
if (( cP != Vector3D(0,0,0) ) && ( dotProd(cP,oD) == 0 ))
return true;
else
return false;
}



Bei der Implementation einer Methode für die
Schnittpunktberechnung komme ich irgendwie zu
keinem schön übersichtlichen Ergebnis.

Wenn ich die Geradengleichungen gleichsetze

A.origin + lambda* A.direction
= B.origin + kappa * B.direction

dann erkenne ich in Komponentenschreibweise

A.origin.x+ lambda * A.direction.x
= B.origin.x + kappa * B.direction.x

A.origin.y+ lambda * A.direction.y
= B.origin.y + kappa * B.direction.y

A.origin.z+ lambda * A.direction.z
= B.origin.z + kappa * B.direction.z

dass man auf jeden Fall, um lambda
und kappa ausrechnen zu können,
Fallunterscheidungen braucht;
denn durch Null zu dividieren
ist ja nicht gerade zulàssig.


Betrachten wir den Fall
(A.direction.x!=0)&&(B.direction.y!=0)
etwas genauer:

Es gilt nach Umstellung der Komponentenschreibweise:

lambda
= (B.origin.x + kappa * B.direction.x - A.origin.x)
/ A.direction.x
= (B.origin.x - A.origin.x) / A.direction.x
+ (kappa * B.direction.x) / A.direction.x


und

kappa
= (A.origin.y+ lambda * A.direction.y - B.origin.y)
/ B.direction.y
= (A.origin.y - B.origin.y) / B.direction.y
+ lambda * A.direction.y / B.direction.y

Um den Wert für lambda zu bestimmen,
setze ich nun kappa in lambda ein und löse nach lambda auf:

lambda
= (B.origin.x - A.origin.x) / A.direction.x
+ (kappa * B.direction.x) / A.direction.x
= (B.origin.x - A.origin.x) / A.direction.x
+ ((A.origin.y - B.origin.y) / B.direction.y
+ lambda * A.direction.y / B.direction.y)
* B.direction.x) / A.direction.x

damit ist, wenn ich mich nicht verrechnet habe:

lambda
= ( [(B.origin.x-A.origin.x)/A.direction.x]
+ ( [(A.origin.y-B.origin.y)/B.direction.y]
*[B.direction.x/A.direction.x ) )
/ ( 1
- [A.direction.y*B.direction.x]
/ [B.direction.y*A.direction.x] )

diesen Wert in die kappa-Berechnung einsetzen.

Wenn mit den so berechneten Werten für
lambda und kappa die bisher ungenutzte
dritte Komponentengleichung zur wahren
Aussage wird

A.origin.z+ lambda * A.direction.z
== B.origin.z + kappa * B.direction.z ,

kann man endlich den Schnittpunkt zurückliefern.

Dies ist wie geschrieben nur der Fall
(A.direction.x!=0)&&(B.direction.y!=0) gewesen.


Ähnliches müsste man nun für die anderen Fàlle,
dazu darf man dann aber auch keinen der Fàlle
vergessen, auch machen.

Nun zu meiner eigentlichen Frage:

Kann man eine allgemeine Schnittpunktbestimmung
nicht irgendwie deutlich einfacher implementieren?

Dazu sei weiterhin angemerkt,
dass der Zugriff auf die Vektor-Komponenten
auch mit numerischen Indizes zugreifen kann:
So ist z.B.
A.origin.x == A.origin[0],
A.origin.y == A.origin[1],
A.origin.z == A.origin[2].
entsprechend àhnlich für die anderen Vektoren
A.direction, B.origin, B.direction

Gruß Robert
 

Lesen sie die antworten

#1 Jakob Creutzig
12/06/2009 - 13:29 | Warnen spam
Robert Hartmann writes:

Der Test, ob sich zwei beliebige Geraden im R^3 schneiden,
ist recht einfach implementiert.


[..]
Bei der Implementation einer Methode für die
Schnittpunktberechnung komme ich irgendwie zu
keinem schön übersichtlichen Ergebnis.

Wenn ich die Geradengleichungen gleichsetze

A.origin + lambda* A.direction
= B.origin + kappa * B.direction



hast Du ein lineares Gleichungssystem mit zwei
Unbekannten in drei Dimensionen:

(lamba, -kappa) * (A.direction, B.direction)^T
= B.origin - A.origin

Quasi der Grossvater aller linearen Gleichungssysteme ;-).

fup2 dsm

Best,
Jakob

Ähnliche fragen