Determine if two rectangles overlap each other

Question

I am trying to write a C   program that takes the following inputs from the user to construct rectangles  between 2 and 5   height  width  x-pos  y-pos  All of these rectangles will exist parallel to the x and the y axis  that is all of their edges will have slopes of 0 or infinity   I ve tried to implement what is mentioned in this question but I am not having very much luck   My current implementation does the following      Gets all the vertices for Rectangle 1 and stores them in an array - gt  arrRect1    point 1 x  arrRect1 0   point 1 y  arrRect1 1  and so on       Gets all the vertices for Rectangle 2 and stores them in an array - gt  arrRect2     rotated edge of point a  rect 1 int rot x  rot y  rot x   -arrRect1 3   rot y   arrRect1 2      point on rotated edge int pnt x  pnt y  pnt x   arrRect1 2    pnt y   arrRect1 3      test point  a from rect 2 int tst x  tst y  tst x   arrRect2 0   tst y   arrRect2 1    int value  value    rot x    tst x - pnt x      rot y    tst y - pnt y    cout  lt  lt   Value     lt  lt  value      However I m not quite sure if  a  I ve implemented the algorithm I linked to correctly  or if I did exactly how to interpret this   Any suggestions

User · Accepted Answer

if  RectA Left  lt  RectB Right  amp  amp  RectA Right  gt  RectB Left  amp  amp       RectA Top  gt  RectB Bottom  amp  amp  RectA Bottom  lt  RectB Top      or  using Cartesian coordinates        With X1 being left coord  X2 being right coord  increasing from left to right and   Y1 being Top coord  and Y2 being Bottom coord  increasing from bottom to top -- if this is not how your coordinate system  e g  most computers have the Y direction reversed   swap the comparisons below       if  RectA X1  lt  RectB X2  amp  amp  RectA X2  gt  RectB X1  amp  amp      RectA Y1  gt  RectB Y2  amp  amp  RectA Y2  lt  RectB Y1       Say you have Rect A  and Rect B   Proof is by contradiction  Any one of four conditions guarantees that no overlap can exist    Cond1   If A s left edge is to the right of the B s right edge         -  then A is Totally to right Of B Cond2   If A s right edge is to the left of the B s left edge         -  then A is Totally to left Of B Cond3   If A s top edge is below B s bottom  edge         -  then A is Totally below B Cond4   If A s bottom edge is above B s top edge         -  then A is Totally above B   So condition for Non-Overlap is   NON-Overlap    Cond1 Or Cond2 Or Cond3 Or Cond4  Therefore  a sufficient condition for Overlap is the opposite     Overlap    NOT  Cond1 Or Cond2 Or Cond3 Or Cond4   De Morgan s law says Not  A or B or C or D  is the same as Not A And Not B And Not C And Not D so using De Morgan  we have  Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4  This is equivalent to    A s Left Edge to left of B s right edge   RectA Left  lt  RectB Right   and A s right edge to right of B s left edge   RectA Right  gt  RectB Left   and A s top above B s bottom   RectA Top  gt  RectB Bottom   and A s bottom below B s Top  RectA Bottom  lt  RectB Top    Note 1   It is fairly obvious this same principle can be extended to any number of dimensions  Note 2   It should also be fairly obvious to count overlaps of just one pixel  change the  lt  and or the  gt  on that boundary to a  lt   or a  gt    Note 3  This answer  when utilizing Cartesian coordinates  X  Y  is based on standard algebraic Cartesian coordinates  x increases left to right  and Y increases bottom to top   Obviously  where a computer system might mechanize screen coordinates differently   e g   increasing Y from top to bottom  or X From right to left   the syntax will need to be adjusted accordingly

User · Answer

I have implemented a C  version  it is easily converted to C     public bool Intersects   Rectangle rect       float ulx   Math Max   x  rect x      float uly   Math Max   y  rect y      float lrx   Math Min   x   width  rect x   rect width      float lry   Math Min   y   height  rect y   rect height       return ulx  lt   lrx  amp  amp  uly  lt   lry

User · Answer

Lets say the two rectangles are rectangle A and rectangle B  Let their centers be A1 and B1  coordinates of A1 and B1 can be easily found out   let the heights be Ha and Hb  width be Wa and Wb  let dx be the width x  distance between A1 and B1 and dy be the height y  distance between A1 and B1   Now we can say we can say A and B overlap  when  if   dx  gt  Wa Wb     dy  gt  Ha Hb   returns true

User · Answer

This is a very fast way to check with C   if two rectangles overlap  return std  max rectA left  rectB left   lt  std  min rectA right  rectB right       amp  amp  std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom    It works by calculating the left and right borders of the intersecting rectangle  and then comparing them  if the right border is equal to or less than the left border  it means that the intersection is empty and therefore the rectangles do not overlap  otherwise  it tries again with the top and bottom borders  What is the advantage of this method over the conventional alternative of 4 comparisons  It s about how modern processors are designed  They have something called branch prediction  which works well when the result of a comparison is always the same  but have a huge performance penalty otherwise  However  in the absence of branch instructions  the CPU performs quite well  By calculating the borders of the intersection instead of having two separate checks for each axis  we re saving two branches  one per pair  It is possible that the four comparisons method outperforms this one  if the first comparison has a high chance of being false  That is very rare  though  because it means that the second rectangle is most often on the left side of the first rectangle  and not on the right side or overlapping it  and most often  you need to check rectangles on both sides of the first one  which normally voids the advantages of branch prediction  This method can be improved even more  depending on the expected distribution of rectangles   If you expect the checked rectangles to be predominantly to the left or right of each other  then the method above works best  This is probably the case  for example  when you re using the rectangle intersection to check collisions for a game  where the game objects are predominantly distributed horizontally  e g  a SuperMarioBros-like game   If you expect the checked rectangles to be predominantly to the top or bottom of each other  e g  in an Icy Tower type of game  then checking top bottom first and left right last will probably be faster   return std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom       amp  amp  std  max rectA left  rectB left   lt  std  min rectA right  rectB right     If the probability of intersecting is close to the probability of not intersecting  however  it s better to have a completely branchless alternative   return std  max rectA left  rectB left   lt  std  min rectA right  rectB right        amp  std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom     Note the change of  amp  amp  to a single  amp

