# 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.

• If you need to handle the special cases that stand outside Hagen's solution, you might look at my textbook's SegSegInt code here. – Joseph O'Rourke Jun 28 '15 at 18:18

## 5 Answers

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.

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|$$

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$$

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?

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.

• No: Keep one line segment fixed and stretch the other until one or both of its endpoints move out of the bounding box of the first segment. The intersection point does not cease to exist. – ccorn Jul 1 '15 at 22:05
• In fact, your condition only states that $(x,y)$ is within the bounding box of the line segment $(x_1,y_1)(x_2,y_2)$. That segment divides its bounding box in two disjoint (triangular) halves. Choose one half, pick two points in its interior, and join them. The resulting segment does not cross the original line segment, yet it fulfills your stated condition. – ccorn Jul 1 '15 at 22:10