Out of bounds: Line intersection
Author
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.
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.
. Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
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:
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.
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.
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
You can always go to http://astronomy.swin.edu.au/~pbourke/geometry/. That website has lots of information on all kidns of intersection tests, which is very usefull for all kinds of projects.
"The Requested Information Is Unknown Or Classified" -Anonymous
"The Requested Information Is Unknown Or Classified" -Anonymous
Author
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement