LoginLogin
Nintendo shutting down 3DS + Wii U online services, see our post

Line & Rectangle Intersection

Root / Programming Questions / [.]

MZ952Created:
So I'm starting to build a library for determining collision between different types of objects. I'm having difficulty determining intersection between a line and a rectangle. I thought it was simple when I first started thinking about it. Here's how I attempted it: 1.) Find the slope of the line. 2.) Find the maximum & minimum heights and widths of the rectangle. 3.) Use the slope to determine the (x or y) component by multiplying the slope by the (y or x) component. 4.) Check to see if the (x or y) component fits within the (x or y) range given by the length of that side of the rectangle. So basically, if you think about drawing a box and then an arbitrary line through it (or not), the algorithm I attempted was to find out where the x (or y) component existed at a given y (or x), which was the minimum and maximums of the rectangle. I received nothing pretty, it returns to me a detection area that resembles a ray around the vicinity of the rectangle. My knowledge of mathematics is far from pristine. Is there a better way?

Perhaps find the point on the line closest to the center of the rectangle and then check if it's inside the rectangle.

If you have a line segment given by (ax, ay)- (bx, by) and a rectangle given by (cx, cy) - (dx, dy) (where cx, cy, and dx, dy are the top left and bottom right corners of the rectangle) you could do a first pass with a rectangle rectangle intersection check treating the line segment as a rectangle. If the two rectangles do not intersect then the line and rectangle will not either. This will be a faster check and I if the intersection is normally false we should get a decent speedup that way. However, if the two rectangles intersect you may have a false positive so on a successful intersection you would have to run another set of tests. For the line segment to intersect the rectangle, it should pierce at least one of the four line segments making up the rectangle. So you would run a line - line intersection test between the original line segment and (cx,cy)-(dx, cy), (dx, cy)-(dx, dy), (cx, dy)-(dx, dy), (cx, cy)-(cx, dy). You can stop testing segments if you find an intersection early. I ripped off a line intersection algorithm from stack overflow for my asteroids game which admittedly is running quite slowly on original 3DS so maybe use this sparingly. But anyway I have typed it in below, I hope it helps (there are probably quite a few type-o's, sorry).
'I GOT THIS FROM STACK OVERFLOW.
'CHECK IF TWO LINE SEGMENTS INTERSECT
DEF LINE_INTERSECT(P0_x#, P0_Y#, P1_X#, P1_Y3, P2_X#, P2_Y#, P3_X#, P3_Y#)
 VAR S02_X#, S02_Y#, S10_X#, S10_Y#
 VAR S32_X#, S32_y#, S_NUMER#, T_NUMER#
 VAR DENOM#, T#, DENOM_POSITIVE%

 'BOUNDING BOX CHECK
 IF (MAX(P0_X#, P1_X#, P2_X#, P3_X#) - MIN(P0_X3, P1_X#, P2_X#, P3_X#) <= ABS(P1_X# - P0_X#) + ABS(P3_X# - P2_X#)) AND (MAX(P0_Y#, P1_Y#, P2_Y#, P3_Y#) - MIN(P0_Y#, P1_Y#, P2_Y#, P3_Y3) <= ABS(P1_Y# - P0_Y#) + ABS(P3_Y#, P2_Y#)) THEN
  S10_X# = P1_X# - P0_X#
  S10_Y# = P1_Y# - P0_Y#
  S32_X# = P3_X# - P2_X#
  S32_Y# = P3_Y# - P2_Y#

 DENOM# = (S10_X# * S32_Y#) - (S32_X# * S10_Y#)

  IF DENOM# == 0.0 THEN
   RETURN FALSE 'COLLINEAR
  ENDIF

  DENOM_POSITIVE% = (DENOM# > 0.0)
  S02_X# = P0_X# - P2_X#
  S02_Y# = P0_Y# - P2_Y#
  S_NUMER# = (S10_X# * S02_Y#) - (S10_Y# * S02_X#)
  IF (S_NUMER# < 0.0) == DENOM_POSITIVE% THEN
   RETURN FALSE 'NO COLLISION
  ENDIF

  T_NUMER# = (S32_X# * S02_Y#) - (S32_Y# * S02_X#)
  IF (T_NUMER# < 0.0) == DENOM_POSITIVE% THEN
   RETURN FALSE 'NO COLLISION
  ENDIF

  IF ((S_NUMER# > DENOM#) == DENOM_POSITIVE%) OR ((T_NUMER#  > DENOM#) == DENOM_POSITIVE%) THEN
   RETURN FALSE 'NO COLLISION
  ENDIF

  'COLLISION DETECTED
  RETURN TRUE
 ELSE
  RETURN FALSE
 ENDIF
END
The described method above will fail if the line segment lies completely within the rectangle. You may need an extra check for that. Anyway, I hope that helps.

Wow. I'm rather impressed (that's an understatement). Stackoverflow is a good site, I had tried a little research for this on geeksforgeeks. I use an alternate format for denoting rectangles, but nothing a little conversion can't handle. I'll definitely give your code a try and get back to you on its functionality, thanks a ton!