Line intersect RECT

Fastest way I can think of is to test each point - if it''s inside the bounds of the rect, the line intersects the rectangle nontangentally. There are probably more clever algorithms out there, but if you implement this one efficiently, and you don''t use super-long lines, there shouldn''t be too much of a slow-down relative to the amount of time it would take to execute more advanced methods.

Later,
ZE.

//email me.//zealouselixir software.//msdn.//n00biez.//
miscellaneous links

[if you have a link proposal, email me.]

http://www.realtimerendering.com/int/ describes many different intersection tests in 3D. A Ray-AABB test is very similar to a Line-AARect test so maybe you should check it out.

Sorry I should have specified its strictly a 2-D game, but I will check out the web site, and if worst comes to worst Ill give the point checking suggestion a go. Thanks for the help.

-Jeff

The problem with checking each point is the case where it crosses completly over the rectangle. The best way I can think of is to check the line against each line making up the rectangle.

What is the formula for seeing if two lines intersect?

To check if the line intersects the rectangle, simply check if each end lies within the rectangle. To find the intersection point, you must (as you said) find the gradient.
Using basic linear algebra.. a line though point (a,b) & (c,d)
has equation:

(b-d)*x+(c-a)*y+d*a-b*c = 0

Now since the edges of the rectangle are along the x and y axis... it is simple to find hte intersection points. you should do this for all 4 sides of the rectangle, and it will provide you with 2 solutions (3 or 4 if it lines up with 1/2 corners exactly)... ie if your rectangle had one corner (e,f) and the opposite one was (g,h) then the edges would be defined by the lines:
x=e,x=g,y=f,y=h.
Substitute these into the equation for the line, to obtain the coordinates for the intersections with the edges. ie:

for the line, x=e: (b-d)*e+(c-a)*y+d*a-b*c=0
solving for y : y=(d*(e-a)+b*(e-c))/(c-a)
now it remains to check if this y value lies between, f&h... if so... this is a point of intersection of the line with the rectangle.

For each one that satisfies the above condition. it is now necessay to check if the point you have found (e,(d*(e-a)+b*(e-c))/(c-a)) actually lies within the ends of the line, and is not a projection of the line. to do this one must check if e lies between a&c, and that d*(e-a)+b*(e-c))/(c-a)) lies between b&d.

If it does.. then you have hte intersection point. If not, you need to try the next edge.

This routine is far from optimal. and by rearraging the checking order you can improve performance (I did not inculde any of htis as it takes half the fun away, but it is no fun, when you don''t know where to start). It is also wise to make special routines for horizontal and vertical lines (as there involve obvious simplifications and in the case of vertical lines. this method will not work as they constitute a singular point in the solution space) also consider the line lying entirely within the rectangle (the routine I detailed copes with this by not producing any intersections, and also copes with the line being entirely separate form the rectangle). I know this sounds overly complex, but it is net very hard to code (with a little thought). Hope this helps anyway

Hey that is really helpfull actually, thanks a ton! The line shouldn''t ever be encapsulated in the rectangle, because I force the ships firing the laser off of each others square for collision detection. I will give it a whirl and see what happens. For vert. and horiz. lines, would you just check if the x or y value is lined up with the rect., and if it is, see if the other end is beyond the rect.?

-Jeff

Yep, thats it exactly.

Hope it works out ok