Q:

Algebraically determine if lines intersect

I have a programming problem that involves determining if any 4 line segments intersect.  (I am testing to see if four points [in a specific order] comprise a quadrilateral).  Mathematically speaking, using the four "endpoints," what is the easiest way to determine whether any of the segments intersect?

A:

Suppose that you have four points, $A=(x_a,y_a)$, $B=(x_b,y_b)$, $C=(x_c,y_c)$, and $D=(x_d,y_d)$.  The line segment joining $A$ and $B$ contains the points $(tx_a+(1-t)x_b,ty_a+(1-t)y_b)$ for $0\le t\le 1$; the line segment joining $C$ and $D$ contains the points $(ux_c+(1-u)x_d,uy_c+(1-u)y_d)$ for $0\le u\le 1$.  If the two segments intersect, then the system $$\begin{align}
tx_a+(1-t)x_b&=ux_c+(1-u)x_d
\\
ty_a+(1-t)y_b&=uy_c+(1-u)y_d
\end{align}$$
has a solution for $t$ and $u$ where $0\le t\le 1$ and $0\le u\le 1$.
It should be relatively straight-forward to write explicit formulas for the solutions of that system in terms of the points and check if the solutions are between 0 and 1, inclusive.