User · Answer

This is a very fast way to check with C   if two rectangles overlap  return std  max rectA left  rectB left   lt  std  min rectA right  rectB right       amp  amp  std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom    It works by calculating the left and right borders of the intersecting rectangle  and then comparing them  if the right border is equal to or less than the left border  it means that the intersection is empty and therefore the rectangles do not overlap  otherwise  it tries again with the top and bottom borders  What is the advantage of this method over the conventional alternative of 4 comparisons  It s about how modern processors are designed  They have something called branch prediction  which works well when the result of a comparison is always the same  but have a huge performance penalty otherwise  However  in the absence of branch instructions  the CPU performs quite well  By calculating the borders of the intersection instead of having two separate checks for each axis  we re saving two branches  one per pair  It is possible that the four comparisons method outperforms this one  if the first comparison has a high chance of being false  That is very rare  though  because it means that the second rectangle is most often on the left side of the first rectangle  and not on the right side or overlapping it  and most often  you need to check rectangles on both sides of the first one  which normally voids the advantages of branch prediction  This method can be improved even more  depending on the expected distribution of rectangles   If you expect the checked rectangles to be predominantly to the left or right of each other  then the method above works best  This is probably the case  for example  when you re using the rectangle intersection to check collisions for a game  where the game objects are predominantly distributed horizontally  e g  a SuperMarioBros-like game   If you expect the checked rectangles to be predominantly to the top or bottom of each other  e g  in an Icy Tower type of game  then checking top bottom first and left right last will probably be faster   return std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom       amp  amp  std  max rectA left  rectB left   lt  std  min rectA right  rectB right     If the probability of intersecting is close to the probability of not intersecting  however  it s better to have a completely branchless alternative   return std  max rectA left  rectB left   lt  std  min rectA right  rectB right        amp  std  max rectA top  rectB top   lt  std  min rectA bottom  rectB bottom     Note the change of  amp  amp  to a single  amp

User · Answer

Lets say the two rectangles are rectangle A and rectangle B  Let their centers be A1 and B1  coordinates of A1 and B1 can be easily found out   let the heights be Ha and Hb  width be Wa and Wb  let dx be the width x  distance between A1 and B1 and dy be the height y  distance between A1 and B1   Now we can say we can say A and B overlap  when  if   dx  gt  Wa Wb     dy  gt  Ha Hb   returns true

User · Answer

In the question  you link to the maths for when rectangles are at arbitrary angles of rotation   If I understand the bit about angles in the question however  I interpret that all rectangles are perpendicular to one another   A general knowing the area of overlap formula is   Using the example      1   2   3   4   5   6  1   --- ---                  2      A    --- ---               B       3               --- ---                           4   --- --- --- ---                               5                  C                              6               --- ---    1  collect all the x coordinates  both left and right  into a list  then sort it and remove duplicates  1 3 4 5 6  2  collect all the y coordinates  both top and bottom  into a list  then sort it and remove duplicates  1 2 3 4 6  3  create a 2D array by number of gaps between the unique x coordinates   number of gaps between the unique y coordinates   4   4  4  paint all the rectangles into this grid  incrementing the count of each cell it occurs over       1   3   4   5   6  1   ---       1   0   0   0 2   --- --- ---       1   1   1   0 3   --- --- --- ---       1   1   2   1   4   --- --- --- ---       0   0   1   1   6           --- ---    5  As you paint the rectangles  its easy to intercept the overlaps

User · Answer

In the question  you link to the maths for when rectangles are at arbitrary angles of rotation   If I understand the bit about angles in the question however  I interpret that all rectangles are perpendicular to one another   A general knowing the area of overlap formula is   Using the example      1   2   3   4   5   6  1   --- ---                  2      A    --- ---               B       3               --- ---                           4   --- --- --- ---                               5                  C                              6               --- ---    1  collect all the x coordinates  both left and right  into a list  then sort it and remove duplicates  1 3 4 5 6  2  collect all the y coordinates  both top and bottom  into a list  then sort it and remove duplicates  1 2 3 4 6  3  create a 2D array by number of gaps between the unique x coordinates   number of gaps between the unique y coordinates   4   4  4  paint all the rectangles into this grid  incrementing the count of each cell it occurs over       1   3   4   5   6  1   ---       1   0   0   0 2   --- --- ---       1   1   1   0 3   --- --- --- ---       1   1   2   1   4   --- --- --- ---       0   0   1   1   6           --- ---    5  As you paint the rectangles  its easy to intercept the overlaps

User · Answer

Ask yourself the opposite question  How can I determine if two rectangles do not intersect at all   Obviously  a rectangle A completely to the left of rectangle B does not intersect   Also if A is completely to the right   And similarly if A is completely above B or completely below B   In any other case A and B intersect   What follows may have bugs  but I am pretty confident about the algorithm   struct Rectangle   int x  int y  int width  int height      bool is left of Rectangle const  amp  a  Rectangle const  amp  b       if  a x   a width  lt   b x  return true     return false    bool is right of Rectangle const  amp  a  Rectangle const  amp  b       return is left of b  a      bool not intersect  Rectangle const  amp  a  Rectangle const  amp  b       if  is left of a  b   return true     if  is right of a  b   return true        Do the same for top bottom        bool intersect Rectangle const  amp  a  Rectangle const  amp  b      return  not intersect a  b

User · Answer

I have a very easy solution  let x1 y1 x2 y2  l1 b1 l2 be cordinates and lengths and breadths of them respectively  consider the condition   x2  now the only way these rectangle will overlap is if the point diagonal to x1 y1 will lie inside the other rectangle or similarly the point diagonal to x2 y2 will lie inside the other rectangle  which is exactly the above condition implies

User · Answer

struct point   int x  y      struct rect   point tl  br        top left and bottom right points     return true if rectangles overlap bool overlap const rect  amp a  const rect  amp b        return a tl x  lt   b br x  amp  amp  a br x  gt   b tl x  amp  amp              a tl y  gt   b br y  amp  amp  a br y  lt   b tl y

User · Answer

