line intersection

safra · 2009-03-22 07:10:47

Hi,

I am coding something and need to know if the line between points AB and the line between points CD intersect. So I can get the direction of both lines by subtracting Vector B from A and D from C.

I remember from math classes a long while how to find x and y values of 2 lines when they are known like something like this:

Ax+By=C

but how can you get the intersection point out of 2 vectors like described above?

Raoul

luca-deltodesco · 2009-03-22 07:51:06

I think you mean putting the lines into the form y = mx + c, i would suggest against this as it will not deal with vertical lines for a start.
There is an easier way working with lines parametrically as rays.

You 'can' solve for s and t in this manner, but it is quite messy.
It easier to think about it another way:

If you take the vector from one of the starting points 'a' or 'c', to the intersection point, that vector will be parallel to the corresponding starting point, so if the intersection point is f, then (f-a) is parallel to v, and (f-c) is parallel to q
to know if two vectors are parallel, we take the dot product and if they are paralell the dot product will be equal to (plus/minus) the length of the two vectors multiplied together. However, we can think of this another way again, and by rotating (f-a) and (f-c) by 90 degrees, we can instead check that the perpendicular vector to (f-a) is perpendicular to v, and the perpendicular vector to (f-c) is perpendicular to q, this is easier to do since to check if two vectors are perpendicular we are only checking if their dot product is 0.

All that remains to test whether the two line segements intersect is to check that both s and t are betweeen 0 and 1, and if both of them are, then you can find the point of intersection by plugging either s or t into their respective ray equations for the lines

The equations have been set out so that the least amount of computation is needed, so to calculate s,t i would have:

// a {x,y}, b {x,y}, c {x,y}, d {x,y}
\\ v {}, q {}
\\ amc {}, denom, s, t

v.x = b.x-a.x;
v.y = b.y-a.y;
q.x = d.x-c.x;
q.y = d.y-c.y;

denom = v.y*q.x - v.x*q.y;
if(denom ~=~ 0) { /*no intersection, or the lines are colinear*/ return; }
denom = 1/denom;

amc.x = c.x-a.x;
amc.y = c.y-a.y;

t = (amc.y*q.x - amc.x*q.y)*denom;
if( t < 0 || t > 1 ) { /*no intersection*/ return; }

s = (amc.y*v.x - amc.x*v.y)*denom;
if( s < 0 || s > 1 ) { /*no intersection*/ return; }

/*intersection*/ return {a.x + t*v.x, a.y + t*v.y }

Last edited by luca-deltodesco (2009-03-23 09:14:42)

gnitsuk · 2009-03-23 00:31:29

Don't use y = mx + c form as indeed vertical lines are not representable this way.

Use the more general form ax + by = d.

So your two lines will be:

and

So you now solve the matrix equation:

Check determinant of matrix is not zero then solve system. Check that solutions for x and y lie between x and y extremities of line segments given.

safra · 2009-03-23 06:33:01

Many thanks luca-deltodesco. I read your reply this morning and did a quick test. It didn't work but I have to do more tests. I just wanted to say thanks a lot for your big post.

Just to be sure, I have never seen this operator ~=~

Is it like !=
?

luca-deltodesco · 2009-03-23 09:12:58

safra wrote:

Many thanks luca-deltodesco. I read your reply this morning and did a quick test. It didn't work but I have to do more tests. I just wanted to say thanks a lot for your big post.

i took a quick look and i made a few typos when doing it (I did it in a hurry) I've corrected them now

safra wrote:

Just to be sure, I have never seen this operator ~=~
Is it like !=
?

it's just to mean approximately equal to, since you should never use == and != with floating point numbers in such an application as rounding errors can occur.

---

Gutsnik's method, whilst valid is far more convoluted than my own involving far more computation.

Last edited by luca-deltodesco (2009-03-23 09:39:45)

safra · 2009-03-23 10:25:27

gnitsuk, thanks for your reply, I missed it! I am not really into matrices and just don't have an idea how to put your solution into code.

luca-deltodesco , I will try your updated code tomorrow.

bossk171 · 2009-03-23 10:55:11

I asked a similar question a while back. Nothing ever became of the game I was working on, but the response (similar to those here) were very helpful:

http://www.mathisfunforum.com/viewtopic.php?id=8541

It seems as though Luca-Deltodesco is a bit of an expert on the subject...

kuadratic · 2009-03-23 12:36:12

the best tutorials i've ever read about finding the intersections of vectors is here http://www.tonypa.pri.ee/vectors/start.html . Also, these were written with the idea of coding vectors and collisions in games. enjoy

luca-deltodesco · 2009-03-23 21:13:23

kuadratic wrote:

the best tutorials i've ever read about finding the intersections of vectors is here http://www.tonypa.pri.ee/vectors/start.html . Also, these were written with the idea of coding vectors and collisions in games. enjoy

The method they present is the same as my own

safra · 2009-03-24 10:06:32

Thanks a lot guys, I got it working!

Math Is Fun Forum

#1 2009-03-22 07:10:47

line intersection

#2 2009-03-22 07:51:06

Re: line intersection

#3 2009-03-23 00:31:29

Re: line intersection

#4 2009-03-23 06:33:01

Re: line intersection

#5 2009-03-23 09:12:58

Re: line intersection

#6 2009-03-23 10:25:27

Re: line intersection

#7 2009-03-23 10:55:11

Re: line intersection

#8 2009-03-23 12:36:12

Re: line intersection

#9 2009-03-23 21:13:23

Re: line intersection

#10 2009-03-24 10:06:32

Re: line intersection

Board footer