Frage zur Vektorrechnung

[Kelven]

Ich hab folgendes Problem: Eine Strecke und eine Fläche, ich möchte wissen ob die Strecke durch die Fläche läuft. Leider hab ich schon alles was Mathe betrifft aus meinem Gedächtnis verdrängt. Ich denke aber mal die Vektorrechnung sollte hier eine Lösung anbieten, kann aber auch sein, dass ich mich irre. Weiß jemand ob es für das Problem eine Formel gibt und am besten eine, die sich auch leicht mit einer Programmiersprache implementieren lässt? Der Vollständigkeit halber könntet ihr auch noch aufschreiben, wie man eine Gerade und eine Fläche bei denen man nur die Endpunkte kennt als Vektor ausdrückt. xD

[TheBiber]

Gott, jetzt hatte ich 20 Minuten lange einen Text verfasst, dann stürzte mein PC einfach so mal ab, und ich regte mich tierisch auf. Ich editier jetzt das ganze nochmals hier herein...

Also erstmal vorneweg: Wenn du von einem Vektor c den Anfangspunkt \vec a = \left(\begin{array}{c}a_1\\a_2\\a_3\end{array}\right) und Endpunkt \vec b = \left(\begin{array}{c}b_1\\b_2\\b_3\end{array}\right) kennst, kannst du ihn berechnen, indem du die Koordinaten des Anfangspunktes vom Endpunkt abziehst: \vec c = \vec b - \vec a = \left(\begin{array}{c}b_1-a_1\\b_2-a_2\\b_3-a_3\end{array}\right)

Ganz allgemein lassen sich Kurven und Flächen im Raum durch eine Parameterdarstellung beschreiben. Abstrakt geschrieben sieht das für eine Kurve k so aus: k:\mathbb{R}\rightarrow\mathbb{R}^3,t \mapsto \vec x(t) und für eine Fläche F so: F:\mathbb{R}^2\rightarrow\mathbb{R}^3, (r,s)\mapsto \vec x(r,s)

Die Kurve lässt sich am besten als "Fahrplan" darstellen, zu jedem "Zeitpunkt" t lassen sich die Koordinaten des Punktes berechnen. Die Fläche funktioniert analog, für zwei Zahlen r und s erhält man die Koordinaten eines Punktes auf der Fläche. Falls die Parameter t, r und s nur linear vorkommen, hat man den einfachsten Spezialfall einer Geraden bzw. einer Ebene. Dazu mache ich je ein Beispiel, damit man sich das ganze formal besser vorstellen kann:

g:\vec x(t) = \left(\begin{array}{c}2\\2\\3 \end{array}\right)\cdot t + \left(\begin{array}{c} -2\\0\\1\end{array}\right)

Der zweite (unabhängige) Vektor ist hierbei der Stützvektor, d.h. irgendein Punkt auf der Gerade, den du kennst. Der erste Vektor ist der Richtungsvektor, d.h. irgendein Vektor, der in die gleiche Richtung wie die Gerade zeigt. Wenn du zwei Punkte gegeben hast, kannst du sie berechnen mit der ersten Formel, die ich geschrieben habe.

E:\vec y(r,s) = \left(\begin{array}{c} 1\\0\\-1\end{array}\right)\cdot r + \left(\begin{array}{c} -4\\2\\5\end{array}\right)\cdot s + \left(\begin{array}{c} 0\\3\\2 \end{array}\right)

Hier hast du ebenfalls den unabhängigen Stützvektor, der einfach einen Punkt der Ebene repräsentiert und zwei Richtungsvektoren. Eine Ebene ist durch drei Punkte exakt bestimmt. Die Differenz aus Stützpunkt und einem weiteren Punkt entspricht einem Richtungsvektor.

Ganz allgemein gilt: Willst du von zwei solchen geometrischen Objekten die Schnittpunkte berechnen, so setzt du ihre Parameterdarstellungen gleich. Daraus resultiert ein Gleichungssystem für die Parameter. Die Lösungen sind dann diejenigen Parameter, für welche du die Schnittpunkte erhältst. Hat das Gleichungssystem für die Parameter keine Lösung, heisst das, es gibt keine Schnittpunkte. Als Beispiel suchen wir mal Schnittpunkte obiger Beispiele.

Gleichsetzen: \vec x(t)=\vec y(r,s) \Rightarrow \left(\begin{array}{c}2\\2\\3 \end{array}\right)\cdot t + \left(\begin{array}{c} -2\\0\\1\end{array}\right) = \left(\begin{array}{c} 1\\0\\-1\end{array}\right)\cdot r + \left(\begin{array}{c} -4\\2\\5\end{array}\right)\cdot s + \left(\begin{array}{c} 0\\3\\2 \end{array}\right) führt auf das Gleichungssystem: \begin{array}{rcl} 2t-s+4r &=& 2 \\ 2t-2s&=&3 \\ 3+r-5s&=&3 \end{array}

