Einiges zur Geometrie (Punkte, Vektoren, Geraden)

[Beni]

Vektoren & Punkte

Praktisch in jedem Spiel muss man sich mit Vektoren und Punkten herumschlagen. Eine gute Gelegenheit die wichtigsten Begriffe und Formeln kennenzulernen (ich versuch hier wirklich nur das aufzulisten, was man benötigt, oder was das Leben erleichtert).

Dabei soll sich dieser Text auf 2- und 3-dimensionale Räume beschränken, und es soll auch nur immer ein rechtwinkliges, normiertes Koordinatensystem benutzt werden (einige der Formeln die hier gezeigt werden, gelten auch nur unter diesen Bedingungen).

P.S. Ich mache im Text immer ein Strich unter die Vektoren und Punkte damit man sie auch erkennt. Alles was kein Strich hat, ist auch kein Vektor oder Punkt.

Punkte
Punkte sind ganz einfach eine Angabe "soviele Schritte in x-Richtung, soviele in y-Richtung, dann bist Du am Ziel." Punkte sind also einfach ein Zahlenpaar (oder ein Zahlentrippel im 3D-Fall), und werdem meist so geschrieben:

im 2D-Fall: (x, y)
im 3D-Fall: (x, y, z)

wobei x, y, z irgendwelche Zahlen sein können (man nennt x, y und z auch "Koordinaten", in seltenen Fällen "Komponenten")

Natürlich gibt es auch Punkte die keine ganzen Zahlen als Koordinaten haben, zum Beispiel (1.235, 67.89).

Vektoren
Vektoren kann man auch mit "Richtung" übersetzen. Auch sie sind Zahlenpaare (Zahlentrippel), und werden genau gleich wie Punkte aufgeschrieben:

im 2D-Fall: (x, y)
im 3D-Fall: (x, y, z)

wobei x, y, z irgendwelche Zahlen (auch 0) sein können (man nennt x, y und z auch "Komponenten")

Einige Vektoren:

Das hier sind dieselben Vektoren, da es ja nur um die Richtung, und nicht den Anfang geht:

Vektoren kann man addieren, subtrahieren und skalieren:

Die Addition ist denkbar einfach:

a + b =
(ax, ay) + (bx, by) =
(ax + bx, ay + by)

Die Subtraktion ist genau gleich:

a - b =
(ax, ay) - (bx, by) =
(ax - bx, ay - by)

Auch das Skalieren (bzw. Multiplizieren) ist kein grosses Problem:

c*a =
c * (ax, ay) =
(c*ax, c*ay)

Vektortypen
Manchmal wird zwischen 2 Arten Vektoren unterschieden: Richtungsvektoren und Ortsvektoren.

• Richtungsvektoren: sie beschreiben eine Richtung. So wie "Osten" keinen Anfangspunkt hat, haben auch Richtungsvektoren keinen Anfangspunkt.
• Ortsvektoren: sind eng mit Punkten verwandt. Sie sind an einem Punkt (meist dem Nullpunkt) "befestigt", und beschreiben selbst einen Punkt, der gegenüber dem Ursprung (des Ortsvektors) verschoben ist.

Diese Unterscheidung wird im folgenden Text nicht weiter beachtet.

Einige Formeln & Definitionen zu Vektoren

• Der Nullvektor
  Der Vektor (0, 0) (oder (0, 0, 0)) heisst Nullvektor. Er hat einige spezielle Eigenschaften, die jeweils "vor Ort" gezeigt werden.
• Die Länge
  Die Länge eines Vektors ist definiert als:
  

  a = (x, y)
  |a| = sqrt( x*x + y*y ) //sqrt bedeutet einfach Wurzel
  

  ... was nichts anderes als der Phytagorassatz ist.
  
  (Die Striche || bedeuten, dass die Länge des Vektors gemeint ist)
  
  Mit der Methode Math.hypot lässt sich die Länge in Java bequem berechnen.
  
  Oder für 3D:
  

  b = (x, y, z)
  |b| = sqrt( x*x + y*y + z*z )

  
  
  
  
  
  [list:fc923fe8f9]
• Ein Vektor mit der Länge 1 wird "normierter Vektor" oder "Einheitsvektor" genannt.
  Es gibt zu jedem Vektor (Ausnahme: Nullvektor) einen Einheitsvektor, der genau in dieselbe Richtung zeigt. Und zwar ist das:
  

  a = (x, y, z)
  ea = a / |a|

