How do you detect where two line segments intersect?

Question

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

Answer 1

If each side of the rectangle is a line segment, and the user drawn portion is a line segment, then you need to just check the user drawn segment for intersection with the four side line segments. This should be a fairly simple exercise given the start and end points of each segment.

Answer 2

Take a look at this code: (It is javascript, but I think you can get the idea)

http://www.kevlindev.com/gui/math/intersection/Intersection.js

Look at:

• intersectLineLine
• intersectLineRectangle

Here is a demo: http://www.kevlindev.com/geometry/2D/intersections/intersect_line_rect.svg

Answer 3

The problem reduces to this question: Do two lines from A to B and from C to D intersect? Then you can ask it four times (between the line and each of the four sides of the rectangle).

Here's the vector math for doing it. I'm assuming the line from A to B is the line in question and the line from C to D is one of the rectangle lines. My notation is that Ax is the "x-coordinate of A" and Cy is the "y-coordinate of C." And "*" means dot-product, so e.g. A*B = Ax*Bx + Ay*By.

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

This h number is the key. If h is between 0 and 1, the lines intersect, otherwise they don't. If F*P is zero, of course you cannot make the calculation, but in this case the lines are parallel and therefore only intersect in the obvious cases.

The exact point of intersection is C + F*h.

More Fun:

If h is exactly 0 or 1 the lines touch at an end-point. You can consider this an "intersection" or not as you see fit.

Specifically, h is how much you have to multiply the length of the line in order to exactly touch the other line.

Therefore, If h<0, it means the rectangle line is "behind" the given line (with "direction" being "from A to B"), and if h>1 the rectangle line is "in front" of the given line.

Derivation:

A and C are vectors that point to the start of the line; E and F are the vectors from the ends of A and C that form the line.

For any two non-parallel lines in the plane, there must be exactly one pair of scalar g and h such that this equation holds:

A + E*g = C + F*h

Why? Because two non-parallel lines must intersect, which means you can scale both lines by some amount each and touch each other.

