# Einiges zur Geometrie (Punkte, Vektoren, Geraden)



## Beni (6. Aug 2004)

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
> ...










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:_
> ...



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 (10. Aug 2004)

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
> ...



(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: _
> ...


(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:_
> ...



*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
> 
> ...



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 (30. Jan 2008)

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


----------



## Gast (4. Aug 2008)

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 (8. Aug 2009)

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

gute Arbeit, euer Tutorial ist super.


----------



## Marco13 (8. Aug 2009)

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 (10. Aug 2009)

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


----------



## Illuvatar (10. Aug 2009)

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


----------



## Quaxli (14. Aug 2009)

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


----------

