• Advertisement

Archived

This topic is now archived and is closed to further replies.

Very Simple Q: Intersection of 2d Vectors

This topic is 5754 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How do I find the intersection of 2 2d vectors? Or better yet 2 2D segments, which is the same thing of course but easier for me to understand I would think ByteMe95::~ByteMe95() My S(h)ite

Share this post


Link to post
Share on other sites
Advertisement
A good way to find the intersection between two lines is to use determinants to solve a system of equations.

So, basically, you have two line equations:

ax + by = c
dx + ey = f

First, take the detiminant of a, b, c and d like this:

|a b| = ae - bd = p
|d e|


If this value (p) is equal to 0, then the two lines are parallel, and will never intersect.

If not, then you take the same determinant, except for you replace a column with c and f, like this:


|c b| = ce - bf = q
|f e|


And the other determinant like this:


|a c| = af - cd = r
|d f|


And finally, to calculate the intersection, you use the formula

x = q / p
y = r / p


It''s easy to check whether or not these values are bounded by a line segment, so that part shouldn''t give you any trouble.


NickW

Share this post


Link to post
Share on other sites
NickW did the explaining, here''s some source. You only give the beginning and ending coordinates to this function and get the results. Replace ints with floats if necessary

  
/*-----------------------------------------------------
2-dimensional line intersection test
Input: line a and line b (1=beginning, 2=end)
Output: true == collision
-------------------------------------------------------*/


bool 2dIntersect(int xa1, int ya1, int xa2, int ya2, int xb1, int yb1, int xb2, int yb2)
{
int jako,luku;

//trivial cases

if (ya1 < ya2)
{
if (yb1 < ya1 && yb2 < ya1) return false;
if (yb1 > ya2 && yb2 > ya2) return false;
}
else
{
if (yb1 < ya2 && yb2 < ya2) return false;
if (yb1 > ya1 && yb2 > ya1) return false;
}

if (xa1 < xa2)
{
if (xb1 < xa1 && xb2 < xa1) return false;
if (xb1 > xa2 && xb2 > xa2) return false;
}
else
{
if (xb1 < xa2 && xb2 < xa2) return false;
if (xb1 > xa1 && xb2 > xa1) return false;
}

jako = (xa2 - xa1) * (yb2 - yb1) - (xb2 - xb1) * (ya2 - ya1);

//parallel lines or one of the lines is a point

if (jako == 0) return false;

luku = (xb2 - xb1) * (ya1 - yb1) - (yb2 - yb1) * (xa1 - xb1);

if (jako > 0)
{
if (luku >= 0 && luku <= jako)
{
luku = (xa2 - xa1) * (ya1 - yb1) - (ya2 - ya1) * (xa1 - xb1);

if (luku >= 0 && luku <= jako) return true;
}
}
else
{
if (luku <= 0 && luku >= jako)
{
luku = (xa2 - xa1) * (ya1 - yb1) - (ya2 - ya1) * (xa1 - xb1);

if (luku <= 0 && luku >= jako) return true;
}
}

return false;
}

Share this post


Link to post
Share on other sites
hmm, civ guy can that code be adjusted to give the actual coordinates of the intersection? That''s what I really need

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
y1 = a1x + b1
y2 = a2x + b2

y1 = y2
a1x + b1 = a2x + b2
(a1 - a2) * x = b2 - b1

So here''s all you need:
x = (b2 - b1) / (a1 - a2)
y = a1x + b1

Cédric

P.S. To anyone: how can I make spaces that won''t be eaten up by the forum system? I wanted to write
x = b2 - b1
-------
a1 - a2
like Timkin does, because it looks so much nicer, but it doesn''t work for me...

Share this post


Link to post
Share on other sites
hehe... embed your maths within code tags (not source tags) and play around with the spacing... it sometimes takes a couple of edits to get it right... but it looks good in the end! Also, be careful of bold (as with vectors) as it adds extra spaces in because of the altered font size.

Cheers,

Timkin

[edited by - Timkin on April 22, 2002 4:35:53 AM]

Share this post


Link to post
Share on other sites

  • Advertisement