Kollisionstest durch Determinanten-Vorzeichen

Wie wir bereits gesehen haben, lässt sich die konvexe Hülle allein mit den Vorzeichen von Determinanten bestimmen. Können wir die Kollision zweier Strecken mithilfe von Determinanten bestimmen?

Eine Gerade durch $v$ und $w$ schneidet eine Strecke $t u$ (ohne Endpunkte), wenn $t$ und $u$ auf unterschiedlichen Seiten der Geraden liegen. Dies ist genau dann der Fall, wenn $\det(v,w,u) \cdot \det(v,w,t) < 0$, also die beiden Determinanten ein verschiedenes Vorzeichen haben oder die Umlaufsinne der jeweiligen drei Punkte verschieden sind. Die Punkte werden jeweils mit einer zusätzlichen 1 im letzten Eintrag in die 3x3-Determinante eingesetzt.

Ebenso schneidet eine Gerade durch $t$ und $u$ die Strecke $v w$, falls $\det(u,t,v)\cdot \det(u,t,w) < 0$.

Genau dann wenn beide Bedingungen gleichzeitig erfüllt sind, so schneiden sich die beiden Strecken $t u$ und $v w$.

In dem folgendem Applet werden die Segmente genau im Schnittfall rot (andernfalls grün) gezeichnet

Dies wurde durch folgenden Code bewerkstelligt.

collision(A,B,C,D):=
  and(
    det(A,B,C)*det(A,B,D)<0,
    det(C,D,A)*det(C,D,B)<0
  );
if(collision(v,w,u,t),
  a.color=b.color=(1,0,0); //rot
,// else
  a.color=b.color=(0,1,0); //grün
);