Someone please explain this intersection test function

Question

I'm looking over a few functions provided in a geometry class and I found this very poorly commented function that apparently tests whether or not there is an intersection between two lines. Can someone please explain to me how this works?

inline bool LineIntersection2D(Vector2D A,
                               Vector2D B,
                               Vector2D C, 
                               Vector2D D)
{
   double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y);
   double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y);

   double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);

   if (Bot == 0)//parallel
   {
      return false;
   }

    double invBot = 1.0/Bot;
    double r = rTop * invBot;
    double s = sTop * invBot;

    if( (r > 0) && (r < 1) && (s > 0) && (s < 1) )
    {
        //lines intersect
        return true;
    }

//lines do not intersect
return false;
}

From what I've gathered, A and B are the two points of the first line and C and D are the two points of the second. After that I'm totally lost. Thanks in advance!

Do you understand the line intersection equation in general? Not this function, but the mathematical equation. — Carcigenicate, Oct 09 '16 at 21:24
I would say, step 1, make you you understand the equation separate from the code. Then, look at the code again and see if anything makes more sense to you. — Carcigenicate, Oct 09 '16 at 21:27
BTW, the question is off topic as it stands. This isn't a site to request explanations. — Carcigenicate, Oct 09 '16 at 21:28
If the slopes are the same, lines are parallel (or same line). Otherwise they intersect somewhere, but this code wants the segments to intersect, so it checks that the intersection is between each set of points (by taking a kind of parametric look at heading from one point to the corresponding endpoinr) — Jeremy Kahan, Oct 09 '16 at 21:35
Okay, so I did a quick google search and I found what I expected. Set the two equations equal to each other and solve for y. This is obvious but only the case for lines and not line segments. I'm still having trouble understanding this. — Alden Bernitt, Oct 09 '16 at 21:35
I figured it was off topic but I didnt know where else to ask. — Alden Bernitt, Oct 09 '16 at 21:37
http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect this is the closest I could find but I still don't understand. I know about cross and dot products but my understanding is probably minimal. — Alden Bernitt, Oct 09 '16 at 22:49

Salix alba · Answer 1 · 2016-10-10T15:42:54.940

First lets identify some vectors. Let u = B - A, v = D - C and w = A - C. The first lines

double rTop = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y);
double sTop = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y);
double Bot = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);

translates to

rtop = v X w 
stop = u X w
bot  = u X v

Here u X v is 2D version of the cross-product which gives the signed area of the parallelogram with edges u, v.

Lets assume there is some point P of intersection and we can write

P = r u  + A.

The parameter r will range from 0 to 1 to give the line segment. We can also write

P = s v + C

we can set these equal to each other

r u + A = s v + C

and subtract C

r u + A - C = s v

or

r u + w = s v

this is a 2D vector equation in two variable r and s. We can eliminate either r or s by taking cross product with u or v as u X u = 0.

r u X u + w X u = s v X u

so

w X u = s v X u

and

s = ( w X u ) / ( v X u )

similarly taking cross product with v eliminates s.

r u X v + w X v = s v X v
r u X v + w X v = 0
r = - (w X v) / (u X v)
r = ( v X w )/ (u X v)

There is a sign adrift somewhere, but I hope it gives the gist.

Both r and s must be between 0 and 1 for the intersection point to lie on the segments.

We can interpret this geometrically. Lets take the example where u is horizontal and v is vertical

Now u X v gives the area of the rectangle and w X v gives the area of the parallelogram. We can see that the ratio of two areas is the same as the ratio of the lengths AB to AP.

Here is another view of a more general position case.

sTop = v X w is the area of the parallelogram ACDE and Bot = u X v is the area of the larger parallogram ABFE. The ratio of the two tell you how far along the line AB the point of intersection is.

Okay, but why are we defining these vectors: u, v, and w. What do they represent, respectively? — Alden Bernitt, Oct 10 '16 at 00:41
They make the rest of the calculation easier. u is just the vector from the start to the end of the fist segment. v is the vector from the start to the end of the second segment, and w is the vector from the base of the second segment to the base of the first segment. — Salix alba, Oct 10 '16 at 06:44

Someone please explain this intersection test function

1 Answers1