["python","math","geometry"]
How can I check if two segments intersect?

How can I check if 2 segments intersect? I've the following data: Segment1 [ {x1,y1}, {x2,y2} ] Segment2 [ {x1,y1}, {x2,y2} ] I need to write a small algorithm in Python to detect if the 2 lines are intersecting.
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 abscissa 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 abscissae 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.