(At first this looks like a single equation with two unknowns! But it isn't when you consider that this is a 2D vector equation, which means this is really a pair of equations in x and y.)

We have to eliminate one of these variables. An easy way is to make the E term zero. To do that, take the dot-product of both sides of the equation using a vector that will dot to zero with E. That vector I called P above, and I did the obvious transformation of E.

You now have:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

Answer 4

You might find some useful information in the question I previously asked about this very topic (but with GDI+) at http://stackoverflow.com/questions/153592/how-do-i-determine-the-intersection-point-of-two-lines-in-gdi.

Answer 5

This is working well for me. Taken from here.

 // calculates intersection and checks for parallel lines.  
 // also checks that the intersection point is actually on  
 // the line segment p1-p2  
 Point findIntersection(Point p1,Point p2,  
   Point p3,Point p4) {  
   float xD1,yD1,xD2,yD2,xD3,yD3;  
   float dot,deg,len1,len2;  
   float segmentLen1,segmentLen2;  
   float ua,ub,div;  

   // calculate differences  
   xD1=p2.x-p1.x;  
   xD2=p4.x-p3.x;  
   yD1=p2.y-p1.y;  
   yD2=p4.y-p3.y;  
   xD3=p1.x-p3.x;  
   yD3=p1.y-p3.y;    

   // calculate the lengths of the two lines  
   len1=sqrt(xD1*xD1+yD1*yD1);  
   len2=sqrt(xD2*xD2+yD2*yD2);  

   // calculate angle between the two lines.  
   dot=(xD1*xD2+yD1*yD2); // dot product  
   deg=dot/(len1*len2);  

   // if abs(angle)==1 then the lines are parallell,  
   // so no intersection is possible  
   if(abs(deg)==1) return null;  

   // find intersection Pt between two lines  
   Point pt=new Point(0,0);  
   div=yD2*xD1-xD2*yD1;  
   ua=(xD2*yD3-yD2*xD3)/div;  
   ub=(xD1*yD3-yD1*xD3)/div;  
   pt.x=p1.x+ua*xD1;  
   pt.y=p1.y+ua*yD1;  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  
   xD1=pt.x-p1.x;  
   xD2=pt.x-p2.x;  
   yD1=pt.y-p1.y;  
   yD2=pt.y-p2.y;  
   segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  
   xD1=pt.x-p3.x;  
   xD2=pt.x-p4.x;  
   yD1=pt.y-p3.y;  
   yD2=pt.y-p4.y;  
   segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);  

   // if the lengths of both sets of segments are the same as  
   // the lenghts of the two lines the point is actually  
   // on the line segment.  

   // if the point isn’t on the line, return null  
   if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)  
     return null;  

   // return the valid intersection  
   return pt;  
 }  

 class Point{  
   float x,y;  
   Point(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  

   void set(float x, float y){  
     this.x = x;  
     this.y = y;  
   }  
 }

Answer 6

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be v_xw_y − v_yw_x (this is the magnitude of the 3-dimensional cross product).

Suppose the two line segments run from p to p + r and from q to q + s. Then any point on the first line is representable as p + tr (for a scalar parameter t) and any point on the second line as q + us (for a scalar parameter u).

The two lines intersect if we can find t and u such that:

p + tr = q + us

Cross both sides with s, getting

(p + tr) × s = (q + us) × s

And since s×s = 0, this means

t(r × s) = (q − p) × s

And therefore, solving for t:

t = (q − p) × s / (r × s)

In the same way, we can solve for u:

u = (q − p) × r / (r × s)

Now if r × s = 0 then the two lines are parallel. (There are two cases: if (q − p) × r = 0 too, then the lines are collinear, otherwise they never intersect.)

Otherwise the intersection point is on the original pair of line segments if 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1.

(Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Graham, published in Graphics Gems, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.)

Answer 7

Here there is matlab function with a very fast algorithm which calculates the intersectin point between two line segments:

From mathworks(author: Douglas Schwarz):

Description This function computes the (x,y) locations where two curves intersect. The curves can be broken with NaNs or have vertical segments. It is also very fast (at least on data that represents what I think is a typical application).

Answer 8

I have this big graph of edges and vertices in 2D space. The big graph is returned by a function computed in a C++ library. I am reading this graph and using it to compute all the intersections of its edges (the lines segements). I use sweep algorithm. For detecting the intersection of two edges I have though some problems. I have 4 different methods according to which I test if two edges intersect and if affirmative I compute and retain their intersection:

1- one which test if the two edges are the diagonals of a polygon. that is the coordinates of the edges of one line inserted into the equation of the other line have different signs

2- one which computes the intersection each time and check whether the found intersection is between the endpoints of both segments.

3- one which is the code from above implemented in C++ though

4- one which implements the first method proposed by Jason Cohen in this list of discussion

For data that I created (small data with double values) I obtained good results with all the 4 implemented methods. When I use anyone of these methods implemented in C++ on the data from the big graph I get different results each time and not good results:

1- method returns much more intersections that I need (all the points are on the graph) but I get too many points.

2-I always obtain 0 intersections no matter what.

3- I get a lot more intersection than in 1.

4- for some example I get points which are not on the graph (so not even the intersection). But for some examples I get the intersection points plus some other points.

I have no idea where the problem can be. Any suggestion or any other idea on how to compute the intersection and test it moreover are ore than welcomed. thank you, madalina

Answer 9

The answer "accepted" here is incorrect. It does not correctly eliminate all non-intersections. Trivially it may appear to work but it can fail, especially in the case that 0 and 1 are considered valid for h.

Consider the following case:

Lines at (4,1)-(5,1) and (0,0)-(0,2)

These are perpendicular lines which clearly do not overlap.

A=(4,1)
B=(5,1)
C=(0,0)
D=(0,2)
E=(5,1)-(4,1)=(-1,0)
F=(0,2)-(0,0)=(0,-2)
P=(0,1)
h=((4,1)-(0,0)) dot (0,1) / ((0,-2) dot (0,1)) = 0

According to the above answer, these two line segments meet at an endpoint (values of 0 and 1). That endpoint would be:

(0,0)+(0,-2)*0=(0,0)

So, apparently the two line segments meet at (0,0), which is on line CD, but not on line AB. So what is going wrong? The answer is that the values of 0 and 1 are not valid and only sometimes HAPPEN to correctly predict endpoint intersection. When the extension of one line (but not the other) would meet the line segment, the algorithm predicts an intersection of line segments, but this is not correct. I imagine that by testing starting with AB vs CD and then also testing with CD vs AB, this problem would be eliminated. Only if both fall between 0 and 1 inclusively can they be said to intersect.

I recommend using the vector cross product method if you must predict end-points.

-Dan

Answer 10

I have tried to implement the algorithm so elegantly described by Jason above; unfortunately while working though the mathematics in the debugging I found many cases for which it doesn't work.

For example consider the points A(10,10) B(20,20) C(10,1) D(1,10) gives h=.5 and yet it is clear by examination that these segments are no-where near each other.

Graphing this makes it clear that 0 < h < 1 criteria only indicates that the intercept point would lie on CD if it existed but tells one nothing of whether that point lies on AB. To ensure that there is a cross point you must do the symmetrical calculation for the variable g and the requirement for interception is: 0 < g < 1 AND 0 < h < 1

Answer 11

FWIW, the following function (in C) both detects line intersections and determines the intersection point. It is based on an algorithm in Andre LeMothe's "Tricks of the Windows Game Programming Gurus". It's not dissimilar to some of the algorithm's in other answers (e.g. Gareth's). LeMothe then uses Cramer's Rule (don't ask me) to solve the equations themselves.

