Patrick - 2 years ago 116
Python Question

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

Update:

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 into 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, you need to check that this interval Ia exists :

``````if (MAX(X1,X2) < MIN(X3,X4))
return false; // There is no mutual abcisses
``````

So, you got 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) )) ||
(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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download