How can I check if two segments intersect?

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 intersectdef 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 = yf2(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 zeroA2 = (Y3-Y4)/(X3-X4)  # Pay attention to not dividing by zerob1 = Y1-A1*X1 = Y2-A1*X2b2 = 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 + b1Ya = A2 * Xa + b2A1 * Xa + b1 = A2 * Xa + b2Xa = (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 boundelse:    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 pointbool 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 eachother "from side to side".
• Improper: One segment only "touches" the other (at least one ofthe points is collinear to theanchored segment).