How do you detect where two line segments intersec

Question

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

Answer 1

I read these algorithm from the book "multiple view geometry"

following text using

' as transpose sign

* as dot product

x as cross product, when using as operator

1. line definition

a point x_vec = (x, y)' lies on the line ax + by + c = 0

we denote L = (a, b, c)', the point as (x, y, 1)' as homogeneous coordinates

the line equation can be written as

(x, y, 1)(a, b, c)' = 0 or x' * L = 0

2. intersection of lines

we have two lines L1=(a1, b1, c1)', L2=(a2, b2, c2)'

assume x is a point, a vector, and x = L1 x L2 (L1 cross product L2).

be careful, x is always a 2D point, please read homogeneous coordinates if you are confused about (L1xL2) is a three elements vector, and x is a 2D coordinates.

according to triple product, we know that

L1 * ( L1 x L2 ) = 0, and L2 * (L1 x L2) = 0, because of L1,L2 co-plane

we substitute (L1xL2) with vector x, then we have L1*x=0, L2*x=0, which means x lie on both L1 and L2, x is the intersection point.

be careful, here x is homogeneous coordinates, if the last element of x is zero, it means L1 and L2 are parallel.

Answer 2

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

Answer 3

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:

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

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?

Let's say your point A = (x1, y1), point B = (x2, y2), C = (x_3, y_3), D = (x_4, y_4). Your first line is defined by AB (with A != B), and 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.

Answer 4

Based on t3chb0t's answer:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
   //L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
   int d;
   d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
   if(!d)
       return 0;
   p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
   p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
   return 1;
}

int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
    return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;

}

int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
    if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
        return 0;

    return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

Answer 5

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 p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_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.

Answer 6

Plenty of solutions are available above, but I think below solution is pretty simple and easy to understand.

Two segments Vector AB and Vector CD intersect if and only if

1. The endpoints a and b are on opposite sides of the segment CD.
2. The endpoints c and d are on opposite side of the segment AB.

More specifically a and b are on opposite side of segment CD if and only if exactly one of the two triples a,c,d and b,c,d is in counterclockwise order.

Intersect(a, b, c, d)
 if CCW(a, c, d) == CCW(b, c, d)
    return false;
 else if CCW(a, b, c) == CCW(a, b, d)
    return false;
 else
    return true;

Here CCW represent counterclockwise which returns true/false based on the orientation of the points.

Source : http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Page 2