WaBis

walter.bislins.ch

Schnittpunkt Ebene mit Gerade einfach berechnen (JavaScript)

Donnerstag, 23. März 2017 - 21:23 | Autor: wabis | Themen: Wissen, Mathematik, Geometrie, Programmierung, Animation, Interaktiv
Die hier vorgestellte Methode zum Berechnen des Schnittpunktes einer Ebene mit einer Geraden ist 3 mal effizienter als die allgemeine Methode des Lösens eines Gleichungssystems. Ich beschreibe beide Methoden und stelle ein JavaScript zur Verfügung, welches die schnelle Methode verwendet. Die Korrektheit der schnellen Methode und des JavaScripts wird in einer interaktiven Animation bewiesen.

Aufgabe

Es sollen die Koordinaten eines Schnittpunktes einer Geraden mit einer Ebene berechnet werden. Die Gleichungen für die Gerade und die Ebene lauten:

(1)
\vec X = \vec P + a \cdot \vec r

Geraden-Gleichung

(2)
\vec X = \vec Q + b \cdot \vec u + c \cdot \vec v

Ebenen-Gleichung

wobei'
\vec P ' =' 'Punkt auf der Geraden
\vec r ' =' 'Richtung der Geraden
\vec Q ' =' 'Punkt auf der Ebene
\vec u, \vec v ' =' 'Zwei nicht parallele Vekroren auf der Ebene

Lösung durch Koordinatentransformation

Ich kann den Schnittpunkt mit zwei unterschiedlichen Methoden berechnen.

  1. Aufstellen und Lösen eines Gleichungssystems mit 3 Unbekannten → Gleichungssystem lösen
  2. Transformation der Geraden in das Koordinatensystem der Ebene

Die hier vorgestellte Methode (2) erweist sich als einfacher und effizienter (20 Operationen pro Schnittpunkt) als die Methode des Lösens eines Gleichungssystems (ca. 60 Operationen pro Schnittpunkt).

Übersicht der Punkte und Vektoren

Die Idee ist folgende: Die Ebene kann als Koordinatensystem aufgefasst werden, welches durch die Einheits-Vektoren \vec u, \vec v und \vec n = \vec u \times \vec v definiert ist. Der Punkt \vec Q der Ebene soll der Ursprung dieses Korrdinatensystems sein. Wenn ich die Gerade in dieses Koordinatensystem transformiere, kann der Parameter a sehr einfach berechnet werden. Die anderen Parameter b und c benötige ich nicht.

Ich gehe davon aus, dass die beiden Vektoren \vec u und \vec v, welche in der Eben liegen, Einheitsvektoren sind und einen Winkel von 90° aufspannen. Der Vektor \vec n steht senkrecht auf der Ebene und kann über das Kreuzprodukt aus den Vektoren \vec u und \vec v berechnet werden. Da \vec u und \vec v Einheitsvektoren sind, ist auch \vec n ein Einheitsvektor.

Die Gerade wird in das Koordinatensystem der Ebene transformiert, indem die Skalarprodukte der Geraden-Vektoren \vec P - \vec Q und \vec r mit den drei Basisvektoren der Ebene berechnet werden. Die Skalarprodukte entsprechen den Projektionen der Geradenvektoren auf diese Basisvektoren.

Da der Ebenenpunkt \vec Q der Ursprung des Ebenen-Koordinatensystems ist, muss ich den Punkt \vec P der Geraden bezüglich dieses Punktes berechnen:

(3)
\vec {QP} = \vec P - \vec Q

Der Punkt \vec P hat dann bezüglich des Ebenen-Koordinatensystems die folgenden Komponenten:

(4)
\vec P^{\,\prime} = \pmatrix{ \vec {QP} \cdot \vec u \\ \vec {QP} \cdot \vec v \\ \vec {QP} \cdot \vec n }

Der Richtungsvektor \vec r der Geraden bezüglich des Ebenen-Koordinatenssystems wird analog berechnet:

