Check if two line segments intersect

Introduction

In this post, I discussed the cross product of two line segments in order to determine the relative orientation with respect to the origin. In this article, I extend the cross product idea to check if two line segments intersect. In order to fully understand this article, you need to understand this article first.

Two line segments intersect if and only if either (or both) of the following conditions hold

1. Each segment straddles the line containing the other as shown in the figure (a) below.
2. An endpoint of one segment lies on the other segment as shown in the figure (b) below.

If the above two conditions do not hold, then the line segments do not intersect.

Algorithm

I describe both cases stated above here in detail.

Case 1: Each Segment straddles the line containing other

In figure (a) above, point $p_1$ is left of a segment $p_3p_4$. In other word, if we draw a new vector $\overline{p_3p_1}$ then this vector is anti-clockwise from the vector $\overline{p_3p_4}$ which in turn means the cross product of vector $(p_1 - p_3)$ and $(p_4 - p_3)$ is less than zero i.e.
$$d_1 = (p_1 - p_3) \times (p_4 - p_3) < 0$$
Similarly point $p_2$ lies right of a segment $p_3p_4$. Which means the cross product of vector $(p_2 - p_3)$ and $(p_4 - p_3)$ is greater than zero i.e.
$$d_2 = (p_2 - p_3) \times (p_4 - p_3) > 0$$
Likewise, point $p_3$ is right of a segment $p_1p_2$. Which means the cross product of vector $(p_3 - p_1)$ and $(p_2 - p_1)$ is greater than zero i.e.
$$d_3 = (p_3 - p_1) \times (p_2 - p_1) > 0$$
Finally, point $p_4$ lies left of a segment $p_1p_2$. Which means the cross product of vector $(p_4 - p_1)$ and $(p_1 - p_1)$ is less than zero i.e.
$$d_4 = (p_4 - p_1) \times (p_2 - p_1) < 0$$
If we combine all four conditions above, the condition for two segments to intersect becomes,
$$d_1 < 0 \text{ and } d_2 > 0 \text{ and } d_3 > 0 \text{ and } d_4 < 0$$
The segments in figure (a) above can be arranged in four different ways as shown in the figure below.

In figure (b) the position of points $p_1$ and $p_2$ is reversed and the result of cross product will be opposite i.e.
$$ d_1 > 0 \text{ and } d_2 < 0 $$
If we consider the case (b) then the our condition becomes
$$((d_1 < 0 \text{ and } d_2 > 0) or ((d_1 > 0 \text{ and } d_2 < 0)) \text{ and } d_3 > 0 \text{ and } d_4 < 0$$
Similarly if we consider all the four cases, the final condition would become
$$((d_1 < 0 \text{ and } d_2 > 0) or ((d_1 > 0 \text{ and } d_2 < 0)) \text{ and } (d_3 > 0 \text{ and } d_4 < 0) \text { or } (d_3 < 0 \text{ and } d_4 > 0))$$

Case 2: An endpoint of one segment lies on other segment

In this case we need to check two conditions

1. One endpoint of one segment must be collinear with the other segment.
2. The collinear endpoint of one segment must lie between the two endpoints of other segment.

This is illustrated in the figure below. In both figures, one endpoint $p_3$ is collinear with the segment $p_1p_2$ but only figure (a) meets both the conditions. In figure (b) the point $p_3$ lies outside the segment $p_1p_2$.

The python code to check if a point lies on the segment is given below.

1
2
3

# checks if p lies on the segment p1p2
def on_segment(p1, p2, p):
    return min(p1.x, p2.x) <= p.x <= max(p1.x, p2.x) and min(p1.y, p2.y) <= p.y <= max(p1.y, p2.y)

Since the segments in figure (a) can be arranged in four different ways, there are four different conditions. If any one of the condition holds, then two segments intersect.

1. $p_3$, $p_4$ and $p_1$ are collinear and $p_1$ lies between $p_3$ and $p_4$
2. $p_3$, $p_4$ and $p_2$ are collinear and $p_2$ lies between $p_3$ and $p_4$
3. $p_1$, $p_2$ and $p_3$ are collinear and $p_3$ lies between $p_1$ and $p_2$
4. $p_1$, $p_2$ and $p_4$ are collinear and $p_4$ lies between $p_1$ and $p_2$.

The following python code implements the whole idea discussed above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# checks if line segment p1p2 and p3p4 intersect
def intersect(p1, p2, p3, p4):
    d1 = direction(p3, p4, p1)
    d2 = direction(p3, p4, p2)
    d3 = direction(p1, p2, p3)
    d4 = direction(p1, p2, p4)

    if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and \
        ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
        return True

    elif d1 == 0 and on_segment(p3, p4, p1):
        return True
    elif d2 == 0 and on_segment(p3, p4, p2):
        return True
    elif d3 == 0 and on_segment(p1, p2, p3):
        return True
    elif d4 == 0 and on_segment(p1, p2, p4):
        return True
    else:
        return False

Complexity

The complexity of above program is $O(1)$. All the operation performed are of constant complexity therefore the overall time complexity is also constant.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.