How to determine if 2 line segments cross? Give two line segments, each defined by $2$ points in $x,y$ space, such as $L_1 = (x_1,y_1)-(x_2,y_2)$ and $L_2 = (x_3-y_3)-(x_4,y_4)$, and that these points are the result of sampled data (they are not the result of known functions), is there a way to know if the line segments $L_1$ and $L_2$ cross each other (do they share a common $x,y$ point)?  A yes or no result is desired - not necessarily where (at what coordinate) they cross.
 A: As the points are fromsampled data, we may ignore border cases such as that three of the four points are collinear.
For a point $(x,y)$ you can compute the expression $$ f(x,y)=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)$$
and this changes sign precisely when $(x,y)$ moves across the line given by $(x_1,y_1)$ and $(x_2,y_2)$. Hence if $f(x_3,y_3)$ and $f(x_4,y_4)$ have different signs, the endpoints of the second line segment are on different sides of the first (prolonged) line.
With a similar test, you can check if the points $(x_1,y_1)$ and $(x_2,y_2)$ are on different sides of the second (prolonged) line.
If and only if both these tests approve, then the two line segments intersect.
A: We see that two points $P_1$, $P_2$ are an the same (opposite) sides of the line $QR$ if an only if  the $\it{oriented}$ areas $\text{Area}(P_1 QR) $ and $\text{Area}(P_2 QR)$ have the same (opposite) sign. The expression that appear are just  determinants.
This is easily generalized in $n$-space, when inquiring whether two points $P_1$, $P_2$ are on the same or opposite sides of the hyperplane determined by $Q_1, \ldots Q_n$. 
So for the problem at hand, the segments $P_1 P_2$ and $P_3 P_4$ intersect if and only if 
\begin{eqnarray}
\text{Area}(P_1 P_3 P_4)&\cdot& \text{Area}(P_2 P_3 P_4)\le 0 \ \ \text{and} \\ 
\text{Area}(P_3 P_1 P_2)&\cdot &\text{Area}(P_4 P_1 P_2)\le 0
\end{eqnarray}
Note:
$$\text{Area}(P_1 P_2 P_3) = \frac{1}{2} \cdot \left | \begin{array}{ccc} 1 & x_1 &y_1 \\
 1 & x_2 &y_2 \\
 1 & x_3 &y_3 
\end{array} \right| 
$$
A: I was thinking that the point where the lines would intersect would be given by the X coordinate $x = (B_2-B_1) / (M_1 - M_2)$ where $B_n$ and $M_n$ are the intercept and slope according to $y = Mx + B$, and $n$ is the line segment being discussed (1 and 2).  It would then be a simple matter to test if ($x$ lies between $X_1$ and $X_2$) and ($x$ lies between $X_3$ and $X_4$).  Yes?  No?
A: let 
$f(x,y)=(x-x_1)(y_2-y_1)-(y-y_1)(x_2-x_1)$ 
and 
$g(x,y)=(x-x_3)(y_4-y_3)-(y-y_3)(x_4-x_3)$
then the segments intersect provided that both of the following statements are correct.
$$f(x_3, y_3)f(x_4, y_4) <0 $$ $$ g(x_1, y_1)g(x_2, y_2) <0$$
A: Verbally stated, x as well as y each must lie between their respective extreme points to have an intersection. And symbolically
$$ (x-x_1)( x_2 -x) > 0,\; AND \, (y-y_1)(y_2-y) > 0 \; AND \,
(x-x_3)( x_4 -x) > 0,\; AND \, (y-y_3)(y_4-y) > 0 $$ 
where $ \ge $ sign valid if intersection occurs at one extremity of a line.
EDIT1
And,similarly for the second line.