(5)
\vec r^{\,\prime} = \pmatrix{ \vec r \cdot \vec u \\ \vec r \cdot \vec v \\ \vec r \cdot \vec n }

Die Vektoren der Ebene im Ebenen-Koordinatensystem sind trivial:

(6)
\vec Q^{\,\prime} = \pmatrix{ 0 \\ 0 \\ 0 } \qquad \vec u^{\,\prime} = \pmatrix{ 1 \\ 0 \\ 0 } \qquad \vec v^{\,\prime} = \pmatrix{ 0 \\ 1 \\ 0 } \qquad \vec n^{\,\prime} = \pmatrix{ 0 \\ 0 \\ 1 }

Beschreiben wir nun die Ebene und Gerade bezüglich des Ebenen-Koordinatensystems:

(7)
\vec X^{\,\prime} = \vec P^{\,\prime} + a \cdot \vec r^{\,\prime}

Geradengleichung

(8)
\vec X^{\,\prime} = \vec Q^{\,\prime} + b \cdot \vec u^{\,\prime} + c \cdot \vec v^{\,\prime}

Ebenengleichung

Der Schnittpunkt \vec S^{\,\prime} im Ebenen-Koordinatensystem ist jener Punkt, der beide Gleichungen erfüllt:

(9)
\vec S^{\,\prime} = \vec P^{\,\prime} + a \cdot \vec r^{\,\prime} = \vec Q^{\,\prime} + b \cdot \vec u^{\,\prime} + c \cdot \vec v^{\,\prime}

Etwas Umstellen ergibt:

(10)
-a \cdot \vec r^{\,\prime} + b \cdot \vec u^{\,\prime} + c \cdot \vec v^{\,\prime} = \vec P^{\,\prime} - \vec Q^{\,\prime}

Ausschreiben der Vektoren ergibt das Gleichungssystem:

(11)
-a \cdot \pmatrix{ r_1^{\,\prime} \\ r_2^{\,\prime} \\ r_3^{\,\prime} } + b \cdot \pmatrix{ u_1^{\,\prime} \\ u_2^{\,\prime} \\ u_3^{\,\prime} } + c \cdot \pmatrix{ v_1^{\,\prime} \\ v_2^{\,\prime} \\ v_3^{\,\prime} } = \pmatrix{ P_1^{\,\prime} \\ P_2^{\,\prime} \\ P_3^{\,\prime} } - \pmatrix{ Q_1^{\,\prime} \\ Q_2^{\,\prime} \\ Q_3^{\,\prime} }

Einsetzen der Zahlenwerte für die Vektoren ergibt (\vec Q^{\,\prime} = 0):

(12)
-a \cdot \pmatrix{ r_1^{\,\prime} \\ r_2^{\,\prime} \\ r_3^{\,\prime} } + b \cdot \pmatrix{ 1 \\ 0 \\ 0 } + c \cdot \pmatrix{ 0 \\ 1 \\ 0 } = \pmatrix{ P_1^{\,\prime} \\ P_2^{\,\prime} \\ P_3^{\,\prime} }

Aus der letzten Zeile dieses Gleichungssystems können wir direkt den Wert a berechnen:

(13)
-a \cdot r_3^{\,\prime} = P_3^{\,\prime} \qquad \Rightarrow \qquad a = -{ P_3^{\,\prime} \over r_3^{\,\prime} }

Wenn a bekannt ist, können wir den Schnittpunkt im Ebenen-Koordinatensystem berechnen:

(14)
\vec S^{\,\prime} = \vec P^{\,\prime} + a \cdot \vec r^{\,\prime}

Die Rücktransformtion ins ursprüngliche Koordinatensystem erfolgt über die Basisvektoren \vec u, \vec v und \vec n wiefolgt:

(15)
\vec S = \vec Q + S_1^{\,\prime} \cdot \vec u + S_2^{\,\prime} \cdot \vec v + S_3^{\,\prime} \cdot \vec n