Im linearen Fall lassen sich die Lösungen z.B. mit dem Gaussschen Eliminationsverfahren (http://de.wikipedia.org/wiki/Gau%C3%9Fsches_Eliminationsverfahren) berechnen. Auf jeden Fall ist das System lösbar und hat die Lösungen: r=-\frac{5}{21}, s=-\frac{1}{21}, t=\frac{61}{42}

Wie es bei einer Gerade und einer Ebene im Allgemeinen zu erwarten war, erhält man genau einen einzigen Schnittpunkt. Dieser lässt sich berechnen, indem man t in die Parameterdarstellung der Geraden oder r und s in die Parameterdarstellung der Ebene einsetzt.

Auf jeden Fall funktioniert diese Vorgehensweise ganz allgemein, d.h. auch für die Schnittpunkte zweier Geraden (hier ist das System im Allgemeinen nicht lösbar, da zwei Geraden normalerweise windschief liegen) oder für zwei Ebenen (hier erhält man unendlich viele abhängige Lösungen, die dann wieder auf eine Gerade führen) und für x-beliebige Kurven und Flächen, nur das bei letzterem im Allgemeinen mathematische Vorsicht und Fallunterscheidungen betrachtet werden müssen.

Aus deiner Fragestellung entnehme ich, dass du dieses Problem jetzt wohl programmiertechnisch umsetzen willst. Solange du nur Geraden und Ebenen verwendest, sollte dies kein allzu grosses Problem sein. Die Parameterdarstellung besteht aus drei Funktionen und enthält allgemein 6 Konstanten für die Gerade und 9 für die Ebene:

g:\vec x(t)=\left(\begin{array}{c}a_1\\a_2\\a_3\end{array}\right)\cdot t + \left(\begin{array}{c}b_1\\b_2\\b_3\end{array}\right)

E:\vec y(t)=\left(\begin{array}{c}c_1\\c_2\\c_3\end{array}\right)\cdot r + \left(\begin{array}{c}d_1\\d_2\\d_3\end{array}\right)\cdot s+ \left(\begin{array}{c}e_1\\e_2\\e_3\end{array}\right)

Das Gleichungssystem lässt sich einfacher darstellen mit Hilfe einer augmentierten Matrix, d.h. es interessieren nur noch die Koeffizienten. Für das allgemeine Beispiel von Gerade und Ebene hat man dann:

\left[\begin{array}{ccc|c}a_1&-c_1&-d_1&-b_1+e_1 \\ a_2&-c_2&-d_2&-b_2+e_2 \\ a_3&-c_3&-d_3&-b_3+e_3 \end{array}\right]

Nun muss man lediglich den Gausschen Algorithmus darauf anwenden, dafür gibt es sicher entsprechende Bibliotheken. Falls er eine Lösung ausspuckt, existiert ein Schnittpunkt, ansonsten nicht.

Ich hoffe, ich konnte helfen und hab mit dem Formalismus nicht zuviel Verwirrung gestiftet. ;)

[Kelven]

Erstmal Danke, aber - soweit es meine Erinnerung an das Fach noch zulässt - ist eine Gerade doch etwas anderes als eine Strecke und mit "Fläche" meinte ich keine Ebene (die ist ja unendlich) sondern in meinem Fall ein Quadrat. D.h. auch, dass für diesen speziellen Fall nur der 2D-Raum eine Rolle spielt. Funktioniert das mit deinem Beispiel trotzdem oder gibt es vielleicht ausserhalb der Vektorrechnung noch Lösungen?

[TheBiber]

Dann habe ich die Frage wohl falsch aufgefasst. :D

Also wenn wir statt einen dreidimensionalen einen zweidimensionalen Raum zulassen, ändert sich an den Parameterdarstellungen ebenfalls nur die Dimension. Eine Gerade wird dann nur noch durch zwei Gleichungen beschrieben. Flächengleichungen sind allerdings nicht mehr möglich, da der zweidimensionale Raum eine Ebene ist. Was du hier unter Flächen verstehst sind Geometrische Figuren.

Im Prinzip lässt sich aber alles parametrisieren: Eine Strecke ist nichts anderes als eine Gerade, bei dem du den Parameter t in einem Intervall beschränkst, d.h. er darf nur Werte zwischen zwei reellen Zahlen annehmen. Quadrate lassen sich so als eine Menge von mehreren Strecken auffassen, d.h. du brauchst für jede einzelne Strecke eine eigene Parameterdarstellung.

Obige Methode funktioniert immer noch, nur das die Einzelfälle zu mühsamen Spezialfällen werden: Willst du prüfen, ob eine Strecke ein Quadrat schneidet, musst du die Parameterdarstellung der Strecke mit jeder einzelnen der 4 Parameterdarstellungen der Geraden gleich setzen. Zudem musst du für alle Parameter prüfen, ob die Lösungen innerhalb der Intervalle liegen, da ansonsten der Schnittpunkt nicht gegeben ist.

Zu deiner Frage, ob es ausserhalb der Vektorrechnung Lösungen gibt: Es kommt auf den Fall an. Liegt ein Rechteck parallel zum Koordinatensystem, dann lässt sich das Rechteck einfach als Menge von Punkten beschreiben, z.B. ein Reckteck R der Breite 3 und der Höhe 2, bei dem der linke untere Eckpunkt mit dem Ursprung des Koordinatensystems zusammenfällt, wäre: R=\{x,y\in\mathbb{R}^2|0\leq x\leq 3,0\leq y\leq 2\}

Wenn du eine Strecke gegeben hast, kannst du sie als Parameterdarstellung \vec x(t)=\vec a\cdot t+\vec b, c\leq t\leq d beschreiben, oder als Punktmenge g=\{x,y\in U\subset \mathbb{R}^2|x+y=c\} oder, falls sie nicht senkrecht ist, auch als eine Funktionsgleichung y=f(x)=mx+q, c\leq x\leq d.

Für die Frage, ob die Strecke das Rechteck schneidet, gibt es deshalb verschiedenste Möglichkeiten. Eine wäre z.B. die x-Koordinate eines linken oder rechten Randpunktes des Rechtecks zu überprüfen, ob sie innerhalb der Intervallgrenzen der x-Koordinate der Strecke liegt. Falls ja, so setzt man die x-Koordinate in die Parameterdarstellung/Mengengleichung/Funktion ein und berechnet die y-Koordinate. Liegt diese ebenfalls im Rechteck, so besteht ein Schnitt, ansonsten nicht. Dies muss dann für alle vier Kanten des Rechtecks einzeln durchgeführt werden.