Schnittpunkt Gerade

Hallo,

ich habe 5 Punkte gegeben: a,b, x,y,z in R^3

Zwischen a und b soll eine endliche Gerade sein.
x,y,z ist ein beliebiges Dreieck.
(Alles in 3D)

Wie kann ich berechnen, ob und wenn ja an welcher Stelle die Gerade das Dreieck schneidet?

Griffin

Eine endliche Gerade ist ja erstmal eine Strecke. :p
Sonst arbeite mit dem Richtungsvektor der Geraden (so nenne ich das jetzt auch mal)
Ist dieser kollinear zur Ebene in der das Dreieck liegt? Wenn nicht Schneide Gerade und Ebene. Schnittpunkt ermitteln und gucken, ob er Element des Dreiecks ist!

MBCS-CITP

Ich wuerde erst all auf folgendes testen: Schneidet die Gerade durch AB die Ebene die durch die drei Dreieckspunkt (ich nenne sie hier - zur Verirrung und um Verwirrung zu vermeiden) C, D und E und wo. Der Test ist relativ einfach:

Fuer C, D, und E muss gelten:

z = ax + by + c

Du hast dann drei Gleichungen fuer drei Unbekannte. Die beiden Punkte seinen definiert:

A := (x_A | y _A | z _A)
B := (x_B | y _B | z _B)

Zwischen beiden Punkten besteht der Vektor g

g = A - B = (x_A - x_B, y_A - y_B, z_A - z_B)

Fuer jeden Punkt G auf der Gerade muss gelten:

G = A + λ b

Du musst die nun Gleichung der Ebene mit der der Geraden gleichsetzen. Gibt ein λ, dass dieser Bedingung genuegt, so exitiert ein Schnittpunkt

S = A + λ b = (x_S | y _S | z _S)

Der naechste Test ist, ob dieser Schnittpunkt S auf der Strecke zwischen A und B liegt. Das ist der Fall, wenn λ >= 0 und <= 1 ist.

Letzte Frage: Liegt der Schnittpunkt im Dreieck?

Wir nehmen uns zumaechst zwei Punkte des Dreiecks: C und D.

Fuer die Gerade a durch C und D muss wieder gelten:

a = C + λ(C - D)

Es muss ein Vector b existieren, der von dieser Geraden im rechten Winkel zum Schnittpunkt laeuft. Fuer diesen Vector muss gelten:

a b = 0
b = S - C + λ(C - D)

Dieser ist zu berechnen.

Es muss noch ein zweiter Vector e existieren, der wieder von dieser Geraden im rechten Winkel zum Punkt E geht:

a e = 0
e = E - C + λ(C - D)

Da beide Vectoren die gleiche Orientierung haben, muss gelten:

e = λ a

Wenn λ groesser 1 ist oder kleiner 0 dann kann der Schnittpunkt nicht im Dreieck liegen.

Wenn dieser Test fuer alle drei Geraden CD, DE und EC erfolgreich ist, dann liegt der Schnittpunkt im Dreieck.

PS: Ich hoffe, es findet jemand einen einfacheren weg.

Taurin

MBCS-CITP schrieb:

PS: Ich hoffe, es findet jemand einen einfacheren weg.

Mein Weg ist nicht großartig anders, aber vielleicht etwas einfacher zu rechnen:

Die Strecke S habe die beiden Endpunkte $a,b \in R^3$ .
Das Dreieck D sei gegeben durch die Eckpunkte $c,d,e \in R^3$

Dann liegt jeder Punkt $x = \lambda u + b$ mit $u = a-b$ und \lambda \in [0,1] auf S.

Jeder Punkt $y = \alpha v + \beta w + e$ mit $v = c-e$ , $w = d-e$ , \alpha, \beta \in [0,1] und $\alpha + \beta \leq 1$ . Das Dreieck müsste so stimmen, bin mir aber nicht ganz sicher. Ich geh mal davon aus und mach weiter

Wir suchen den Schnittpunkt von S und D.

$x = y$
$\lambda u + b = \alpha v + \beta w + e$
$\alpha v + \beta w - \lambda u = b - e$
\left(v \ w \ -u\right) \left({{\alpha \atop \beta} \atop \lambda}\right) = b -e

Das ist ein LGS. Wenn es eine Lösung hat, schneiden sich die Gerade, die durch S verläuft und die Ebene, in der das Dreieck D liegt. Prüfen, ob das LGS sich lösen lässt, kann man mit $\det\left(v w -u\right) \neq 0$ .
Wenn es sich lösen lässt, prüfen wir, ob $\alpha, \beta, \lambda$ jeweils zwischen 0 und 1 liegen und ob die Summe $\alpha + \beta$ kleiner oder gleich 1 ist. Wenn ja, dann schneiden sich S und D in dem Punkt $x_s = \lambda u + b$ .

edit: Noch mal zur Deutlichkeit: $\left(v \ w \ -u\right)$ ist die Matrix, die als erste Spalte den Vektor v, als zweite den Vektor w und als letzte Spalte den Vektor -u hat.

edit2: Mir ist eben aufgefallen, dass man auch noch ganz gräßlich den Vorzeichen aufpassen muss. Könnt ihr ja noch mal drüber nachdenken, hab grad leider recht viel zu tun.

MBCS-CITP

Taurin schrieb:

edit2: Mir ist eben aufgefallen, dass man auch noch ganz gräßlich den Vorzeichen aufpassen muss. Könnt ihr ja noch mal drüber nachdenken, hab grad leider recht viel zu tun.

Ich glaube, das ist ein Vorteil meiner Methode. Ich hatte zuerst auch mit wuesten Falizifizierungen herumgespielt, habe dann aber noch einmal nachgedacht, wie die jeweilugen Werte λ verhalten und stellte fest, dass man sich das dann sparen kann.