A and B be two rectangle  C be their covering rectangle    four points of A be  xAleft yAtop   xAleft yAbottom   xAright yAtop   xAright yAbottom  four points of A be  xBleft yBtop   xBleft yBbottom   xBright yBtop   xBright yBbottom   A width   abs xAleft-xAright   A height   abs yAleft-yAright   B width   abs xBleft-xBright   B height   abs yBleft-yBright    C width   max xAleft xAright xBleft xBright -min xAleft xAright xBleft xBright   C height   max yAtop yAbottom yBtop yBbottom -min yAtop yAbottom yBtop yBbottom    A and B does not overlap if  C width  gt   A width   B width   OR  C height  gt   A height   B height     It takes care all possible cases

User · Answer

In the question  you link to the maths for when rectangles are at arbitrary angles of rotation   If I understand the bit about angles in the question however  I interpret that all rectangles are perpendicular to one another   A general knowing the area of overlap formula is   Using the example      1   2   3   4   5   6  1   --- ---                  2      A    --- ---               B       3               --- ---                           4   --- --- --- ---                               5                  C                              6               --- ---    1  collect all the x coordinates  both left and right  into a list  then sort it and remove duplicates  1 3 4 5 6  2  collect all the y coordinates  both top and bottom  into a list  then sort it and remove duplicates  1 2 3 4 6  3  create a 2D array by number of gaps between the unique x coordinates   number of gaps between the unique y coordinates   4   4  4  paint all the rectangles into this grid  incrementing the count of each cell it occurs over       1   3   4   5   6  1   ---       1   0   0   0 2   --- --- ---       1   1   1   0 3   --- --- --- ---       1   1   2   1   4   --- --- --- ---       0   0   1   1   6           --- ---    5  As you paint the rectangles  its easy to intercept the overlaps

User · Answer

I have implemented a C  version  it is easily converted to C     public bool Intersects   Rectangle rect       float ulx   Math Max   x  rect x      float uly   Math Max   y  rect y      float lrx   Math Min   x   width  rect x   rect width      float lry   Math Min   y   height  rect y   rect height       return ulx  lt   lrx  amp  amp  uly  lt   lry

User · Answer

bool Square  IsOverlappig Square  amp other        bool result1   other x  gt   x  amp  amp  other y  gt   y  amp  amp  other x  lt    x   width   amp  amp  other y  lt    y   height      other s top left falls within this area     bool result2   other x  gt   x  amp  amp  other y  lt   y  amp  amp  other x  lt    x   width   amp  amp   other y   other height   lt    y   height      other s bottom left falls within this area     bool result3   other x  lt   x  amp  amp  other y  gt   y  amp  amp   other x   other width   lt    x   width   amp  amp  other y  lt    y   height      other s top right falls within this area     bool result4   other x  lt   x  amp  amp  other y  lt   y  amp  amp   other x   other width   gt   x  amp  amp   other y   other height   gt   y     other s bottom right falls within this area     return result1   result2   result3   result4

User · Answer

struct Rect       Rect int x1  int x2  int y1  int y2        x1 x1   x2 x2   y1 y1   y2 y2                assert x1  lt  x2           assert y1  lt  y2              int x1  x2  y1  y2      bool overlap const Rect  amp r1  const Rect  amp r2           The rectangles don t overlap if        one rectangle s minimum in some dimension         is greater than the other s maximum in        that dimension       bool noOverlap   r1 x1  gt  r2 x2                         r2 x1  gt  r1 x2                         r1 y1  gt  r2 y2                         r2 y1  gt  r1 y2       return  noOverlap

User · Answer

Ask yourself the opposite question  How can I determine if two rectangles do not intersect at all   Obviously  a rectangle A completely to the left of rectangle B does not intersect   Also if A is completely to the right   And similarly if A is completely above B or completely below B   In any other case A and B intersect   What follows may have bugs  but I am pretty confident about the algorithm   struct Rectangle   int x  int y  int width  int height      bool is left of Rectangle const  amp  a  Rectangle const  amp  b       if  a x   a width  lt   b x  return true     return false    bool is right of Rectangle const  amp  a  Rectangle const  amp  b       return is left of b  a      bool not intersect  Rectangle const  amp  a  Rectangle const  amp  b       if  is left of a  b   return true     if  is right of a  b   return true        Do the same for top bottom        bool intersect Rectangle const  amp  a  Rectangle const  amp  b      return  not intersect a  b

User · Answer

Suppose that you have defined the positions and sizes of the rectangles like this     My C   implementation is like this   class Vector2D       public          Vector2D int x  int y    x x   y y              Vector2D             int x  y      bool DoRectanglesOverlap    const Vector2D  amp  Pos1                              const Vector2D  amp  Size1                              const Vector2D  amp  Pos2                              const Vector2D  amp  Size2        if   Pos1 x  lt  Pos2 x   Size2 x   amp  amp           Pos1 y  lt  Pos2 y   Size2 y   amp  amp           Pos2 x  lt  Pos1 x   Size1 x   amp  amp           Pos2 y  lt  Pos1 y   Size1 y                 return true            return false      An example function call according to the given figure above   DoRectanglesOverlap Vector2D 3  7                       Vector2D 8  5                       Vector2D 6  4                       Vector2D 9  4      The comparisons inside the if block will look like below   if   Pos1 x  lt  Pos2 x   Size2 x   amp  amp       Pos1 y  lt  Pos2 y   Size2 y   amp  amp       Pos2 x  lt  Pos1 x   Size1 x   amp  amp       Pos2 y  lt  Pos1 y   Size1 y                        if      3    lt     6       9       amp  amp          7    lt     4       4       amp  amp          6    lt     3       8       amp  amp          4    lt     7       5

User · Answer

struct Rect      Rect int x1  int x2  int y1  int y2       x1 x1   x2 x2   y1 y1   y2 y2              assert x1  lt  x2          assert y1  lt  y2            int x1  x2  y1  y2        some area of the r1 overlaps r2 bool overlap const Rect  amp r1  const Rect  amp r2        return r1 x1  lt  r2 x2  amp  amp  r2 x1  lt  r1 x2  amp  amp             r1 y1  lt  r2 y2  amp  amp  r2 x1  lt  r1 y2       either the rectangles overlap or the edges touch bool touch const Rect  amp r1  const Rect  amp r2        return r1 x1  lt   r2 x2  amp  amp  r2 x1  lt   r1 x2  amp  amp             r1 y1  lt   r2 y2  amp  amp  r2 x1  lt   r1 y2