Da wir immer mit Einheitsvektoren und orthogonalen Basis-Vektoren gerechnet haben ist der Parameter a in beiden Koordinatensystemen identisch. So können wir den Schnittpunkt auch direkt berechnen:

(16)
\vec S = \vec P + a \cdot \vec r

Zusammenfassung

Wenn wir den oben aufgezeigten Weg zusammenfassen, erkennen wir, dass viele Berechnungen eingespart werden konnten. Die verbliebenen Berechnungen fasse ich hier nochmals zusammen:

Übersicht der Punkte und Vektoren

Zunächst benötigen wir den Normalenvektor auf die Ebene:

(17)
\vec n = \vec u \times \vec v

Diese Vektoren bilden die Basis des Ebenen-Koordinatensystems. Um die Vektoren der Geraden in diesem System auszudrücken können wir das komponentenweise Skalarprodukt der Vektoren mit den Basisvektoren verwenden wie in (4) und (5) gezeigt. Wir benötigen jedoch nur die 3. Komponente für die Berechnung von a:

(18)
P_3^{\,\prime} = (\vec P - \vec Q) \cdot \vec n \qquad\qquad r_3^{\,\prime} = \vec r \cdot \vec n

Damit können wir den parameter a berechnen:

(19)
a = - { P_3^{\,\prime} \over r_3^{\,\prime} }

und erhalten den Schnittpunkt:

(20)
\vec S = \vec P + a \cdot \vec r

Beachte: Wenn die Richtung der Geraden, ausgedrückt durch den Vektor \vec r, parallel zur Ebene ist, gibt es keinen Schnittpunkt. Dies äussert sich darin, dass r_3^{\,\prime} = 0 wird, da das Skalarprodukt von \vec r mit dem Normalenvektor \vec n Null ist, wenn diese beiden Vektoren einen 90° Winkel bilden, was bei einer zur Ebene parallelen Geraden der Fall ist.

JavaScript IntersectPlaneLine

// some vector functions

function VectProd( u, v ) {
  // Vector Product: return = u x v
  // u, v: [ x, y, z ]
  // return: [ x, y, z ]
  return [ 
    u[1] * v[2] - u[2] * v[1],
    u[2] * v[0] - u[0] * v[2],
    u[0] * v[1] - u[1] * v[0]
  ];
}

function VectScalProd( u, v ) {
  // Scalar Product: return = u dot v
  // u, v: [ x, y, z ]
  // return: number
  return u[0] * v[0] + u[1] * v[1] + u[2] * v[2];
}

function VectAdd( u, v ) {
  // Vector addition: return = u + v
  // u, v: [ x, y, z ]
  // return: [ x, y, z ]
  return [ u[0] + v[0], u[1] + v[1], u[2] + v[2] ];
}

function VectSub( u, v ) {
  // Vector subtraction: u - v
  // u, v: [ x, y, z ]
  // return: [ x, y, z ]
  return [ u[0] - v[0], u[1] - v[1], u[2] - v[2] ];
}

function VectScale( v, s ) {
  // Vector scaling: s * vec v
  // v: [ x, y, z ]
  // s: number
  // return: [ sx, sy, sz ]
  return [ s * v[0], s * v[1], s * v[2] ];
}

function IntersectPlaneLine( Q, u, v, P, r ) {
  // All parameters are Arrays [ x, y, z ]
  // Q = point on plane
  // u, v = orthogonal unit vectors on plane
  // P = point on line
  // r = direction of line
  // return = intersection point [ x, y, z] or null

  var n = VectProd( u, v );
  var r3 = VectScalProd( r, n );
  if (r3 == 0) return null;
  var P3 = VectScalProd( VectSub( P, Q ), n );
  var a = -P3 / r3;
  var S = VectAdd( P, VectScale( r, a ) );
  return S;
}

Rundungs-Probleme