• Der Nullvektor 0 hat die Länge 0, alle anderen Vektoren haben eine Länge > 0.

[*]Das Skalarprodukt
Das Skalarprodukt ist das Resultat der (skalaren) Multiplikation von Vektoren.
Dazu werden die Komponenten paarweise multipliziert, und danach addiert:

a = (ax, ay), b = (bx, by)
s = a*b = (ax, ay)*(bx, by) = ax*bx + ay*by

Genau gleich in 3 Dimensionen:

a = (ax, ay, az), b = (bx, by, bz)
s = a*b = (ax, ay, az)*(bx, by, bz) = ax*bx + ay*by + az*bz

• Es gilt:
  

  |a| * |a| = a * a

• Der Nullvektor wird seinem Namen gerecht:
  

  0 * v = (0, 0) * (x, y) = 0 + 0 = 0

• Es gibt eine andere Schreibweise für das Skalarprodukt, welche auch oft zu finden ist:
  

  a * b = <a, b>

[*]Der Winkel
Der Winkel zwischen zwei Vektoren ist gegeben durch:

cos w = ( a * b )/( |a| * |b| ) // w ist der Winkel, "cos" ist die Winkelfunktion "Cosinus"

• Rechnet man nur mit Einheitsvektoren, kann man das Teilen weglassen, denn:
  

  ( a * b )/( |a| * |b| ) = ( a / |a| ) * ( b / |b| ) // und da |a| = |b| = 1...

• Das Skalarprodukt von zwei Vektoren die normal (auch "senkrecht" genannt) zueinander sind, ist 0.
• Da das Skalarprodukt des Nullvektors mit irgendeinem anderen Vektor 0 gibt, muss der Nullvektor normal zu jedem anderen Vektor sein. Da man dem Nullvektor keine Richtung zuordnen kann, ist das aber noch akzeptabel.
• Der Normalvektor zu einem beliebigen Vektor lässt sich folgendermassen berechnen (nur in 2D):
  

  a = (ax, ay)
  b = (ay, -ax)
  
  oder
  
  b = (ay, -ax) * t // wobei t ein beliebig wählbarer Wert ist. t skaliert b einfach, das ändert aber nichts am Winkel

• Durch Umkehren der Winkelgleichung kann man den Innenwinkel (derjenige Winkel der kleiner oder gleich 90° ist) zweier Vektoren berechnen:
  

  w1 = acos( (a * b) / (|a| * |b|) ) // wobei acos die Funktion Arcus Cosinus meint

• Der Aussenwinkel (der Winkel der grösser oder gleich pi/2 ist), ist dann:
  

  w2 = 2*pi - w1

(In Java wird mit dem Bogenmass (english: radians) gerechnet. Die Umrechnung Bogenmass - Winkelmass kann mit einem Dreisatz gelöst werden, wobei man "2*pi = 360°" setzt.)

[*]Parallel / Antiparallel
Zwei Vektoren sind parallel, wenn sie in dieselbe Richtung zeigen, aber unterschiedlich lang sind:

a = (ax, ay), b = (bx, by)
a = t * b

//oder auch:
ax = t*bx
ay = t*by

Falls der Wert t < 0 ist, spricht man auch von antiparallel.
Falls t = 0 ist, ist entweder a oder b der Nullvektor. Natürlich ist der Nullvektor parallel zu allen Vektoren, aber er ist auch gleichzeitig normal zu allen Vektoren. Seltsame Sache, aber es funktioniert.

[*]Das Vektorprodukt (Kreuzprodukt)
Das Vektorprodukt kann nur in 3 Dimensionen berechnet werden. Das Resultat dieser Multiplikation zweier Vektoren ist ein neuer Vektor, der normal zu den beiden Originalen ist.

Das Vektorprodukt (mit dem Zeichen "x")

c = a x b

cx = ay*bz - az*by
cy = az*bx - ax*bz
cz = ax*by - ay*bx

Und es gilt:

a * c = 0
b * c = 0

Der Vektor c ist also normal zu den Vektor a und b.

Falls die beiden Vektor parallel oder antiparallel sind, ist die Länge des Vektorproduktes = 0, und damit ist es sicher normal zu den beiden Vektoren, auch wenn es keine eindeutige Richtung hat.

