Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

safra
Member
Registered: 2005-12-03
Posts: 41

line intersection

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

Offline

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

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: line intersection

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)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

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

gnitsuk
Member
Registered: 2006-02-09
Posts: 121

Re: line intersection

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.

Offline

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

safra
Member
Registered: 2005-12-03
Posts: 41

Re: line intersection

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 !=   
?

Offline

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

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: line intersection

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)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

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

safra
Member
Registered: 2005-12-03
Posts: 41

Re: line intersection

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.

Offline

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

bossk171
Member
Registered: 2007-07-16
Posts: 305

Re: line intersection

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...


There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.

Offline

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

kuadratic
Member
Registered: 2009-02-26
Posts: 7

Re: line intersection

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


teacher resources--my online edu dir

Offline

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

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: line intersection

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


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

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

safra
Member
Registered: 2005-12-03
Posts: 41

Re: line intersection

Thanks a lot guys, I got it working!

Offline

Board footer

Powered by FluxBB