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.
A: I think there may be a way to avoid the "parameterized" approach. Suppose we wish to determine whether the points $A,B,C,D$ in order determine a nondegenerate quadrilateral. This will occur precisely when the "diagonals" $AC$ and $BD$ have a unique point of intersection interior to both line segments. This happens precisely when $A$ and $C$ lie on different "sides" of $BD$ and $B$ and $D$ lie on different "sides" of $AC$. This last condition can easily be re-expressed in terms of dot products (recall that for vectors $u$ and $v$ their dot product $u \cdot v$ will be positive, zero or negative according as the smallest positive angle between $u,v$ is less than, equal to, or greater than $90$ degrees). For instance, $A,B,C,D$ in that order will form a nondegenerate quadrilateral if and only if both of


*

*$\overrightarrow{AB} \cdot (\overrightarrow{AC})^\bot$ and $\overrightarrow{AD} \cdot (\overrightarrow{AC})^\bot$ are nonzero with opposing signs (or equivalently their product is negative).

*$\overrightarrow{BA} \cdot (\overrightarrow{BD})^\bot$ and $\overrightarrow{BC} \cdot (\overrightarrow{BD})^\bot$ are nonzero with opposing signs.


hold where, for points $X,Y$, $\overrightarrow{XY} := Y - X$ is the vector from a $X$ to $Y$ and for a vector $v=(x,y)$, $v^\bot := (-y,x)$ is $v$ rotated counterclockwise by $90$ degrees.
