Take the 2-minute tour ×

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

share|improve this question
It might help to think of the edges of the rectangle as separate lines instead of the complete polygon. –  Ryan Graham Feb 18 '09 at 22:53
You might find some useful information in the question I previously asked about this very topic (but with GDI+) at stackoverflow.com/questions/153592/…. –  Robert S. Feb 19 '09 at 3:20
Do you want to know (A) where two line segments intersect or (B) whether or not two lines intersect (C) whether or not two line segments intersect (D) where two lines intersect? Could you please make your title consistent with your question? –  moose Feb 23 '13 at 15:29
add comment

16 Answers

There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product v × w to be vx wy − vy wx (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 + t r (for a scalar parameter t) and any point on the second line as q + u s (for a scalar parameter u).

Two line segments intersecting

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

p + t r = q + u s

Formulae for the point of intersection

Cross both sides with s, getting

(p + t r) × s = (q + u s) × s

And since s × s = 0, this means

t (r × s) = (qp) × s

And therefore, solving for t:

t = (qp) × s / (r × s)

In the same way, we can solve for u:

(p + t r) × r = (q + u s) × r

u (s × r) = (pq) × r

u = (pq) × r / (s × r)

To reduce the number of computation steps, it's convenient to rewrite this as follows (remembering that s × r = − r × s):

u = (qp) × r / (r × s)

Now there are five cases:

  1. If r × s = 0 and (q − p) × r = 0, then the two lines are collinear. If in addition, either 0 ≤ (q − p) · rr · r or 0 ≤ (p − q) · ss · s, then the two lines are overlapping.

  2. If r × s = 0 and (q − p) × r = 0, but neither 0 ≤ (q − p) · rr · r nor 0 ≤ (p − q) · ss · s, then the two lines are collinear but disjoint.

  3. If r × s = 0 and (q − p) × r ≠ 0, then the two lines are parallel and non-intersecting.

  4. If r × s ≠ 0 and 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1, the two line segments meet at the point p + t r = q + u s.

  5. Otherwise, the two line segments are not parallel but do not intersect.

(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 Goldman, 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.)

share|improve this answer
This is essentially the same technique as mine, but I use the dot product instead of cross product. In this case, I believe the efficiency is approximentally identical. –  Jason Cohen Mar 15 '09 at 17:00
Excellent solution. Thanks Gareth for your valuable answer. –  Wodzu Nov 29 '09 at 13:19
@myrkos: No. The first line segment runs "from p to p + r" so when it's represented in parametric terms as "p + tr" then the segment corresponds to 0 ≤ t ≤ 1. Similarly for the other segment. –  Gareth Rees Jan 31 '12 at 17:48
For those interested, here is a simple C# implementation, taking PointF start and end coordinates for lines, that seems to be working: ideone.com/PnPJgb –  Matt Dec 17 '12 at 0:42
I put together a JavaScript implementation following @Matt. I made corrections for the errors pointed out by Tekito. –  pgkelley Aug 29 '13 at 4:10
show 28 more comments

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

        // 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. :(

share|improve this answer
Thanks Gavin - the solution you mention is the one that works best for me too. –  Shunyata Kharg Jan 4 '10 at 12:12
function getLineIntersection(p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x, p3_y) { var 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; var 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); –  cortijon Dec 19 '12 at 15:27
if (s >= 0 && s <= 1 && t >= 0 && t <= 1) { // Collision detected var intX = p0_x + (t * s1_x); var intY = p0_y + (t * s1_y); return [intX, intY]; } return null; // No collision } –  cortijon Dec 19 '12 at 15:28
Great answer! But crap. I just spent like 15 minutes porting it to JavaScript only to find that someone already did it. D: –  Cheezey May 18 '13 at 17:02
good algorithm, however fyi it doesn't handle cases where the determinant is 0. (the -s2_x * s1_y + s1_x * s2_y above). If it's 0 (or near 0) the lines are parallel or collinear. If it's collinear then the intersection may be another line segment. –  seand Jul 5 '13 at 22:56
show 5 more comments

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.


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
share|improve this answer
This algorithm is nice. But there is a hole in it as pointed to by Dan @ stackoverflow.com/questions/563198/… & Elemental @ stackoverflow.com/questions/563198/… It would be cool if you would update your answer for future reference. Thanks. –  Chantz Oct 6 '09 at 1:45
Is this algorithm numerically stable? I've tried a similliar aproach and it turned out to give weird results when working on floats. –  milosz Aug 1 '10 at 8:57
There seems to be another problem with this algorithm. When it's fed the points A={1, 0} B={2, 0} C={0, 0} D={1,0}, although the line segments clearly touch at an end, F*P (and also E*Q, in line with the user below's fix) are both 0, thus causing division by 0 to find h and g. Still working on the solution for this one, but I thought the problem was worth pointing out. –  candrews Feb 27 '11 at 6:24
This answer is simply incorrect. Try A={0,0}, B={0,1}, C={0,2} D={2,0} –  Tim Cooper Dec 23 '12 at 14:32
A + E*g = C + F*h The two lines intersect if and only if the solution to that equation (assuming they are not parallel) has both, g and h between 0 and 1 (in- or exclusive, depending on whether you count touching at an end point). –  Daniel Fischer Dec 23 '12 at 16:23
show 5 more comments

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

share|improve this answer
I've been pulling my hair out trying to figure out why the accepted answer wasn't working for me. Thanks so much! –  Matt Bridges Aug 22 '09 at 18:40
Also notable that the boundary conditions work in this case (i.e for h=0 or h=1 or g=0 or g=1 the lines 'just' touch –  Elemental Oct 7 '09 at 8:34
add comment

The answer once accepted here is incorrect (it has since been unaccepted, so hooray!). 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.

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:


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.


share|improve this answer
The "accepted" answer can change, so you should call it something else. (In fact, I think it has changed since your comment) –  Johannes Hoff Feb 15 '13 at 21:21
add comment

Here's an improvement to Gavin's answer. marcp's solution is similar also, but neither postpone the division.

This actually turns out to be a practical application of Gareth Rees' answer as well, because the cross-product's equivalent in 2D is the perp-dot-product, which is what this code uses three of. Switching to 3D and using the cross-product, interpolating both s and t at the end, results in the two closest points between the lines in 3D. Anyway, the 2D solution:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y, 
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;

Basically it postpones the division until the last moment, and moves most of the tests until before certain calculations are done, thereby adding early-outs. Finally, it also avoids the division by zero case which occurs when the lines are parallel.

You also might want to consider using an epsilon test rather than comparison against zero. Lines that are extremely close to parallel can produce results that are slightly off. This is not a bug, it is a limitation with floating point math.

share|improve this answer
The most elegant solution. Thank you. –  Ray Feb 19 '13 at 9:58
Fails if some of the points have a value of 0.. that should not happen right? –  hfossli Feb 20 '13 at 15:21
I've made a correction for a bug introduced when deferring the divide. t could be positive when the numer and denom were both negative. –  iMalc Apr 2 '13 at 5:05
add comment

Question C: How do you detect whether or not two line segments intersect?

I have searched for the same topic and I wasn't happy with the answers. So I have written an article that explains very detailed how to check if two line segments intersect with a lot of images. There is complete (and tested) Java-code.

Here is the article, cropped to the most important parts:

The algorithm, that checks if line segment a intersects with line segment b, looks like this:

enter image description here

What are bounding boxes? Here are two bounding boxes of two line segments:

enter image description here

If both bounding boxes have an intersection, you move line segment a so that one point is at (0|0). Now you have a line through the origin defined by a. Now move line segment b the same way and check if the new points of line segment b are on different sides of line a. If this is the case, check it the other way around. If this is also the case, the line segments intersect. If not, they don't intersect.

Question A: Where do two line segments intersect?

You know that two line segments a and b intersect. If you don't know that, check it with the tools I gave you in "Question C".

Now you can go through some cases and get the solution with 7th grade math (see code and interactive example).

Question B: How do you detect whether or not two lines intersect?

Lets say your point A = (x1, y1), point B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Your first line is definied by AB (with A != B), your second one by CD (with C != D).

function doLinesIntersect(AB, CD) {
    if (x1 == x2) {
        return !(x3 == x4 && x1 != x3);
    } else if (x3 == x4) {
        return true;
    } else {
        // both lines are not parallel to the y-axis
        m1 = (y1-y2)/(x1-x2);
        m2 = (y3-y4)/(x3-x4);
        return m1 != m2;

Question D: Where do two lines intersect?

Check with Question B if they intersect at all.

The lines a and b are defined by two points for each line. You can basically apply the same logic was used in Question A.

share|improve this answer
To be clear, the Question B in this answer is truly about two lines intersecting, not line segments. I'm not complaining; it's not incorrect. Just don't want anyone to be misled. –  phord Jul 16 '13 at 3:46
add comment

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  

   // calculate the lengths of the two lines  

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

   // 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);  

   // calculate the combined length of the two segments  
   // between Pt-p1 and Pt-p2  

   // calculate the combined length of the two segments  
   // between Pt-p3 and Pt-p4  

   // 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;  
share|improve this answer
There are several problems with this code. It can raise an exception due to division by zero; it's slow because it takes square roots; and it sometimes returns false positives because it uses a fudge factor. You can do better than this! –  Gareth Rees Feb 19 '09 at 23:14
Okay as a solution but that given by Jason is definitely computationally quicker and avoids a lot of the problems with this solution –  Elemental Oct 6 '09 at 8:17
add comment

Just wanted to mention that a good explanation and explicit solution can be found in the Numeric Recipes series. I've got the 3rd edition and the answer is on page 1117, section 21.4. Another solution with a different nomenclature can be found in a paper by Marina Gavrilova Reliable Line Section Intersection Testing. Her solution is, to my mind, a little simpler.

My implementation is below:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
   return (x >= x0) && (x <= x1);

bool NuGeometry::FindIntersection(const double& x0, const double& y0, 
     const double& x1, const double& y1,
     const double& a0, const double& b0, 
     const double& a1, const double& b1, 
     double& xy, double& ab) {
   // four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
   // returned values xy and ab are the fractional distance along xy and ab
   // and are only defined when the result is true

   bool partial = false;
   double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
   if (denom == 0) {
      xy = -1;
      ab = -1;
   } else {
      xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
      partial = NuGeometry::IsBetween(0, xy, 1);
      if (partial) {
         // no point calculating this unless xy is between 0 & 1
         ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom; 
   if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
      ab = 1-ab;
      xy = 1-xy;
      return true;
   }  else return false;
share|improve this answer
add comment

Processing.js has a demo with sample code.

share|improve this answer
add comment

C and Objective-C

Based on Gareth Rees' answer

typedef union AGPoint {
    struct { double x, y; };
    double v[2];
} AGPoint;

typedef union AGLine {
    struct { AGPoint start, end; };
    double v[2];
} AGLine;

BOOL AGLineIntersection(AGLine l1, AGLine l2, AGPoint *out_pointOfIntersection)
    AGPoint p = l1.start;
    AGPoint q = l2.start;
    AGPoint r = AGPointSubtract(l1.end, l1.start);
    AGPoint s = AGPointSubtract(l2.end, l2.start);

    double s_r_crossProduct = AGPointCrossProduct(r, s);
    double t = AGPointCrossProduct(AGPointSubtract(q, p), s) / s_r_crossProduct;
    double u = AGPointCrossProduct(AGPointSubtract(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
        if(out_pointOfIntersection != NULL)
            *out_pointOfIntersection = AGPointZero;
        return NO;
        if(out_pointOfIntersection != NULL)
            AGPoint i = AGPointAdd(p, AGPointMultiply(r, t));
            *out_pointOfIntersection = i;
        return YES;

extern AGPoint AGPointSubtract(AGPoint p1, AGPoint p2)
    return (AGPoint){p1.x - p2.x, p1.y - p2.y};

extern double AGPointCrossProduct(AGPoint p1, AGPoint p2)
    return (p1.x * p2.y) - (p1.y * p2.x);

extern AGPoint AGPointAdd(AGPoint p1, AGPoint p2)
    return (AGPoint){p1.x + p2.x, p1.y + p2.y};

extern AGPoint AGPointMultiply(AGPoint p1, double factor)
    return (AGPoint){p1.x * factor, p1.y * factor};

Many of the functions and structs are private, but you should pretty easy be able to know what's going on. This is public on this repo https://github.com/hfossli/AGGeometryKit/

share|improve this answer
add comment

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

From Mathworks (author: Douglas Schwarz):


share|improve this answer
Thanks to your link, I have found Fast Line Segment Intersection, by U. Murat Erdem (2010) and a link to an explanation by Paul Bourke (1989). –  Wok May 8 '11 at 15:20
add comment

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

With a little modification to his code I now have this function that will return the point of intersection or if no intersection is 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.

    '//  Success.
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function
share|improve this answer
add comment

I tried lot of ways and then I decided to write my own. So here it is:

bool IsBetween (float x, float b1, float b2)
   return ( ((x >= (b1 - 0.1f)) && 
        (x <= (b2 + 0.1f))) || 
        ((x >= (b2 - 0.1f)) &&
        (x <= (b1 + 0.1f))));

bool IsSegmentsColliding(   POINTFLOAT lineA,
                POINTFLOAT lineB,
                POINTFLOAT line2A,
                POINTFLOAT line2B)
    float deltaX1 = lineB.x - lineA.x;
    float deltaX2 = line2B.x - line2A.x;
    float deltaY1 = lineB.y - lineA.y;
    float deltaY2 = line2B.y - line2A.y;

    if (abs(deltaX1) < 0.01f && 
        abs(deltaX2) < 0.01f) // Both are vertical lines
        return false;
    if (abs((deltaY1 / deltaX1) -
        (deltaY2 / deltaX2)) < 0.001f) // Two parallel line
        return false;

    float xCol = (  (   (deltaX1 * deltaX2) * 
                        (line2A.y - lineA.y)) - 
                    (line2A.x * deltaY2 * deltaX1) + 
                    (lineA.x * deltaY1 * deltaX2)) / 
                 ((deltaY1 * deltaX2) - (deltaY2 * deltaX1));
    float yCol = 0;
    if (deltaX1 < 0.01f) // L1 is a vertical line
        yCol = ((xCol * deltaY2) + 
                (line2A.y * deltaX2) - 
                (line2A.x * deltaY2)) / deltaX2;
    else // L1 is acceptable
        yCol = ((xCol * deltaY1) +
                (lineA.y * deltaX1) -
                (lineA.x * deltaY1)) / deltaX1;

    bool isCol =    IsBetween(xCol, lineA.x, lineB.x) &&
            IsBetween(yCol, lineA.y, lineB.y) &&
            IsBetween(xCol, line2A.x, line2B.x) &&
            IsBetween(yCol, line2A.y, line2B.y);
    return isCol;

Based on these two formulas: (I simplified them from equation of lines and other formulas)

formula for x

formula for y

share|improve this answer
add comment

Python version of iMalc's answer:

def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision

    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]

    return intersection_point
share|improve this answer
add comment

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.

share|improve this answer
Note that this was a reasonable answer to the question as originally framed but now that the question has been edited heavily it doesn't make so much sense. –  Ganesh Sittampalam Jan 10 at 22:12
add comment

Your Answer


