How can I check if 2 segments intersect ?

Question

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.

thanks

Update:

Answer 1

The formula for 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.

Answer 2

if your data define line you just have to prove that they are not parallel. To do this you can compute

alpha = float(y2 - y1) / (x2 - x1).

If this coefficient is equal for both Line1 and Line2, it means the line are parallel. If not, it means they will intersect.

If they are parallel you then have to prove that they are not the same. For that, you compute

beta = y1 - alpha*x1

If beta is the same for Line1 and Line2,it means you line intersect as they are equal

If they are segment, you still have to compute alpha and beta as described above for each Line. Then you have to check that (beta1 - beta2) / (alpha1 - alpha2) is greater than Min(x1_line1, x2_line1) and less than Max(x1_line1, x2_line1)

Answer 3

Calculate the intersection point of the lines laying on your segments (it means basically to solve a linear equation system), then check whether is it between the starting and ending points of your segments.

Answer 4

You have two line segments. Define one segment by endpoints A & B and the second segment by endpoints C & D. There is a nice trick to show that they must intersect, WITHIN the bounds of the segments. (Note that the lines themselves may intersect beyond the bounds of the segments, so you must be careful. Good code will also watch for parallel lines.)

The trick is to test that points A and B must line on opposite sides of line CD, AND that points C and D must lie on opposite sides of line AB.

Since this is homework, I won't give you an explicit solution. But a simple test to see which side of a line a point falls on, is to use a dot product. Thus, for a given line CD, compute the normal vector to that line (I'll call it N_C.) Now, simply test the signs of these two results:

dot(A-C,N_C)

and

dot(B-C,N_C)

If those results have opposite signs, then A and B are opposite sides of line CD. Now do the same test for the other line, AB. It has normal vector N_A. Compare the signs of

dot(C-A,N_A)

and

dot(D-A,N_A)

I'll leave it to you to figure out how to compute a normal vector. (In 2-d, that is trivial, but will your code worry about whether A and B are distinct points? Likewise, are C and D distinct?)

You still need to worry about line segments that lie along the same infinite line, or if one point actually falls on the other line segment itself. Good code will cater to every possible problem.

Answer 5

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

Answer 6

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

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 function, one must remember to check that each segment lays "between" the other segment (since these are finite segments, and not infinite lines).

Also, using these function 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).

Answer 7

This is what I've got for AS3, don't know much about python but the concept is there

    public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
        var A:Point = $A.clone();
        var B:Point = $B.clone();
        var C:Point = $C.clone();
        var D:Point = $D.clone();
        var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);

        // are lines parallel
        if (f_ab == 0) { return Infinity };

        var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
        var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
        var f1:Number = f_ab/f_d
        var f2:Number = f_cd / f_d
        if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
        if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
        return f1;
    }

    public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
    {
        var f:Number = getIntersectingPointF($A, $B, $C, $D);
        if (f == Infinity || f <= 0 || f >= 1) { return null };

        var retPoint:Point = Point.interpolate($A, $B, 1 - f);
        return retPoint.clone();
    }