User · Answer

struct Rect       Rect int x1  int x2  int y1  int y2        x1 x1   x2 x2   y1 y1   y2 y2                assert x1  lt  x2           assert y1  lt  y2              int x1  x2  y1  y2      bool overlap const Rect  amp r1  const Rect  amp r2           The rectangles don t overlap if        one rectangle s minimum in some dimension         is greater than the other s maximum in        that dimension       bool noOverlap   r1 x1  gt  r2 x2                         r2 x1  gt  r1 x2                         r1 y1  gt  r2 y2                         r2 y1  gt  r1 y2       return  noOverlap

User · Answer

struct rect       int x      int y      int width      int height      bool valueInRange int value  int min  int max    return  value  gt   min      value  lt   max      bool rectOverlap rect A  rect B        bool xOverlap   valueInRange A x  B x  B x   B width                         valueInRange B x  A x  A x   A width        bool yOverlap   valueInRange A y  B y  B y   B height                         valueInRange B y  A y  A y   A height        return xOverlap    yOverlap

User · Answer

Easiest way is         Check if two rectangles collide    x 1  y 1  width 1  and height 1 define the boundaries of the first rectangle    x 2  y 2  width 2  and height 2 define the boundaries of the second rectangle     boolean rectangle collision float x 1  float y 1  float width 1  float height 1  float x 2  float y 2  float width 2  float height 2      return   x 1  gt  x 2 width 2    x 1 width 1  lt  x 2    y 1  gt  y 2 height 2    y 1 height 1  lt  y 2       first of all put it in to your mind that in computers the coordinates system is upside down  x-axis is same as in mathematics but y-axis increases downwards and decrease on going upward   if rectangle are drawn from center  if x1 coordinates is greater than x2 plus its its half of widht   then it means going half they will touch each other  and in the same manner going downward   half of its height  it will collide

User · Answer

If the rectangles overlap then the overlap area will be greater than zero  Now let us find the overlap area   If they overlap then the left edge of overlap-rect will be the max r1 x1  r2 x1  and right edge will be min r1 x2  r2 x2   So the length of the overlap will be min r1 x2  r2 x2  - max r1 x1  r2 x1   So the area will be   area    max r1 x1  r2 x1  - min r1 x2  r2 x2      max r1 y1  r2 y1  - min r1 y2  r2 y2     If area   0 then they don t overlap   Simple isn t it

User · Answer

A and B be two rectangle  C be their covering rectangle    four points of A be  xAleft yAtop   xAleft yAbottom   xAright yAtop   xAright yAbottom  four points of A be  xBleft yBtop   xBleft yBbottom   xBright yBtop   xBright yBbottom   A width   abs xAleft-xAright   A height   abs yAleft-yAright   B width   abs xBleft-xBright   B height   abs yBleft-yBright    C width   max xAleft xAright xBleft xBright -min xAleft xAright xBleft xBright   C height   max yAtop yAbottom yBtop yBbottom -min yAtop yAbottom yBtop yBbottom    A and B does not overlap if  C width  gt   A width   B width   OR  C height  gt   A height   B height     It takes care all possible cases

User · Answer

I have a very easy solution  let x1 y1 x2 y2  l1 b1 l2 be cordinates and lengths and breadths of them respectively  consider the condition   x2  now the only way these rectangle will overlap is if the point diagonal to x1 y1 will lie inside the other rectangle or similarly the point diagonal to x2 y2 will lie inside the other rectangle  which is exactly the above condition implies

User · Answer

I have implemented a C  version  it is easily converted to C     public bool Intersects   Rectangle rect       float ulx   Math Max   x  rect x      float uly   Math Max   y  rect y      float lrx   Math Min   x   width  rect x   rect width      float lry   Math Min   y   height  rect y   rect height       return ulx  lt   lrx  amp  amp  uly  lt   lry

User · Answer

For those of you who are using center points and half sizes for their rectangle data  instead of the typical x y w h  or x0 y0 x1 x1  here s how you can do it    include  lt cmath gt     for fabsf float   struct Rectangle       float centerX  centerY  halfWidth  halfHeight      bool isRectangleOverlapping const Rectangle  amp a  const Rectangle  amp b        return  fabsf a centerX - b centerX   lt    a halfWidth   b halfWidth    amp  amp              fabsf a centerY - b centerY   lt    a halfHeight   b halfHeight

User · Answer

Java code to figure out if Rectangles are contacting or overlapping each other       for   int i   0  i  lt  n  i           for   int j   0  j  lt  n  j               if   i    j                 Rectangle rectangle1   rectangles get i               Rectangle rectangle2   rectangles get j                int l1   rectangle1 l    left             int r1   rectangle1 r    right             int b1   rectangle1 b    bottom             int t1   rectangle1 t    top              int l2   rectangle2 l              int r2   rectangle2 r              int b2   rectangle2 b              int t2   rectangle2 t               boolean topOnBottom   t2    b1              boolean bottomOnTop   b2    t1              boolean topOrBottomContact   topOnBottom    bottomOnTop               boolean rightOnLeft   r2    l1              boolean leftOnRight   l2    r1              boolean rightOrLeftContact   leftOnRight    rightOnLeft               boolean leftPoll   l2  lt   l1  amp  amp  r2  gt   l1              boolean rightPoll   l2  lt   r1  amp  amp  r2  gt   r1              boolean leftRightInside   l2  gt   l1  amp  amp  r2  lt   r1              boolean leftRightPossiblePlaces   leftPoll    rightPoll    leftRightInside               boolean bottomPoll   t2  gt   b1  amp  amp  b2  lt   b1              boolean topPoll   b2  lt   b1  amp  amp  t2  gt   b1              boolean topBottomInside   b2  gt   b1  amp  amp  t2  lt   t1              boolean topBottomPossiblePlaces   bottomPoll    topPoll    topBottomInside                boolean topInBetween   t2  gt  b1  amp  amp  t2  lt  t1              boolean bottomInBetween   b2  gt  b1  amp  amp  b2  lt  t1              boolean topBottomInBetween   topInBetween    bottomInBetween               boolean leftInBetween   l2  gt  l1  amp  amp  l2  lt  r1              boolean rightInBetween   r2  gt  l1  amp  amp  r2  lt  r1              boolean leftRightInBetween   leftInBetween    rightInBetween               if    topOrBottomContact  amp  amp  leftRightPossiblePlaces      rightOrLeftContact  amp  amp  topBottomPossiblePlaces                      path i  j    true

User · Answer

struct rect       int x      int y      int width      int height      bool valueInRange int value  int min  int max    return  value  gt   min      value  lt   max      bool rectOverlap rect A  rect B        bool xOverlap   valueInRange A x  B x  B x   B width                         valueInRange B x  A x  A x   A width        bool yOverlap   valueInRange A y  B y  B y   B height                         valueInRange B y  A y  A y   A height        return xOverlap    yOverlap

User · Answer

Don t think of coordinates as indicating where pixels are  Think of them as being between the pixels  That way  the area of a 2x2 rectangle should be 4  not 9   bool bOverlap      A Left  gt   B Right    B Left  gt   A Right                  amp  amp   A Bottom  gt   B Top    B Bottom  gt   A Top

User · Answer

I have implemented a C  version  it is easily converted to C     public bool Intersects   Rectangle rect       float ulx   Math Max   x  rect x      float uly   Math Max   y  rect y      float lrx   Math Min   x   width  rect x   rect width      float lry   Math Min   y   height  rect y   rect height       return ulx  lt   lrx  amp  amp  uly  lt   lry

User · Answer

This is from exercise 3 28 from the book Introduction to Java Programming- Comprehensive Edition  The code tests whether the two rectangles are indenticle  whether one is inside the other and whether one is outside the other  If none of these condition are met then the two overlap     3 28  Geometry  two rectangles  Write a program that prompts the user to enter the  center x-  y-coordinates  width  and height of two rectangles and determines  whether the second rectangle is inside the first or overlaps with the first  as shown  in Figure  3 9  Test your program to cover all cases  Here are the sample runs   Enter r1 s center x-  y-coordinates  width  and height  2 5 4 2 5 43 Enter r2 s center x-  y-coordinates  width  and height  1 5 5 0 5 3 r2 is inside r1   Enter r1 s center x-  y-coordinates  width  and height  1 2 3 5 5 Enter r2 s center x-  y-coordinates  width  and height  3 4 4 5 5 r2 overlaps r1  Enter r1 s center x-  y-coordinates  width  and height  1 2 3 3 Enter r2 s center x-  y-coordinates  width  and height  40 45 3 2 r2 does not overlap r1  import java util Scanner   public class ProgrammingEx3 28   public static void main String   args        Scanner input   new Scanner System in        System out              print  Enter r1 s center x-  y-coordinates  width  and height         double x1   input nextDouble        double y1   input nextDouble        double w1   input nextDouble        double h1   input nextDouble        w1   w1   2      h1   h1   2      System out              print  Enter r2 s center x-  y-coordinates  width  and height         double x2   input nextDouble        double y2   input nextDouble        double w2   input nextDouble        double h2   input nextDouble        w2   w2   2      h2   h2   2          Calculating range of r1 and r2     double x1max   x1   w1      double y1max   y1   h1      double x1min   x1 - w1      double y1min   y1 - h1      double x2max   x2   w2      double y2max   y2   h2      double x2min   x2 - w2      double y2min   y2 - h2       if  x1max    x2max  amp  amp  x1min    x2min  amp  amp  y1max    y2max              amp  amp  y1min    y2min               Check if the two are identicle         System out print  r1 and r2 are indentical           else if  x1max  lt   x2max  amp  amp  x1min  gt   x2min  amp  amp  y1max  lt   y2max              amp  amp  y1min  gt   y2min               Check if r1 is in r2         System out print  r1 is inside r2          else if  x2max  lt   x1max  amp  amp  x2min  gt   x1min  amp  amp  y2max  lt   y1max              amp  amp  y2min  gt   y1min               Check if r2 is in r1         System out print  r2 is inside r1          else if  x1max  lt  x2min    x1min  gt  x2max    y1max  lt  y2min                y2min  gt  y1max               Check if the two overlap         System out print  r2 does not overlaps r1          else           System out print  r2 overlaps r1

User · Answer

Here s how it s done in the Java API   public boolean intersects Rectangle r        int tw   this width      int th   this height      int rw   r width      int rh   r height      if  rw  lt   0    rh  lt   0    tw  lt   0    th  lt   0            return false            int tx   this x      int ty   this y      int rx   r x      int ry   r y      rw    rx      rh    ry      tw    tx      th    ty              overflow    intersect     return   rw  lt  rx    rw  gt  tx   amp  amp               rh  lt  ry    rh  gt  ty   amp  amp               tw  lt  tx    tw  gt  rx   amp  amp               th  lt  ty    th  gt  ry

User · Answer

It is easier to check if a rectangle is completly outside the other  so if it is either   on the left       r1 x   r1 width  lt  r2 x    or on the right       r1 x  gt  r2 x   r2 width    or on top       r1 y   r1 height  lt  r2 y    or on the bottom       r1 y  gt  r2 y   r2 height    of the second rectangle  it cannot possibly collide with it  So to have a function that returns a Boolean saying weather the rectangles collide  we simply combine the conditions by logical ORs and negate the result   function checkOverlap r1  r2    Boolean        return   r1 x   r1 width  lt  r2 x    r1 y   r1 height  lt  r2 y    r1 x  gt  r2 x   r2 width    r1 y  gt  r2 y   r2 height       To already receive a positive result when touching only  we can change the   lt   and     by   lt    and

User · Answer

struct Rect       Rect int x1  int x2  int y1  int y2        x1 x1   x2 x2   y1 y1   y2 y2                assert x1  lt  x2           assert y1  lt  y2              int x1  x2  y1  y2      bool overlap const Rect  amp r1  const Rect  amp r2           The rectangles don t overlap if        one rectangle s minimum in some dimension         is greater than the other s maximum in        that dimension       bool noOverlap   r1 x1  gt  r2 x2                         r2 x1  gt  r1 x2                         r1 y1  gt  r2 y2                         r2 y1  gt  r1 y2       return  noOverlap

User · Answer

Don t think of coordinates as indicating where pixels are  Think of them as being between the pixels  That way  the area of a 2x2 rectangle should be 4  not 9   bool bOverlap      A Left  gt   B Right    B Left  gt   A Right                  amp  amp   A Bottom  gt   B Top    B Bottom  gt   A Top

User · Answer

struct rect       int x      int y      int width      int height      bool valueInRange int value  int min  int max    return  value  gt   min      value  lt   max      bool rectOverlap rect A  rect B        bool xOverlap   valueInRange A x  B x  B x   B width                         valueInRange B x  A x  A x   A width        bool yOverlap   valueInRange A y  B y  B y   B height                         valueInRange B y  A y  A y   A height        return xOverlap    yOverlap

User · Answer

In the question  you link to the maths for when rectangles are at arbitrary angles of rotation   If I understand the bit about angles in the question however  I interpret that all rectangles are perpendicular to one another   A general knowing the area of overlap formula is   Using the example      1   2   3   4   5   6  1   --- ---                  2      A    --- ---               B       3               --- ---                           4   --- --- --- ---                               5                  C                              6               --- ---    1  collect all the x coordinates  both left and right  into a list  then sort it and remove duplicates  1 3 4 5 6  2  collect all the y coordinates  both top and bottom  into a list  then sort it and remove duplicates  1 2 3 4 6  3  create a 2D array by number of gaps between the unique x coordinates   number of gaps between the unique y coordinates   4   4  4  paint all the rectangles into this grid  incrementing the count of each cell it occurs over       1   3   4   5   6  1   ---       1   0   0   0 2   --- --- ---       1   1   1   0 3   --- --- --- ---       1   1   2   1   4   --- --- --- ---       0   0   1   1   6           --- ---    5  As you paint the rectangles  its easy to intercept the overlaps

User · Answer

Don t think of coordinates as indicating where pixels are  Think of them as being between the pixels  That way  the area of a 2x2 rectangle should be 4  not 9   bool bOverlap      A Left  gt   B Right    B Left  gt   A Right                  amp  amp   A Bottom  gt   B Top    B Bottom  gt   A Top

User · Answer

struct point   int x  y      struct rect   point tl  br        top left and bottom right points     return true if rectangles overlap bool overlap const rect  amp a  const rect  amp b        return a tl x  lt   b br x  amp  amp  a br x  gt   b tl x  amp  amp              a tl y  gt   b br y  amp  amp  a br y  lt   b tl y

User · Answer

Here s how it s done in the Java API   public boolean intersects Rectangle r        int tw   this width      int th   this height      int rw   r width      int rh   r height      if  rw  lt   0    rh  lt   0    tw  lt   0    th  lt   0            return false            int tx   this x      int ty   this y      int rx   r x      int ry   r y      rw    rx      rh    ry      tw    tx      th    ty              overflow    intersect     return   rw  lt  rx    rw  gt  tx   amp  amp               rh  lt  ry    rh  gt  ty   amp  amp               tw  lt  tx    tw  gt  rx   amp  amp               th  lt  ty    th  gt  ry

User · Answer

If you perform subtraction x or y coordinates corresponding to the vertices of the two facing each rectangle  if the results are the same sign  the two rectangle do not overlap axes that   i am sorry  i am not sure my translation is correct     Source  http   www ieev org 2009 05 kiem-tra-hai-hinh-chu-nhat-chong-nhau html

User · Answer

If the rectangles overlap then the overlap area will be greater than zero  Now let us find the overlap area   If they overlap then the left edge of overlap-rect will be the max r1 x1  r2 x1  and right edge will be min r1 x2  r2 x2   So the length of the overlap will be min r1 x2  r2 x2  - max r1 x1  r2 x1   So the area will be   area    max r1 x1  r2 x1  - min r1 x2  r2 x2      max r1 y1  r2 y1  - min r1 y2  r2 y2     If area   0 then they don t overlap   Simple isn t it

User · Answer

If you perform subtraction x or y coordinates corresponding to the vertices of the two facing each rectangle  if the results are the same sign  the two rectangle do not overlap axes that   i am sorry  i am not sure my translation is correct     Source  http   www ieev org 2009 05 kiem-tra-hai-hinh-chu-nhat-chong-nhau html

User · Answer

Ask yourself the opposite question  How can I determine if two rectangles do not intersect at all   Obviously  a rectangle A completely to the left of rectangle B does not intersect   Also if A is completely to the right   And similarly if A is completely above B or completely below B   In any other case A and B intersect   What follows may have bugs  but I am pretty confident about the algorithm   struct Rectangle   int x  int y  int width  int height      bool is left of Rectangle const  amp  a  Rectangle const  amp  b       if  a x   a width  lt   b x  return true     return false    bool is right of Rectangle const  amp  a  Rectangle const  amp  b       return is left of b  a      bool not intersect  Rectangle const  amp  a  Rectangle const  amp  b       if  is left of a  b   return true     if  is right of a  b   return true        Do the same for top bottom        bool intersect Rectangle const  amp  a  Rectangle const  amp  b      return  not intersect a  b

User · Answer

For those of you who are using center points and half sizes for their rectangle data  instead of the typical x y w h  or x0 y0 x1 x1  here s how you can do it    include  lt cmath gt     for fabsf float   struct Rectangle       float centerX  centerY  halfWidth  halfHeight      bool isRectangleOverlapping const Rectangle  amp a  const Rectangle  amp b        return  fabsf a centerX - b centerX   lt    a halfWidth   b halfWidth    amp  amp              fabsf a centerY - b centerY   lt    a halfHeight   b halfHeight

User · Answer

struct Rect       Rect int x1  int x2  int y1  int y2        x1 x1   x2 x2   y1 y1   y2 y2                assert x1  lt  x2           assert y1  lt  y2              int x1  x2  y1  y2      bool overlap const Rect  amp r1  const Rect  amp r2           The rectangles don t overlap if        one rectangle s minimum in some dimension         is greater than the other s maximum in        that dimension       bool noOverlap   r1 x1  gt  r2 x2                         r2 x1  gt  r1 x2                         r1 y1  gt  r2 y2                         r2 y1  gt  r1 y2       return  noOverlap

User · Answer

Ask yourself the opposite question  How can I determine if two rectangles do not intersect at all   Obviously  a rectangle A completely to the left of rectangle B does not intersect   Also if A is completely to the right   And similarly if A is completely above B or completely below B   In any other case A and B intersect   What follows may have bugs  but I am pretty confident about the algorithm   struct Rectangle   int x  int y  int width  int height      bool is left of Rectangle const  amp  a  Rectangle const  amp  b       if  a x   a width  lt   b x  return true     return false    bool is right of Rectangle const  amp  a  Rectangle const  amp  b       return is left of b  a      bool not intersect  Rectangle const  amp  a  Rectangle const  amp  b       if  is left of a  b   return true     if  is right of a  b   return true        Do the same for top bottom        bool intersect Rectangle const  amp  a  Rectangle const  amp  b      return  not intersect a  b

User · Answer

Easiest way is         Check if two rectangles collide    x 1  y 1  width 1  and height 1 define the boundaries of the first rectangle    x 2  y 2  width 2  and height 2 define the boundaries of the second rectangle     boolean rectangle collision float x 1  float y 1  float width 1  float height 1  float x 2  float y 2  float width 2  float height 2      return   x 1  gt  x 2 width 2    x 1 width 1  lt  x 2    y 1  gt  y 2 height 2    y 1 height 1  lt  y 2       first of all put it in to your mind that in computers the coordinates system is upside down  x-axis is same as in mathematics but y-axis increases downwards and decrease on going upward   if rectangle are drawn from center  if x1 coordinates is greater than x2 plus its its half of widht   then it means going half they will touch each other  and in the same manner going downward   half of its height  it will collide

User · Answer

Don t think of coordinates as indicating where pixels are  Think of them as being between the pixels  That way  the area of a 2x2 rectangle should be 4  not 9   bool bOverlap      A Left  gt   B Right    B Left  gt   A Right                  amp  amp   A Bottom  gt   B Top    B Bottom  gt   A Top

User · Answer

struct Rect      Rect int x1  int x2  int y1  int y2       x1 x1   x2 x2   y1 y1   y2 y2              assert x1  lt  x2          assert y1  lt  y2            int x1  x2  y1  y2        some area of the r1 overlaps r2 bool overlap const Rect  amp r1  const Rect  amp r2        return r1 x1  lt  r2 x2  amp  amp  r2 x1  lt  r1 x2  amp  amp             r1 y1  lt  r2 y2  amp  amp  r2 x1  lt  r1 y2       either the rectangles overlap or the edges touch bool touch const Rect  amp r1  const Rect  amp r2        return r1 x1  lt   r2 x2  amp  amp  r2 x1  lt   r1 x2  amp  amp             r1 y1  lt   r2 y2  amp  amp  r2 x1  lt   r1 y2

User · Answer

This is from exercise 3 28 from the book Introduction to Java Programming- Comprehensive Edition  The code tests whether the two rectangles are indenticle  whether one is inside the other and whether one is outside the other  If none of these condition are met then the two overlap     3 28  Geometry  two rectangles  Write a program that prompts the user to enter the  center x-  y-coordinates  width  and height of two rectangles and determines  whether the second rectangle is inside the first or overlaps with the first  as shown  in Figure  3 9  Test your program to cover all cases  Here are the sample runs   Enter r1 s center x-  y-coordinates  width  and height  2 5 4 2 5 43 Enter r2 s center x-  y-coordinates  width  and height  1 5 5 0 5 3 r2 is inside r1   Enter r1 s center x-  y-coordinates  width  and height  1 2 3 5 5 Enter r2 s center x-  y-coordinates  width  and height  3 4 4 5 5 r2 overlaps r1  Enter r1 s center x-  y-coordinates  width  and height  1 2 3 3 Enter r2 s center x-  y-coordinates  width  and height  40 45 3 2 r2 does not overlap r1  import java util Scanner   public class ProgrammingEx3 28   public static void main String   args        Scanner input   new Scanner System in        System out              print  Enter r1 s center x-  y-coordinates  width  and height         double x1   input nextDouble        double y1   input nextDouble        double w1   input nextDouble        double h1   input nextDouble        w1   w1   2      h1   h1   2      System out              print  Enter r2 s center x-  y-coordinates  width  and height         double x2   input nextDouble        double y2   input nextDouble        double w2   input nextDouble        double h2   input nextDouble        w2   w2   2      h2   h2   2          Calculating range of r1 and r2     double x1max   x1   w1      double y1max   y1   h1      double x1min   x1 - w1      double y1min   y1 - h1      double x2max   x2   w2      double y2max   y2   h2      double x2min   x2 - w2      double y2min   y2 - h2       if  x1max    x2max  amp  amp  x1min    x2min  amp  amp  y1max    y2max              amp  amp  y1min    y2min               Check if the two are identicle         System out print  r1 and r2 are indentical           else if  x1max  lt   x2max  amp  amp  x1min  gt   x2min  amp  amp  y1max  lt   y2max              amp  amp  y1min  gt   y2min               Check if r1 is in r2         System out print  r1 is inside r2          else if  x2max  lt   x1max  amp  amp  x2min  gt   x1min  amp  amp  y2max  lt   y1max              amp  amp  y2min  gt   y1min               Check if r2 is in r1         System out print  r2 is inside r1          else if  x1max  lt  x2min    x1min  gt  x2max    y1max  lt  y2min                y2min  gt  y1max               Check if the two overlap         System out print  r2 does not overlaps r1          else           System out print  r2 overlaps r1

User · Answer

struct Rect      Rect int x1  int x2  int y1  int y2       x1 x1   x2 x2   y1 y1   y2 y2              assert x1  lt  x2          assert y1  lt  y2            int x1  x2  y1  y2        some area of the r1 overlaps r2 bool overlap const Rect  amp r1  const Rect  amp r2        return r1 x1  lt  r2 x2  amp  amp  r2 x1  lt  r1 x2  amp  amp             r1 y1  lt  r2 y2  amp  amp  r2 x1  lt  r1 y2       either the rectangles overlap or the edges touch bool touch const Rect  amp r1  const Rect  amp r2        return r1 x1  lt   r2 x2  amp  amp  r2 x1  lt   r1 x2  amp  amp             r1 y1  lt   r2 y2  amp  amp  r2 x1  lt   r1 y2

User · Answer

Java code to figure out if Rectangles are contacting or overlapping each other       for   int i   0  i  lt  n  i           for   int j   0  j  lt  n  j               if   i    j                 Rectangle rectangle1   rectangles get i               Rectangle rectangle2   rectangles get j                int l1   rectangle1 l    left             int r1   rectangle1 r    right             int b1   rectangle1 b    bottom             int t1   rectangle1 t    top              int l2   rectangle2 l              int r2   rectangle2 r              int b2   rectangle2 b              int t2   rectangle2 t               boolean topOnBottom   t2    b1              boolean bottomOnTop   b2    t1              boolean topOrBottomContact   topOnBottom    bottomOnTop               boolean rightOnLeft   r2    l1              boolean leftOnRight   l2    r1              boolean rightOrLeftContact   leftOnRight    rightOnLeft               boolean leftPoll   l2  lt   l1  amp  amp  r2  gt   l1              boolean rightPoll   l2  lt   r1  amp  amp  r2  gt   r1              boolean leftRightInside   l2  gt   l1  amp  amp  r2  lt   r1              boolean leftRightPossiblePlaces   leftPoll    rightPoll    leftRightInside               boolean bottomPoll   t2  gt   b1  amp  amp  b2  lt   b1              boolean topPoll   b2  lt   b1  amp  amp  t2  gt   b1              boolean topBottomInside   b2  gt   b1  amp  amp  t2  lt   t1              boolean topBottomPossiblePlaces   bottomPoll    topPoll    topBottomInside                boolean topInBetween   t2  gt  b1  amp  amp  t2  lt  t1              boolean bottomInBetween   b2  gt  b1  amp  amp  b2  lt  t1              boolean topBottomInBetween   topInBetween    bottomInBetween               boolean leftInBetween   l2  gt  l1  amp  amp  l2  lt  r1              boolean rightInBetween   r2  gt  l1  amp  amp  r2  lt  r1              boolean leftRightInBetween   leftInBetween    rightInBetween               if    topOrBottomContact  amp  amp  leftRightPossiblePlaces      rightOrLeftContact  amp  amp  topBottomPossiblePlaces                      path i  j    true

User · Answer

struct Rect      Rect int x1  int x2  int y1  int y2       x1 x1   x2 x2   y1 y1   y2 y2              assert x1  lt  x2          assert y1  lt  y2            int x1  x2  y1  y2        some area of the r1 overlaps r2 bool overlap const Rect  amp r1  const Rect  amp r2        return r1 x1  lt  r2 x2  amp  amp  r2 x1  lt  r1 x2  amp  amp             r1 y1  lt  r2 y2  amp  amp  r2 x1  lt  r1 y2       either the rectangles overlap or the edges touch bool touch const Rect  amp r1  const Rect  amp r2        return r1 x1  lt   r2 x2  amp  amp  r2 x1  lt   r1 x2  amp  amp             r1 y1  lt   r2 y2  amp  amp  r2 x1  lt   r1 y2

User · Answer

bool Square  IsOverlappig Square  amp other        bool result1   other x  gt   x  amp  amp  other y  gt   y  amp  amp  other x  lt    x   width   amp  amp  other y  lt    y   height      other s top left falls within this area     bool result2   other x  gt   x  amp  amp  other y  lt   y  amp  amp  other x  lt    x   width   amp  amp   other y   other height   lt    y   height      other s bottom left falls within this area     bool result3   other x  lt   x  amp  amp  other y  gt   y  amp  amp   other x   other width   lt    x   width   amp  amp  other y  lt    y   height      other s top right falls within this area     bool result4   other x  lt   x  amp  amp  other y  lt   y  amp  amp   other x   other width   gt   x  amp  amp   other y   other height   gt   y     other s bottom right falls within this area     return result1   result2   result3   result4

User · Answer

struct rect       int x      int y      int width      int height      bool valueInRange int value  int min  int max    return  value  gt   min      value  lt   max      bool rectOverlap rect A  rect B        bool xOverlap   valueInRange A x  B x  B x   B width                         valueInRange B x  A x  A x   A width        bool yOverlap   valueInRange A y  B y  B y   B height                         valueInRange B y  A y  A y   A height        return xOverlap    yOverlap

User · Answer

Suppose that you have defined the positions and sizes of the rectangles like this     My C   implementation is like this   class Vector2D       public          Vector2D int x  int y    x x   y y              Vector2D             int x  y      bool DoRectanglesOverlap    const Vector2D  amp  Pos1                              const Vector2D  amp  Size1                              const Vector2D  amp  Pos2                              const Vector2D  amp  Size2        if   Pos1 x  lt  Pos2 x   Size2 x   amp  amp           Pos1 y  lt  Pos2 y   Size2 y   amp  amp           Pos2 x  lt  Pos1 x   Size1 x   amp  amp           Pos2 y  lt  Pos1 y   Size1 y                 return true            return false      An example function call according to the given figure above   DoRectanglesOverlap Vector2D 3  7                       Vector2D 8  5                       Vector2D 6  4                       Vector2D 9  4      The comparisons inside the if block will look like below   if   Pos1 x  lt  Pos2 x   Size2 x   amp  amp       Pos1 y  lt  Pos2 y   Size2 y   amp  amp       Pos2 x  lt  Pos1 x   Size1 x   amp  amp       Pos2 y  lt  Pos1 y   Size1 y                        if      3    lt     6       9       amp  amp          7    lt     4       4       amp  amp          6    lt     3       8       amp  amp          4    lt     7       5

User · Answer

It is easier to check if a rectangle is completly outside the other  so if it is either   on the left       r1 x   r1 width  lt  r2 x    or on the right       r1 x  gt  r2 x   r2 width    or on top       r1 y   r1 height  lt  r2 y    or on the bottom       r1 y  gt  r2 y   r2 height    of the second rectangle  it cannot possibly collide with it  So to have a function that returns a Boolean saying weather the rectangles collide  we simply combine the conditions by logical ORs and negate the result   function checkOverlap r1  r2    Boolean        return   r1 x   r1 width  lt  r2 x    r1 y   r1 height  lt  r2 y    r1 x  gt  r2 x   r2 width    r1 y  gt  r2 y   r2 height       To already receive a positive result when touching only  we can change the   lt   and     by   lt    and

[c++] Determine if two rectangles overlap each other?

Examples related to c++

Examples related to algorithm

Examples related to geometry

Examples related to overlap

Examples related to rectangles