[/list:u:fc923fe8f9]

Philosophie: Der Unterschied zwischen Punkt und Vektor?
Oft sagt man: der Punkt ist ein Gebilde, das einen festen Platz im Raum hat, der Vektor ist eine Richtung.
Diese Trennung kann man machen (und sie ist meistens auch sinnvoll), aber man sollte daran denken, dass Punkt und Vektor eigentlich beide nur eine geordnete Menge von Zahlen sind.
Von diesem Standpunkt gesehen, kann man aber sagen, dass Punkt und Vektor zwei Wörter für ein und dasselbe sind, und man einen Punkt durch einen Vektor (und umgekehrt) vertauschen kann, ohne dass sich das Ergebnis der Gleichung verändert.
Nur die fixe Vorstellung, Punkte und Vektoren als geometrische Gebilde zu sehen, kann einem am auffinden eleganter und schneller Lösungen hindern!

 

[Beni]

Geraden

Geraden in 2D

• Einfache Darstellung
  Die wohl einfachste, und auch bekannteste Art eine Gerade darzustellen, ist die Steigung (m) und den y-Achsenabschnit (q) anzugeben:
  

  y = m x + q

  
  Hat man zwei Punkte (x0, y0) und (x1, y1) gegeben, kann man das Ganze folgendermassen ausrechnen:
  

  dx = x0 - x1
  dy = y0 - y1
  
  m = dy / dx
  q = y0 - m * x0

  
  Der Nachteil ist, dass diese Darstellung keine Geraden parallel zur y-Achse erlaubt. Bei einem Computer können auch Geraden die sehr steil sind Probleme verursachen (z.B. ein Überlauf bei der Berechnung von m * x0).
  
• Komplizierte Darstellung
  Man kann eine Gerade auch als Punkt (a) mit einer Richtungsangabe (b) betrachten.
  Dann gilt:
  

  Punkt p ist Teil der Geraden genau dann wenn:
  p = a + t*b // t ist eine beliebige Zahl

  
  Die Berechnung dieser Darstellung aus zwei Punkten geht schnell, aber alle weiteren Gleichungen werden zur Qual, da man hier mit sehr vielen Variablen rechnen muss.
  
  Allerdings bietet diese Darstellung die Möglichkeit ein 1-dimensionales Koordinatensystem aufzubauen. Denn jeder Punkt auf der Geraden ist durch den Wert von t definiert. Es ist so einfach, Teilabschnitte der Geraden anzugeben (z.B.: 12 <= t <= 15).
  
  Und es gibt keine Probleme mit Geraden die parallel zur y-Achse sind.
  
• Raffinierte Darstellung
  
  Die Darstellung die die meisten Vorteile bietet, sieht so aus:
  

  a*x + b*y + c = 0

  a, b und c sind konstante Werte
  x und y sind die Koordinaten irgendwelcher Punkte. Alle Punkte, die die Gleichung erfüllen, liegen auf der Geraden.
  
  (Die Vorteile: keine Probleme mit Überläufen, da man die Zahlen immer skalieren kann. Dennoch werden nicht soviele Werte wie bei der Darstellung mit Punkt und Vektor benötigt.
  Es gibt auch einige einfache Formeln, z.B. kann man den Normalvektor auf die Gerade ohne eine Rechnung erhalten.)
  
  [list:e0c74be942]
• Berechnen
  
  Mit folgender Formel kann man die Werte für a,b und c für eine Gerade berechnen, welche durch die beiden Punkte u und v gehen soll.
  
  

  dx = ux - vx
  dy = uy - vy
  
  a = dy
  b = -dx
  
  c = -(a*ux + b*uy)

  
  (Der Beweis dass diese Formel stimmt ist einfach: beide Punkte einsetzten, und die Formel fällt auseinander.
  
  
  Hat man einen Punkt p und eine Richtung v gegeben, ist die Sache noch einfacher:
  
  
  

  a = vy
  b = -vx
  
  c = -(a*px + b*py)

• Einige Spezialfälle
  Welche Bedeutung haben a = 0, b = 0, c = 0 oder eine Kombination davon?
  
  Falls c = 0 ist geht die Gerade durch den Ursprung (Nullpunkt), da a*0 + b*0 + 0 = 0 ist.
  
  Falls a = 0 und b != 0 sind, kann man für x einen beliebigen Wert einsetzen (weil 0*x = 0), aber y ist konstant. Daher bedeutet a = 0, dass die Gerade parallel zur y-Achse ist.
  
  Falls a != 0 und b = 0 sind, ist die Gerade parallel zur x-Achse.
  
  Falls a = 0 und b = 0 sind, reduziert sich die Gleichung auf 0*x + 0*y + c = c = 0
  Ist dann c != 0, gibt es keine Punkte, welche die Gleichung erfüllen.
  Ist c hingegen = 0, kann jeder Punkt die Gleichung erfüllen.
  In beiden Fällten bedeutet es, dass die Gleichung etwas anderes als ein Gerade beschreibt, eine unerschöpfliche Fehlerquelle...
  
• Identische Geraden
  Die folgenden beiden Gleichungen beschreiben dieselben Geraden:
  

  2x + 3y + 5 = 0
  4x + 6y + 10 = 0

  Es ist klar: bei der unteren Gleichung 2 ausklammern und wegkürzen, und schon hat man die obere Gleichung.
  
  Allgemein kann man sagen: 2 Geraden sind identisch, falls:
  

  a0 / a1 = b0 / b1 = c0 / c1
  
  // Es kann Probleme geben, falls eine oder mehrere der Variablen 0 sind.
  // Eine besserer Test benutzt nur Multiplikationen:
  a0*b1 = b0*a1 und
  b0*c1 = c0*b1 und
  a0*c1 = c0*a1

  (Ich danke Redfrettchen, der hier einen bösen Fehler entdeckte)
  
  Wird eine eindeutige Darstellung benötigt, kann man die Werte für a, b und c so wählen, dass der Vektor (a, b, c) die Länge 1 hat. (Alternativ könnte man auch sagen, dass der Vektor (a, b) die Länge 1 haben soll. Das kann vielleicht einmal Vorteile bringen.)
  
• Parallele Geraden
  Zwei Geraden sind genau dann parallel, wenn folgende Gleichung gilt:
  

  a0 / a1 = b0 / b1
  
  // oder auch
  a0 * b1 = a1 * b0 != 0 // ungleich 0, weil sonst z.B. a0 und b1 = 0 sein könnten

• Schnittpunkt
  Für den Schnittpunkt zweier Geraden muss man ein kleines Gleichungssystem lösen:
  
  

  a0*x + b0*y + c0 = 0
  a1*x + b1*y + c1 = 0
  
  // das kann man z.B. folgendermassen weiter auflösen:
  
  a1 / a0 * ( a0 * x + b0 * y + c0) = 0
  a1*x + b1*y + c1 = 0
  
  (b1 - a1 / a0 * b0 ) y + ( c1 - a1 / a0 * c0 ) = 0
  
  y = ( a1 / a0 * c0 - c1 ) / (b1 - a1 / a0 * b0 )
  
  x = (b0 * y + c0) / (-a0)
  
  // Das funktioniert natürlich nur, falls a0 != 0. Andernfalls muss man einen anderen Parameter wählen...

• Normalvektor
  Der Normalvektor auf die Gerade a*x + b*y + c = 0 ist der Vektor (a, b).
  
• Winkel zweier Geraden
  Da (a, b) der Normalvektor auf eine Gerade ist, kann man auch einfach die bekannten Formeln für den Winkel zwischen zwei Vektoren anwenden:
  
  

  n0 = (a0, b0)
  n1 = (a1, b1)

  
  cos w = ( n0 * n1 ) / ( |n0| * |n1| )[/quote]
  
• Abstand Punkt-Gerade
  Man kann den Abstand eines Punktes zu einer Geraden berechnen, indem man den Punkt einfach in die Geradengleichung einsetzt:
  
  

  d = (a*x + b*y + c) / sqrt(a*a + b*b)
  // falls |(a, b)| = 1, kann man die Division weglassen

  
  Der Wert d kann jetzt auch negativ sein. Das Vorzeichen von d gibt an, ob der Punkt auf der einen, oder der anderen Seite der Gerade liegt. Der Absolutwert ist der Abstand.

[/list:u:e0c74be942]

Geraden in 3D

Im 3 dimensionalen gibt es nur eine Möglichkeit eine Gerade darzustellen: mit einem Punkt und einer Richtung.

g = p + t*r // p ist ein Punkt der Geraden, r die Richtung der Geraden.

Ein Punkt g ist nur dann auf der Geraden, falls die Gleichung g = p + t*r aufgelöst werden kann.

• Schnittpunkt
  Der Schnittpunkt zweier Geraden ist ein Punkt, der auf der einen wie auf der anderen Geraden liegt.
  
  Daher muss man folgendes Gleichungssystem auflösen:
  

  g1 = p1+t1*r1
  g2 = p2+t2*r2
  g1 = g2
  
  // und daraus ergibt sich:
  p1+t1*r1 = p2+t2*r2
  
  // oder ausgeschrieben und umgeformt:
  r1x*t1 - r2x*t2 = p2x-p1x
  r1y*t1 - r2y*t2 = p2y-p1y
  r1z*t1 - r2z*t2 = p2z-p1z

  
  In diesem Gleichungssystem sind t1 und t2 die Unbekannten. Es gibt also 3 Gleichungen und 2 Unbekannte, was bedeutet, dass das Gleichungssystem nicht in allen Fällen lösbar ist. Das macht auch Sinn, schliesslich schneiden sich im 3D Geraden nicht immer.
  
• Winkel
  Der Winkel zweier Geraden ist einfach der Winkel zwischen den Richtungsvektoren r1 und r2.
  
• Abstand Punkt - Gerade
  Der Abstand zwischen einem Punkt g und einer Geraden p+t*r ist:
  

  d = |(g-p) x r| / |r

• Transversale / Abstand Gerade - Gerade
  Die kürzeste Verbindung zwischen zwei Geraden hat die Eigenschaft, dass
  - sie die Geraden schneidet
  - einen 90° Winkel mit den Geraden bildet.
  
  Daher kann man die Richtung der kürzesten Verbindung sehr schnell berechnen:
  

  n = r1 x r2 // das Vektorprodukt

  
  Nun benötigt man noch einen Punkt der Geraden um ihre Lage endgültig zu bestimmen.
  Da die Transversale die beiden anderen Geraden schneidet, kann man diesen Punkt ausdrücken durch:
  

  m = p1 + t1 * r1

  
  Und nun kann die normale Formel für das bestimmen von Schnittpunkten verwendet werden:
  
  

  p1 + t1 * r1 + s * n = p2 + t2 * r2 //wobei t1, t2 und s Unbekannte Werte sind

  
  Das lässt sich nun in ein Gleichungssystem packen, für das es sicher eine Lösung gibt:
  

  r1x * t1 - r2x * t2 + nx * s = p2x - p1x
  r1y * t1 - r2y * t2 + ny * s = p2y - p1y
  r1z * t1 - r2z * t2 + nz * s = p2z - p1z

  
  Wenn man nur den kürzesten Abstand kennen möchte, reicht es s zu berechnen. Denn der kürzeste Abstand ist:
  

  d = s / |n|

  
  Und die kürzeste Transversale geht vom Punkt p1 + t1 * r1 zum Punkt p2 + t2 * r2

Danke an Redfrettchen und mic_checker, die Verbesserungsvorschläge gemacht haben

 

[güfgüf]

sehr gute arbeit respekt an alle ..die sich da so bemüht haben!!!

 

[Gast]

nützlich sind auch 4D Vektoren, da man sie dann mit der Translationsmatrix multiplizieren kann.

am aller besten ist es wenn man für all diese mathematischen Elemente Klassen schreibt, so sind sie dann überall einsetzbar, und man erspart sich eine Menge arbeit

 

[Developer_X]

jetzt fehlt nur noch ein Tutorial zu 4 Dimensionalen Raumzeit ^^

gute Arbeit, euer Tutorial ist super.

 

[Marco13]

Eigentlich passt in diesen Thread noch der Hinweis auf https://vecmath.dev.java.net/ , was z.B. schon die ganzen Klassen Point3f, Vector3f, Matrix4f usw. enthält. Die JAR gibt's mit Java3D.

 

[moormaster]

Sollte das nicht in die FAQ verschoben werden oder wenigsten ein Sticky werden?

 

[Illuvatar]

http://www.java-forum.org/spiele-und-multimedia-programmierung/6529-tutorials.html *hust*

 

[Quaxli]

Toller Beitrag und schön erklärt. :applaus: