How can I check if two segments intersect?

Question

User @i_4_got points to this page with a very efficent solution in Python. I reproduce it here for convenience (since it would have made me happy to have it here):

def ccw(A,B,C):
    return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

The equation of a line is:

f(x) = A*x + b = y

For a segment, it is exactly the same, except that x is included on an interval I.

If you have two segments, defined as follow:

Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}

The abcisse Xa of the potential point of intersection (Xa,Ya) must be contained in both interval I1 and I2, defined as follow :

I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]

And we could say that Xa is included into :

Ia = [max( min(X1,X2), min(X3,X4) ),
      min( max(X1,X2), max(X3,X4) )]

Now, we need to check that this interval Ia exists :

if (max(X1,X2) < min(X3,X4)):
    return False  # There is no mutual abcisses

So, we have two line formula, and a mutual interval. Your line formulas are:

f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y

As we got two points by segment, we are able to determine A1, A2, b1 and b2:

A1 = (Y1-Y2)/(X1-X2)  # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4

If the segments are parallel, then A1 == A2 :

if (A1 == A2):
    return False  # Parallel segments

A point (Xa,Ya) standing on both line must verify both formulas f1 and f2:

Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2)   # Once again, pay attention to not dividing by zero

The last thing to do is check that Xa is included into Ia:

if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
     (Xa > min( max(X1,X2), max(X3,X4) )) ):
    return False  # intersection is out of bound
else:
    return True

In addition to this, you may check at startup that two of the four provided points are not equals to avoid all that testing.

You don't have to compute exactly where does the segments intersect, but only understand whether they intersect at all. This will simplify the solution.

The idea is to treat one segment as the "anchor" and separate the second segment into 2 points.
Now, you will have to find the relative position of each point to the "anchored" segment (OnLeft, OnRight or Collinear).
After doing so for both points, check that one of the points is OnLeft and the other is OnRight (or perhaps include Collinear position, if you wish to include improper intersections as well).

You must then repeat the process with the roles of anchor and separated segments.

An intersection exists if, and only if, one of the points is OnLeft and the other is OnRight. See this link for a more detailed explanation with example images for each possible case.

Implementing such method will be much easier than actually implementing a method that finds the intersection point (given the many corner cases which you will have to handle as well).

Update

The following functions should illustrate the idea (source: Computational Geometry in C).
Remark: This sample assumes the usage of integers. If you're using some floating-point representation instead (which could obviously complicate things), then you should determine some epsilon value to indicate "equality" (mostly for the IsCollinear evaluation).

// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
     return Area2(a, b, c) > 0;
}

bool IsOnRight(Point a, Point b, Point c)
{
     return Area2(a, b, c) < 0;
}

bool IsCollinear(Point a, Point b, Point c)
{
     return Area2(a, b, c) == 0;
}

// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
     return (b.X - a.X) * (c.Y - a.Y) -
            (c.X - a.X) * (b.Y - a.Y);
}

Of course, when using these functions, one must remember to check that each segment lies "between" the other segment (since these are finite segments, and not infinite lines).

Also, using these functions you can understand whether you've got a proper or improper intersection.

• Proper: There are no collinear points. The segments crosses each other "from side to side".
• Improper: One segment only "touches" the other (at least one of the points is collinear to the anchored segment).

Suppose the two segments have endpoints A,B and C,D. The numerically robust way to determine intersection is to check the sign of the four determinants:

| Ax-Cx  Bx-Cx |    | Ax-Dx  Bx-Dx |
| Ay-Cy  By-Cy |    | Ay-Dy  By-Dy |

| Cx-Ax  Dx-Ax |    | Cx-Bx  Dx-Bx |
| Cy-Ay  Dy-Ay |    | Cy-By  Dy-By |

For intersection, each determinant on the left must have the opposite sign of the one to the right, but there need not be any relationship between the two lines. You are basically checking each point of a segment against the other segment to make sure they lie on opposite sides of the line defined by the other segment.

See here: http://www.cs.cmu.edu/~quake/robust.html

Checking if line segments intersect is very easy with Shapely library using intersects method:

from shapely.geometry import LineString

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True

line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False

Here's a solution using dot products:

# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
    dx0 = s0[1][0]-s0[0][0]
    dx1 = s1[1][0]-s1[0][0]
    dy0 = s0[1][1]-s0[0][1]
    dy1 = s1[1][1]-s1[0][1]
    p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
    p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
    p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
    p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
    return (p0*p1<=0) & (p2*p3<=0)

Here's a visualization in Desmos: Line Segment Intersection

Based on Liran's and Grumdrig's excellent answers here is a complete Python code to verify if closed segments do intersect. Works for collinear segments, segments parallel to axis Y, degenerate segments (devil is in details). Assumes integer coordinates. Floating point coordinates require a modification to points equality test.

def side(a,b,c):
    """ Returns a position of the point c relative to the line going through a and b
        Points a, b are expected to be different
    """
    d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
    return 1 if d > 0 else (-1 if d < 0 else 0)

def is_point_in_closed_segment(a, b, c):
    """ Returns True if c is inside closed segment, False otherwise.
        a, b, c are expected to be collinear
    """
    if a[0] < b[0]:
        return a[0] <= c[0] and c[0] <= b[0]
    if b[0] < a[0]:
        return b[0] <= c[0] and c[0] <= a[0]

    if a[1] < b[1]:
        return a[1] <= c[1] and c[1] <= b[1]
    if b[1] < a[1]:
        return b[1] <= c[1] and c[1] <= a[1]

    return a[0] == c[0] and a[1] == c[1]

#
def closed_segment_intersect(a,b,c,d):
    """ Verifies if closed segments a, b, c, d do intersect.
    """
    if a == b:
        return a == c or a == d
    if c == d:
        return c == a or c == b

    s1 = side(a,b,c)
    s2 = side(a,b,d)

    # All points are collinear
    if s1 == 0 and s2 == 0:
        return \
            is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
            is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    s1 = side(c,d,a)
    s2 = side(c,d,b)

    # No touching and on the same side
    if s1 and s1 == s2:
        return False

    return True