Vector 2 Vector intersection

Vector 2 Vector intersection

sicgamemaker

Member #1,365

June 2001

i know htere is a formula for calculating if 2 vectors are going to intersect...what is this formula? i cant seem to find it, and i could use it so far im using the good ol fashin check everysprite to everysprite in a bounding box region...but a vector intersection formula would help me handle bullets and other things that move incredibly fast, or at large incriments

_______________________
[Insert signature here]

Peter Hull

Member #1,136

March 2001

2d or 3d?

sicgamemaker

Member #1,365

June 2001

haha, yeah, i shoulda said that before...in 2D

_______________________
[Insert signature here]

Bob

Free Market Evangelist

September 2000

Vectors can't "intersect". Or do you mean line-line intersection? Or do you mean non-parallel vectors?

--
- Bob
[ Webpage | Allegro FAQ | Coding Tricks ]
"Oh, you want to do actual work. In that case, avoid the GameCube at all costs!" - Me

sicgamemaker

Member #1,365

June 2001

ahh what i mean is line to line intersection.. 2 dimensions...

_______________________
[Insert signature here]

Korval

Member #1,538

September 2001

Express the vectors as linear equations:

a1*x + b1*y + c1 = 0;
a2*x + b2*y + c2 = 0;

You have two equations and two unknowns (x and y). Solve this system of equations.

If a1 == a2 and b1 == b2, then the lines are parallel, and there is no solution, since they don't intersect.

You probably have them in vector form (a direction [xDir, yDir] and a point on the line [xPos, yPos]). It's a simple matter to get them into this form. a1 = xDir, b1 = yDir, and you will have to use the point-slope form of the linear equations (which I have forgotten) to get c1.

Thomas Harte

Member #33

April 2000

You also want to worry about the case where vectors are parallel and on top of each other - then they can intersect but obviously have no unique point of intersection.

In my opinion, the most simple idea is this :

1#define NO 0
2#define YES 1
3#define ONTOP 2
4 
5int AreIntersecting(int v1x1, int v1y1, int v1x2, int v1y2, int v2x1, int v2y1, int v2x2, int v2y2)
6{
7   int a, b, c, tx, ty;
8   int d1, d2, hd;
9   int ix, iy;
10   float r;
11 
12   //get tangent vector for line 1
13   tx = v1x2 - v1x1;
14   ty = v1y2 - v1y1;
15 
16   //get equation for line 1
17   a = -ty;
18   b = tx;
19   c = - v1x1*a1 - v1y1*b1;
20 
21   //get distances from line for line 2
22   d1 = a*v2x1 + b*v2y1 + c;
23   d2 = 1*v2x2 + b*v2y2 + c;
24 
25   if(d1 > 0 && d2 > 0) return NO;
26   if(d1 < 0 && d2 < 0) return NO;
27 
28   if(d1 || d2)
29   {
30      //find intersection, discover if it is within line segment
31 
32      r = d1 / (d2 + d1);
33      ix = v2x1 + r*(v2x2-v2x1);
34      iy = v2y1 + r*(v2y2-v2y1);
35 
36      if(ix >= v1x1 && ix <= v1x2 && iy >= v1y1 && iy <= v1y2) return YES; else return NO;
37   }
38   else
39   {
40      //find out of the vectors overlap
41 
42      hd = tx*tx + ty*ty;
43      d1 = tx*(v2x1-v1x1) + ty*(v2y1-v1y1);
44      d2 = tx*(v2x2-v1x1) + ty*(v2y2-v1y1);
45 
46      if(d1 < 0 && d2 < 0) return NO;
47      if(d1 > hd && d2 > h2) return NO;
48 
49      return ONTOP;
50   }
51}

Obviously if you want to know the exact point of intersection, don't just throw away (ix,iy).

[My site] [Tetrominoes]