Wenn man einen Algorythmus zum Clippen eines Polygons schreibt, wird man vor dem Berechnen des Schnittpunktes testen, ob sich zwei Punkte des Polygons auf verschiedenen Seiten der Fläche befinden, also ob es einen Schnittpunkt gibt. Durch Rundungsfehler kann es passieren, dass der Test zurückgibt, dass zwei Punkte auf verschiedenen Seiten der Fläche sind, aber beim Berechnen des Schnittpunktes festgestellt wird, dass es keinen Schnittpunkt gibt, so dass IntersectPlaneLine() null zurückgibt.

Dieser Fall muss unbedingt behandelt werden, da es sonst zu Exceptions kommen kann. Eine Möglichkeit ist, die beiden Punkte als auf derselben Seite zu betrachten.

Animation

In der folgenden Animation wird die obige JavaScript Funktion für die Berechnung des Schnittpunktes (grün) verwendet. Durch Klicken in die Animation werden zufällige Werte für eine neue Konfiguration generiert.

Gleichungssystem lösen

Eine allgemeinere Methode den Schnittpunkt von Gerade und Ebene zu berechnen ist das Aufstellen und Lösen eines Gleichungssystems:

Für den Schnittpunkt \vec S gilt, dass er sowohl auf der Geraden, als auch auf der Ebene liegen muss. Der Punkt erfüllt also die Geraden- und Ebenengleichung gleichzeitig. Um ihn zu berechnen, werden die beiden Gleichungen einander gleichgestellt. Man erhält dadurch 3 Gleichungen für die drei Unbekannten Parameter a, b, c. Sind diese Parameter berechnet, kann man sie einfach in eine der beiden Gleichungen einsetzen und man erhält damit den Schnittpunkt.

(21)
\vec S = \vec P + a \cdot \vec r

Geraden-Gleichung

(22)
\vec S = \vec Q + b \cdot \vec u + c \cdot \vec v

Ebenen-Gleichung

Setzen wir also Gleichung (19) gleich (20) und schreiben diese für jede Koordinate einzeln:

(23)
P_i + a \cdot r_i = Q_i + b \cdot u_i + c \cdot v_i

für i = 1...3

Wir stellen die Gleichung (23) so um, dass alle Terme mit den Unbekannten a, b, c auf der linken Seite und alle anderen Terme auf der rechten Seite des Gleichheitszeichens stehen:

(24)
r_1 \cdot a - u_1 \cdot b - v_1 \cdot c = Q_1 - P_1
(25)
r_2 \cdot a - u_2 \cdot b - v_2 \cdot c = Q_2 - P_2
(26)
r_3 \cdot a - u_3 \cdot b - v_3 \cdot c = Q_3 - P_3

Dieses lineare Gleichungssystem mit 3 Gleichungen für die 3 Unbekannten a, b, c können wir in Matrixschreibweise notieren:

(27)
\pmatrix{ r_1 & -u_1 & -v_1 \\ r_2 & -u_2 & -v_2 \\ r_3 & -u_3 & -v_3 } \cdot \pmatrix{ a \\ b \\ c } = \pmatrix{ Q_1 - P_1 \\ Q_2 - P_2 \\ Q_3 - P_3 }

Auf der Seite Lösen linearer Gleichungssysteme wird berschrieben, wie ein solches Gleichungssystem per JavaScript gelöst werden kann. Wenn a berechnet ist, kann der Schnittpunkt durch Einsetzen in die Geradengleichung (21) vektoriell berechnet werden.

Dein Kommentar zu diesem Artikel
Name
Email optional; wird nicht angezeigt
Kommentar
  • Name wird bei deinem Kommentar angezeigt.
  • Email ist nur für den Administrator, sie wird nicht angezeigt.
  • Du kannst deine Kommentare eine Zeit lang editieren oder löschen.
  • Du kannst Formatierungen im Kommentar verwenden, z.B: Code, Formeln, usw.
  • Externen Links und Bilder werden nicht angezeigt, bis sie der Admin freischaltet.
Weitere Infos zur Seite
Erzeugt Dienstag, 21. März 2017
von wabis
Zum Seitenanfang
Geändert Dienstag, 27. Juni 2017
von wabis