WaBis

walter.bislins.ch

Schnittpunkt zweier Geraden berechnen (JavaScript)

Samstag, 14. Februar 2015 - 15:05 | Autor: wabis | Themen: Wissen, Geometrie, Programmierung, Animation, Interaktiv
Wie berechnet man den Schnittpunkt zweier Geraden mit Vektor-Geometrie?

Ich zeige, wie durch Wahl eines geeigneten Koordinatensystems die Berechnung des Schnittpunktes zweier Geraden vereinfacht wird. Ich leite die Formeln her und erstelle ein JavaScript, welches den Schnittpunkt zweier Geraden berechnet. Eine interaktive Animation zeigt das JavaScript in Aktion.

Aufgabe

Gegeben seien zwei Geraden g1 und g2 in Vektorform. Das heisst die Gerade g1 geht durch den Punkt \vec P und hat die Richtung des Einheitsvektors \vec r, die Gerade g2 geht durch den Punkt \vec Q und hat die Richtung des Einheitsvektors \vec s.

Gesucht ist der Schnittpunkt \vec O der beiden Geraden.

Vereinfachung der Aufgabe

Durch Wahl eines geeigneten Koordinatensystems K' lässt sich die Aufgabe vereinfachen:

Ich wähle die Gerade g1 als X-Achse des Koordinatensystems K' und den Punkt \vec P als seinen Ursprung. Dann transformiere ich die Gerade g2, d.h. den Punkt \vec Q und die Richtung \vec s, in das System K'. Jetzt muss nur berechnet werden, bei welchem X-Wert a die Gerade g2 die X-Achse schneidet. Dies ergibt den Punkt \vec O', welcher auf der X-Achse von K' liegt. Diesen Punkt muss ich nun wieder ins Koordinatensystem K zurück transformieren und ich erhalte damit den Schnittpunkt \vec O der beiden Geraden.

Für die beiden Geraden gelten die folgenden Geraden-Gleichungen:

(1)
\vec V_1 = \vec P + \lambda_1 \cdot \vec r
(2)
\vec V_2 = \vec Q + \lambda_2 \cdot \vec s
wobei'
\vec V_1 ' =' 'alle Punkte, welche auf der Geraden g1 liegen
\vec P ' =' 'ein beliebiger Punkt der Geraden g1
\lambda_2 ' =' 'Laufvariable für Gerade g1
\vec r ' =' 'Richtung der Geraden g1 als Einheitsvektor
\vec V_2 ' =' 'alle Punkte, welche auf der Geraden g2 liegen
\vec Q ' =' 'ein beliebiger Punkt der Geraden g2
\lambda_2 ' =' 'Laufvariable für Gerade g2
\vec s ' =' 'Richtung der Geraden g2 als Einheitsvektor

Transformation ins Koordinatensystem K'

Skizze Schnittbild zweier Linien 
(Klick: Zoom)

Die Gerade g1 bildet die X-Achse des Koordinatensystems K' mit dem Ursprung beim Punkt \vec P. Im System K' hat somit die Gerade g1 den Punkt \vec P' beim Nullpunkt und die Richtung \vec r' entspricht dem Einheitsvektor \vec e'_\mathrm{x} der X-Achse von K'.

Den Punkt \vec Q und die Richtung \vec s kann ich mit Hilfe des Skalarproduktes ins System K' abbilden:

(3)
q'_\mathrm{x} = (\vec Q - \vec P) \cdot \vec r \ \qquad\ q'_\mathrm{y} = (\vec Q - \vec P) \cdot \vec r_\mathrm{t}
mit
\vec Q' = \pmatrix{ q'_\mathrm{x} \\ q'_\mathrm{y} } \qquad\qquad \vec r_\mathrm{t} = \pmatrix{ 0 & -1 \\ 1 & 0 } \cdot \vec r
wobei'
q'_\mathrm{x} ' =' 'X-Komponente des Punktes \vec Q im System K'
q'_\mathrm{y} ' =' 'Y-Komponente des Punktes \vec Q im System K'
\vec r ' =' 'Richtung der X-Achse des Systems K' bezüglich K
\vec r_\mathrm{t} ' =' 'Um 90° im Gegenuhrzeigersinn gedrehter Vektor \vec r bezüglich K

Die Richtung \vec s der Geraden g2 lässt sich analog transformieren:

(4)
s'_\mathrm{x} = \vec s \cdot \vec r \qquad\qquad s'_\mathrm{y} = \vec s \cdot \vec r_\mathrm{t}
mit
\vec s' = \pmatrix{ s'_\mathrm{x} \\ s'_\mathrm{y} }
wobei'
s'_\mathrm{x} ' =' 'X-Komponente der Richtung \vec s im System K'
s'_\mathrm{y} ' =' 'Y-Komponente der Richtung \vec s im System K'

Damit erhalte ich zwei neue Geradengleichungen im System K':

(5)
\vec V'_1 = \pmatrix{ 0 \\ 0 } + \lambda_1 \cdot \pmatrix{ 1 \\ 0 }

Linie g1

(6)
\vec V'_2 = \pmatrix{ q'_\mathrm{x} \\ q'_\mathrm{y} } + \lambda_2 \cdot \pmatrix{ s'_\mathrm{x} \\ s'_\mathrm{y} }

Linie g2

Für den Schnittpunkt \vec O' gilt \vec V'_1 = \vec V'_2 = \vec O':

(7)
\vec O' = \pmatrix{ 0 \\ 0 } + a \cdot \pmatrix{ 1 \\ 0 }

Linie g1

(8)
\vec O' = \pmatrix{ q'_\mathrm{x} \\ q'_\mathrm{y} } + b \cdot \pmatrix{ s'_\mathrm{x} \\ s'_\mathrm{y} }

Linie g2

Die Werte a und b erhalte ich, wenn ich die beiden obigen Gleichungen einander gleichsetze:

(9)
\pmatrix{ 0 \\ 0 } + a \cdot \pmatrix{ 1 \\ 0 } = \pmatrix{ q'_\mathrm{x} \\ q'_\mathrm{y} } + b \cdot \pmatrix{ s'_\mathrm{x} \\ s'_\mathrm{y} }

Die obige Gleichung in die beiden Komponenten zerlegt:

(10)
0 + a \cdot 1 = q'_\mathrm{x} + b \cdot s'_\mathrm{x}
0 + a \cdot 0 = q'_\mathrm{y} + b \cdot s'_\mathrm{y}

Vereinfacht:

(11)
a = q'_\mathrm{x} + b \cdot s'_\mathrm{x}
(12)
0 = q'_\mathrm{y} + b \cdot s'_\mathrm{y}

Daraus lassen sich direkt die beiden Variablen a und b berechnen:

(13)
b = - { q'_\mathrm{y} \over s'_\mathrm{y} }
(14)
a = q'_\mathrm{x} - q'_\mathrm{y} \cdot { s'_\mathrm{x} \over s'_\mathrm{y} }

Um den Schnittpunkt \vec O im System K zu erhalten, muss ich nur den Wert λ1 = a in die Geradengleichung (1) für die Gerade g1 einsetzen:

(15)
\vec O = \vec P + a \cdot \vec r

JavaScript IntersectLines

Dem JavaScript müssen die beiden Punkte \vec P und \vec Q, sowie die beiden Richtungen \vec r und \vec s übergeben werden. Die Vektoren werden als zweidimensionales Array der Form [ x, y ] übergeben. Als Resultat wird der Schnittpunkt \vec O der beiden Geraden als [ Ox, Oy ] Array zurückgegeben.

Wenn sich die Geraden nicht schneiden oder identisch sind, wird null zurückgegeben.

function IntersectLines( P, r, Q, s ) {
  // line1 = P + lambda1 * r
  // line2 = Q + lambda2 * s
  // r and s must be normalized (length = 1)
  // returns intersection point O of line1 with line2 = [ Ox, Oy ] 
  // returns null if lines do not intersect or are identical
  var PQx = Q[0] - P[0];
  var PQy = Q[1] - P[1];
  var rx = r[0];
  var ry = r[1];
  var rxt = -ry;
  var ryt = rx;
  var qx = PQx * rx + PQy * ry;
  var qy = PQx * rxt + PQy * ryt;
  var sx = s[0] * rx + s[1] * ry;
  var sy = s[0] * rxt + s[1] * ryt;
  // if lines are identical or do not cross...
  if (sy == 0) return null;
  var a = qx - qy * sx / sy;
  return [ P[0] + a * rx, P[1] + a * ry ];
}

Animation

Der rote Kreis ist der vom JavaScript berechnete Schnittpunkt.

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 Montag, 19. Januar 2015
von wabis
Zum Seitenanfang
Geändert Donnerstag, 4. Mai 2017
von wabis