Archived

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

Michalson

Looking for fast Line-Box 2D collision detection

Recommended Posts

Michalson    1657
I need a function that checks for a collision between an arbitrary line made of 2 points, each point having an X and Y coordinate, and a box defined by the coordinates of the upper left and lower right corner. I have a slow method which checks for a collision between the line and the 2 vertical and 2 horizontal lines of the box, it is slightly optimized to take advantage of the boxes perfect vertical/horizontal lines but I''m thinking there must be an even faster way (I''m not looking for assembly optimizations yet). Anyone out there who can think outside the box? (I didn''t intend that as pun).

Share this post


Link to post
Share on other sites
OldGuy    122
I''m sure that there are some real clever ways, but here is a fairly simple one. Are you comparing the line versus several boxes? If so, it may pay to first reform the line as a rectangle. Then, do a rectangle overlap compare between the ''line rectangle'' and the box.

  
// lbox is the box formed by the line

// box is the box you are checking the line against

if (lbox.left <= box.right &&
lbox.right >= box.left &&
lbox.top <= box.bottom &&
lbox.bottom >= box.top)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
i''m assuming the line is infinite in length.
if not then i had a good time thinking anyways.
you can check on only two lines - the diagonals.

// find y of the line at one side of the box
double t1 = (line.point1.x - line.point2.x) *
(line.point1.y - line.point2.y) /
(box.left - line.point2.x) +
line.point2.y ;

// ditto to other side of box
double t2 = (line.point1.x - line.point2.x) *
(line.point1.y - line.point2.y) /
(box.right - line.point2.x) +
line.point2.y ;

if( t1 < box.top && t2 > box.bottom ||
t2 < box.top && t1 > box.bottom )
then it intersects

Share this post


Link to post
Share on other sites
Michalson    1657
Sorry, the line is not infinite. Think of it as a line of sight algorithm, I''m trying to determine where the box is blocking the line of sight from point A to point B. I''m also trying to avoid any floats as this function is going to get used about 5x10^5 per frame (30 frames per second)

Share this post


Link to post
Share on other sites