#### Archived

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

# Looking for fast Line-Box 2D collision detection

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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)

• ### Forum Statistics

• Total Topics
628354
• Total Posts
2982236

• 10
• 9
• 11
• 24
• 11