I can attest that it works in my feeble asteroids clone, and seems to deal correctly with the edge cases described in other answers by Elemental, Dan and Wodzu. It's also probably faster than the code posted by KingNestor because it's all multiplication and division, no square roots!

I guess there's some potential for divide by zero in there, though it hasn't been an issue in my case. Easy enough to modify to avoid the crash anyway.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines 
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;

    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        // Collision detected
        if (i_x != NULL)
            *i_x = p0_x + (t * s1_x);
        if (i_y != NULL)
            *i_y = p0_y + (t * s1_y);
        return 1;
    }

    return 0; // No collision
}

BTW, I must say that in LeMothe's book, though he apparently gets the algorithm right, the concrete example he shows plugs in the wrong numbers and does calculations wrong. For example:

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

= 844/0.88

= 0.44

That confused me for hours. :(

Answer 12

i tried some of these answers but they didnt work for me(sorry guys) after some more net searching i found this

[http://alienryderflex.com/intersect/][1]

with a little modification to his code i now have this function that will return the point of intercteion or if no intercetion found it will return -1,-1

    Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
    '//  Determines the intersection point of the line segment defined by points A and B
    '//  with the line segment defined by points C and D.
    '//
    '//  Returns YES if the intersection point was found, and stores that point in X,Y.
    '//  Returns NO if there is no determinable intersection point, in which case X,Y will
    '//  be unmodified.

    Dim distAB, theCos, theSin, newX, ABpos As Double

    '//  Fail if either line segment is zero-length.
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)

    '//  Fail if the segments share an end-point.
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)

    '//  (1) Translate the system so that point A is on the origin.
    bx -= ax
    by -= ay
    cx -= ax
    cy -= ay
    dx -= ax
    dy -= ay

    '//  Discover the length of segment A-B.
    distAB = Math.Sqrt(bx * bx + by * by)

    '//  (2) Rotate the system so that point B is on the positive X axis.
    theCos = bx / distAB
    theSin = by / distAB
    newX = cx * theCos + cy * theSin
    cy = cy * theCos - cx * theSin
    cx = newX
    newX = dx * theCos + dy * theSin
    dy = dy * theCos - dx * theSin
    dx = newX

    '//  Fail if segment C-D doesn't cross line A-B.
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)

    '//  (3) Discover the position of the intersection point along line A-B.
    ABpos = dx + (cx - dx) * dy / (dy - cy)

    '//  Fail if segment C-D crosses line A-B outside of segment A-B.
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)

    '//  (4) Apply the discovered position to line A-B in the original coordinate system.
    '*X=Ax+ABpos*theCos
    '*Y=Ay+ABpos*theSin

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function

Answer 13

Found the answers here rather irritating. There is a short tutorial on geometry concept on topcoder which helped me.

http://www.topcoder.com/tc?module=Static&amp;d1=tutorials&amp;d2=geometry2