Archived

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

Out of bounds: Line intersection

This topic is 5584 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

I have a line intersection algorithm which takes 4 points (2 points for each line) and it returns the point at which they intersect. Even though the lines are finite, the algorithm returns the point at which they intersect even if it''s beyond the points which define the bounds of the lines. So I need to determine if the intersection point returned is out of bounds. One way I thought of doing this is: Sort the x coordinate of the 4 points in ascending order. The middle two coordinates become the bounds for the x plane. Do the same thing for the y plane. I then have a bounding box that I can check to see if the intersection point is within. I haven''t coded this yet but I assume it will work. I just wanted to see if anyone knew of an algorithm which, given the above information can simply tell me if the intersection point is within the bounds defined by the 4 points. Thanks, Jules.

Share this post


Link to post
Share on other sites
Actually, I wrote a chapter for the book "Game Programming Gems II" which covers the finite length line segment intersection problem in detail. It has the mathematical derivations, full working source code and sample program included. I know this is a bit of a plug, .

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
There is an easier way than computing the bouding rectangle. You just need to see if the intersection point sits along the first line.

Simply get the line vector (Point1-Point2) and then do a simply < and > check to ensure the point of intersection is inside the vector.

Im not very good at explaining this, so here''s my code that I use for intersection:



  
bool ACollision::LineIntersect(float Ax, float Ay, float Bx, float By,
float Cx, float Cy, float Dx, float Dy)
{
// line intersection test

float s1 = (Cy - Dy) * (Bx - Ax) - (Cx - Dx) * (By - Ay);
if (s1 == 0)
{
// Lines don''t intersect

return false;
}
float s2 = ((Cy - Ay) * (Bx - Ax) - (Cx - Ax) * (By - Ay)) / s1;
if (s2 < 0 || s2 > 1)
{
// Lines don''t intersect

return false;
}

// intersection point

float Px = Cx + s2 * (Dx - Cx);
float Py = Cy + s2 * (Dy - Cy);
float abx=Ax-Bx;
float aby=Ay-By;
if (abx<0.0f)
abx=-(abx);
if (aby<0.0f)
aby=-(aby);
if ((Px-Ax<abx) && (Py-Ay<aby))
return true;

return false;


}


Basically, I take in the four points (Ax,Ay, Bx,By, Cx,Cy, Dx, Dy), check for intersection, if intersection I get the point of intersection (Px,Py). I then get the vector of the line (crudely here using abx and aby). Then make sure it''s a positive number and do the < and > checks.

Share this post


Link to post
Share on other sites
quote:
Original post by grhodes_at_work
Actually, I wrote a chapter for the book "Game Programming Gems II" which covers the finite length line segment intersection problem in detail. It has the mathematical derivations, full working source code and sample program included. I know this is a bit of a plug, .

Tsk, tsk, tsk... Not helpful at all; this would deserve to be moderated.

...

If I understand correctly, you''ve got a point (x,y) and you want to know if it is on the line (x0,y0) - (x1,y1)? Either do a bounding rectangle test, or do this:

t = (x - x0) / (x1 - x0)
if(0 < t < 1) Point is on the line, else point is not

You could also do it with y. In fact, if x1 == x0, you have to use y, because it will result in a division by 0, so it''s an additional test. I don''t know if it''s faster than a bounding rectangle test... Probably not. I almost wish I could copy Graham''s code from Game Programming Gems 2 to punish his uselessness.

Cédric

Share this post


Link to post
Share on other sites
haha. Nice plug Rhodes. This is the place you're meant to help people out of the goodness of your heart. ie. for free I'm sure you've already made enough dosh off that book.
Thanks Damocles, that is heaps helpful. As I don't fully understand the maths, I just had the two long lines of computation to give me the points which I see you've split up first to determine if an intersection even occured. Way quicker than my idea.
Am I right in thinking that s1 and s2 are used to determine if the lines intersect at all? ie. They're not parallel.
I understand the rest of it. It works great.
Thanks cedricl and Extrarius. That's helpful info. That site is excellent Extrarius. I'm always looking for helpful sites like that but they usually consist of information teasers and then make you pay for the rest.
Cheers,
Jules.

[edited by - joolean on August 29, 2002 11:19:14 AM]

Share this post


Link to post
Share on other sites