\documentclass[a4paper,10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amssymb}
\usepackage{german}

\title{Geometrischer Schnitt im $\mathbb{R}^2$}
\author{Viktor Engelmann}
\date{8. August 2002}

\begin{document}

\maketitle

Gegeben seien zwei Strecken mit den Eckpunkten $a=(a_1,a_2)$, $a'=(a'_1,a'_2)$ und $b=(b_1,b_2)$, $b'=(b'_1, b'_2)$ (mit $a\neq a'$ und
$b\neq b'$). Dann sind die Richtungsvektoren zwischen den jeweiligen Eckpunkten $\alpha := a'-a$ und $\beta := b'-b$. Hilfsgeraden durch
die Strecken sind nun $a+k\alpha$ und $b+l\beta$. Man beachte: jeder Punkt auf den Geraden, für den \marginpar{$(*)$}
$0\le k\le 1$ bzw. $0\le l\le 1$ gilt,
liegt auch auf der jeweiligen Strecke, weil die Länge von $\alpha$ bzw. $\beta$ gerade die Distanz von $a$ zu $a'$ bzw. von $b$ zu $b'$ ist.

Genau dann, wenn sich die Geraden schneiden, existieren $k$ und $l$ sodass $a+k\alpha = b+l\beta$. Zerlegen wir diese Gleichung in
in ihre beiden Bestandteile (wobei wir $(\alpha_1,\alpha_2) := \alpha$ und $(\beta_1,\beta_2) := \beta$ setzen), dann erhalten wir
\begin{eqnarray*}
 a_1+k\alpha_1 & = & b_1 + l \beta_1 \\
 a_2 + k \alpha_2 &=& b_2+l\beta_2
\end{eqnarray*}
Wir bestimmen nun $l$ mit dem Einsetzungsverfahren, indem wir die erste Gleichung nach $k$ auflösen, das Ergebnis in die zweite
Gleichung einsetzen und diese nach $l$ auflösen.
\[ k = \frac{b_1+l\beta_1 - a_1}{\alpha_1} \]
Dies in die zweite Gleichung eingesetzt liefert:
\begin{eqnarray*}
  b_2+l\beta_2 & =& a_2+\frac{b_1+l\beta_1-a_1}{\alpha_1} \alpha_2 \\
\Leftrightarrow \alpha_1b_2+\alpha_1l\beta_2 &=& \alpha_1a_2 + (b_1-a_1+l\beta_1)\alpha_2 \\
\Leftrightarrow \alpha_1b_2+\alpha_1l\beta_2 &=& \alpha_1a_2 + \alpha_2b_1-\alpha_2a_1+\alpha_2l\beta_1 \\
\Leftrightarrow \alpha_1b_2+\alpha_1 l\beta_2-\alpha_2l\beta_1 &=& \alpha_1a_2+\alpha_2b_1-\alpha_2a_1 \\
\Leftrightarrow \alpha_1 l\beta_2-\alpha_2l\beta_1 &=& \alpha_1a_2+\alpha_2b_1-\alpha_2a_1-\alpha_1b_2 \\
\Leftrightarrow l(\alpha_1\beta_2-\alpha_2\beta_1) &=& \alpha_1(a_2-b_2)-\alpha_2(a_1-b_1) \\
\Leftrightarrow l &=& \frac{\alpha_1(a_2-b_2)-\alpha_2(a_1-b_1)}{\alpha_1\beta_2-\alpha_2\beta_1} \\
&=& \frac{|\alpha,a-b|}{|\alpha,\beta|}
\end{eqnarray*}

Analog bestimmen wir $k$ mit dem Einsetzungsverfahren, indem wir die erste Gleichung nach $l$ auflösen, das Ergebnis in die zweite
Gleichung einsetzen und diese nach $k$ auflösen.
\[  l  =  \frac{a_1+k\alpha_1-b_1}{\beta_1} \]
Dies in die zweite Gleichung eingesetzt liefert:
\begin{eqnarray*}
 a_2+k\alpha_2 &=& b_2 + \frac{a_1+k\alpha_1-b_1}{\beta_1} \beta_2 \\
\Leftrightarrow \beta_1a_2 + \beta_1 k \alpha_2 & = & \beta_1 b_2+( a_1 + k\alpha_1-b_1)\beta_2 \\
\Leftrightarrow \beta_1a_2 + \beta_1 k \alpha_2 & = & \beta_1 b_2+\beta_2 a_1 + \beta_2k\alpha_1 - \beta_2b_1\\
\Leftrightarrow \beta_1a_2 + \beta_1 k \alpha_2 - \beta_2k\alpha_1 &=& \beta_1 b_2+\beta_2a_1-\beta_2b_1 \\
\Leftrightarrow \beta_1k\alpha_2 - \beta_2k\alpha_1 &=& \beta_1 b_2+\beta_2a_1-\beta_2b_1-\beta_1a_2 \\
\Leftrightarrow k(\beta_1\alpha_2-\alpha_1\beta_2) &=& \beta_1(b_2-a_2) - \beta_2(b_1-a_1)\\
\Leftrightarrow k&=&\frac{\beta_1(b_2-a_2) - \beta_2(b_1-a_1)}{\beta_1\alpha_2-\alpha_1\beta_2}\\
&=& \frac{|\beta,b-a|}{|\beta,\alpha|}
\end{eqnarray*}

Dabei bezeichnet $|x,y|$ die Determinante der Matrix, deren Spalten den Vektoren $x$ bzw. $y$ entsprechen. Zusammen mit
$(*)$ ergibt sich, dass die Strecken sich genau dann schneiden, wenn
\[ 0 \le \frac{|\beta,b-a|}{|\beta,\alpha|} \le 1 \textrm{ und } 0 \le \frac{|\alpha,a-b|}{|\alpha,\beta|} \le 1 \]
gilt. Algorithmisch kann man einen kleinen Performance-Gewinn erzielen, indem man die Determinantengesetze ausnutzt, aus denen folgt,
dass \[ \frac{|\alpha,a-b|}{|\alpha,\beta|} = \frac{-|\alpha,b-a|}{|\alpha,\beta|} = \frac{-|\alpha,b-a|}{-|\beta,\alpha|} = \frac{|\alpha,b-a|}{|\beta,\alpha|} \]
denn dadurch braucht man $|\beta,\alpha|$ und $b-a$ nur je ein mal zu berechnen.

\end{document}