How can I check if two 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.

Solution 1

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.

Solution 2

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)

Solution 3

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[aneuryzm]

Segments, they are segments, sorry. Could you update your answer given segments ?

[aneuryzm]

ok thanks I will go through the code. Wow isn't complicated ? I thought it was not that long solution. But if it's the only one.. well let's do it.

[OMG_peanuts]

This is not so complicated, i wrote a lots of (unessential ?) intermediate steps in a comprehension purpose. The main points to implements are just : Check mutual interval existence, calculate A1, A2, b1, b2, and Xa, and then check that Xa is included in the mutual interval. That's all :)

[Jochen Ritzel]

+1 Pretty much my idea too. If you just think about where the points are in relation to each other, you can decide if their segments must to intersect or not, without calculating anything.

[aneuryzm]

and @THC4k Uhm, it is actually not clear. FOr example check the image I've added to the question: the 2 points are "OnLeft" and "OnRight" but the 2 segments are not intersecting.

[Liran]

@Patrick, actually no. Depending on which of the segments is the "anchor", then both points are either OnLeft or OnRight in this case. (See my updated answer).

[Miguel]

+1 I've seen dozens of answers to this problem, but this is by far the clearest, simplest, and most efficient that I've seen. :)

[egprentice]

A1 - A2 will never be zero because if(A1 == A2) would have returned before this calculation in that case.

[lynxoid]

if A1 == A2 and b1 == b2, the segments are on top of each other and have infinitely many intersections

[charles]

Very simple and elegant, but it does not deal well with colinearity, and thus more code needed for that purpose.

[dmitri]

Formula A1*x + b1 = y doesn't handle vertical lines hence vertical segments should be handled separately with this method.

[Zsolt Safrany]

For a solution that also handles collinearity check out geeksforgeeks.org/check-if-two-given-line-segments-intersect

[Corvin]

Seems you are missing the check if Ya belongs to Y projections. The way you have it, you would miss the case where segments are on top of each other - the abscissa of the intersection would be within segments' projections, but ordinate would not and you, having not checked the ordinate would have returned true. Also, checking that interval exists seems to be wrong. Seems like you are only checking it segment A is to the left of segment B, but are not checking the other case. It is still irrelevant, though since you are checking Xa's inclusion later on

[mac13k]

Are you sure about the formulas? Because coordinates of B are not used, so how can you find the intersection of AB and CD without considering all 4 vertices?

[mac13k]

I think there should be: dist2=slope*(Dx-Bx)+By-Dy

[rbaleksandar]

Yeah, I just found out that the y poses a problem. For example if we have a line segment [[-4, 12], [12, -4]] and then another one which goes VERTICALLY (that is no change along the x` axis) [[-4, -4], [-4, 10]] I still get intersection at [-4, 12]. Although this is true for a line (that is if we look at its continuation) it most certainly is not the case of a segment that doesn't even physically cross the other one.

[rbaleksandar]

Check this post of mine if you have the time. I use Cramer rule (that is a little bit different from your solution) for the intersection however the filtering for segments with no mutual abcisses is at the beginning hence what happens afterwards doesn't matter.

[Sayam Qazi]

does it work for improper intersections i.e. when the point of intersection lies on one line segment?

[Warty]

@SayamQazi It seems to fail intersection if you are passing the endpoint of a line segment, at least. For if you're on the segment: I assume it would be a 0 vs 1/-1 comparison, so it would detect no intersection.

[Warty]

By the way, to explain this: each determinant is computing the cross-product of two line segments' vectors endpoints. The top left is CA x CB vs top right DA x DB, for example. This essentially tests which side a vertex is on (clockness). Still trying to figure out how it works for line segments which don't extend infinitely.

[Björn Lindqvist]

This code doesn't calculate a1 and it doesn't work for orthogonal lines.

[hhquark]

closed_segment_intersect() from the test code is not defined.

[Fabian Ying]

@hhquark Thank you. I've now removed these lines. I included these lines while testing to check that my implementation agrees with the implementation from another answer (stackoverflow.com/a/18524383/7474256, I think).

[Sam]

What does "closed segments" exactly mean?

[dmitri]

@Sam Closed segment contains its endpoints. E.g. a closed segment of points from R would be [0, 1] (0 <= x <= 1) as opposed to say ]0, 1] (0 < x <= 1)

[geowar]

Typo: "dx2 = X4 - X4" should be "dx2 = X4 - X3"

[user1766438]

Love this solution. Very simple and short! I made a wxPython program that draws a line and sees if it intersects with another line. I could not place it here so it is somewhere below this comment.

[M. Volf]

you should also add a check that if min(X1,X2) > max(X3,X4): return False

[H. Pope]

Love your solution but it seems as though it fails if the two line segments are in line

[Pablo Jeken Rico]

I'd recommend you to check out this: geeksforgeeks.org/check-if-two-given-line-segments-intersect‌​/…

[Dee]

is it line or segment?

[Georgy]

@datdinhquoc These are segments. Shapely doesn't support infinite lines. But, depending on the use case, it may be possible to make an approximation. See, for example, How to create an infinite line from two given points to get intersection with other geometry objects in Shapely?

[WDUK]

This doesn't work even when i correct for the dx2 typo...

[Richard Z]

This is the dot product of two cross products. To exclude segment endpoints requires only rewriting the return to (p0*p1<0) & (p2*p3<0).

[MaiaVictor]

This is the best answer here. Very clean.

[Felipe]

it also doesnt work with lines with infinite slope...

[Maxwell's Daemon]

very cool solution @BenMan95. Would it be possible to know the intersection point?