Circle-Rectangle collision detection intersection

Question

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space   i e  classic 2D geometry

User · Answer

This is the fastest solution   public static boolean intersect Rectangle r  Circle c        float cx   Math abs c x - r x - r halfWidth       float xDist   r halfWidth   c radius      if  cx  gt  xDist          return false      float cy   Math abs c y - r y - r halfHeight       float yDist   r halfHeight   c radius      if  cy  gt  yDist          return false      if  cx  lt   r halfWidth    cy  lt   r halfHeight          return true      float xCornerDist   cx - r halfWidth      float yCornerDist   cy - r halfHeight      float xCornerDistSq   xCornerDist   xCornerDist      float yCornerDistSq   yCornerDist   yCornerDist      float maxCornerDistSq   c radius   c radius      return xCornerDistSq   yCornerDistSq  lt   maxCornerDistSq      Note the order of execution  and half the width height is pre-computed  Also the squaring is done  manually  to save some clock cycles

User · Answer

your sphere and rect intersect IIF  the distance between the circle-center and one vertex of your rect is smaller than the radius of your sphere  OR  the distance between the circle-center and one edge of your rect is smaller than the radius of your sphere   point-line distance     OR  the circle center is inside the rect  point-point distance     P1    x1 y1  P2    x2 y2  Distance   sqrt abs x1 - x2  abs y1-y2     point-line distance    L1    x1 y1  L2    x2 y2   two points of your line  ie the vertex points  P1    px py  some point  Distance d    abs   x2-x1  y1-py - x1-px  y2-y1      Distance L1 L2     circle center inside rect   take an seperating axis aproach  if there exists a projection onto a line that seperates the rectangle from the point  they do not intersect  you project the point on lines parallel to the sides of your rect and can then easily determine if they intersect  if they intersect not on all 4 projections  they  the point and the rectangle  can not intersect   you just need the inner-product   x   x1 x2    y    y1 y2    x y   x1 y1   x2 y2    your test would look like that       rectangle edges  TL  top left   TR  top right   BL  bottom left   BR  bottom right    point to test  POI  seperated   false for egde in    TL TR    BL BR    TL BL   TR-BR         the edges     D   edge 0  - edge 1      innerProd    D   POI     Interval min   min D edge 0  D edge 1       Interval max   max D edge 0  D edge 1       if not    Interval min  le  innerProd  le   Interval max               seperated   true            break     end for loop      end if end for if  seperated is true            return  no intersection  else        return  intersection  end if   this does not assume an axis-aligned rectangle and is easily extendable for testing intersections between convex sets

User · Answer

worked for me  only work when angle of rectangle is 180   function intersects circle  rect      let left   rect x   rect width  gt  circle x - circle radius    let right   rect x  lt  circle x   circle radius    let top   rect y  lt  circle y   circle radius    let bottom   rect y   rect height  gt  circle y - circle radius    return left  amp  amp  right  amp  amp  bottom  amp  amp  top

User · Answer

I created class for work with shapes hope you enjoy  public class Geomethry     public static boolean intersectionCircleAndRectangle int circleX  int circleY  int circleR  int rectangleX  int rectangleY  int rectangleWidth  int rectangleHeight       boolean result   false       float rectHalfWidth   rectangleWidth 2 0f      float rectHalfHeight   rectangleHeight 2 0f       float rectCenterX   rectangleX   rectHalfWidth      float rectCenterY   rectangleY   rectHalfHeight       float deltax   Math abs rectCenterX - circleX       float deltay   Math abs rectCenterY - circleY        float lengthHypotenuseSqure   deltax deltax   deltay deltay       do             check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle         if lengthHypotenuseSqure  gt    rectHalfWidth circleR   rectHalfWidth circleR     rectHalfHeight circleR   rectHalfHeight circleR                   System out println  distance between the centerse is more than the distance between the circumcircle of rectangle and circle                break                        check that distance between the centerse is less than the distance between the inscribed circle         float rectMinHalfSide   Math min rectHalfWidth  rectHalfHeight           if lengthHypotenuseSqure  lt    rectMinHalfSide circleR   rectMinHalfSide circleR                   System out println  distance between the centerse is less than the distance between the inscribed circle                result true              break                        check that the squares relate to angles         if  deltax  gt   rectHalfWidth circleR  0 9   amp  amp   deltay  gt   rectHalfHeight circleR  0 9                  System out println  squares relate to angles                result true                 while false        return result     public static boolean intersectionRectangleAndRectangle int rectangleX  int rectangleY  int rectangleWidth  int rectangleHeight  int rectangleX2  int rectangleY2  int rectangleWidth2  int rectangleHeight2       boolean result   false       float rectHalfWidth   rectangleWidth 2 0f      float rectHalfHeight   rectangleHeight 2 0f      float rectHalfWidth2   rectangleWidth2 2 0f      float rectHalfHeight2   rectangleHeight2 2 0f       float deltax   Math abs  rectangleX   rectHalfWidth  -  rectangleX2   rectHalfWidth2        float deltay   Math abs  rectangleY   rectHalfHeight  -  rectangleY2   rectHalfHeight2         float lengthHypotenuseSqure   deltax deltax   deltay deltay       do             check that distance between the centerse is more than the distance between the circumcircle         if lengthHypotenuseSqure  gt    rectHalfWidth rectHalfWidth2   rectHalfWidth rectHalfWidth2     rectHalfHeight rectHalfHeight2   rectHalfHeight rectHalfHeight2                   System out println  distance between the centerse is more than the distance between the circumcircle                break                        check that distance between the centerse is less than the distance between the inscribed circle         float rectMinHalfSide   Math min rectHalfWidth  rectHalfHeight           float rectMinHalfSide2   Math min rectHalfWidth2  rectHalfHeight2           if lengthHypotenuseSqure  lt    rectMinHalfSide rectMinHalfSide2   rectMinHalfSide rectMinHalfSide2                   System out println  distance between the centerse is less than the distance between the inscribed circle                result true              break                        check that the squares relate to angles         if  deltax  gt   rectHalfWidth rectHalfWidth2  0 9   amp  amp   deltay  gt   rectHalfHeight rectHalfHeight2  0 9                  System out println  squares relate to angles                result true                 while false        return result

User · Answer

Here is the modfied code 100  working   public static bool IsIntersected PointF circle  float radius  RectangleF rectangle        var rectangleCenter   new PointF  rectangle X    rectangle Width   2                                         rectangle Y   rectangle Height   2         var w   rectangle Width    2      var h   rectangle Height   2       var dx   Math Abs circle X - rectangleCenter X       var dy   Math Abs circle Y - rectangleCenter Y        if  dx  gt   radius   w     dy  gt   radius   h   return false       var circleDistance   new PointF                                                                 X   Math Abs circle X - rectangle X - w                                    Y   Math Abs circle Y - rectangle Y - h                                       if  circleDistance X  lt    w                 return true             if  circleDistance Y  lt    h                 return true             var cornerDistanceSq   Math Pow circleDistance X - w  2                                         Math Pow circleDistance Y - h  2        return  cornerDistanceSq  lt    Math Pow radius  2         Bassam Alugili

User · Answer

Here s my C code for resolving a collision between a sphere and a non-axis aligned box  It relies on a couple of my own library routines  but it may prove useful to some  I m using it in a game and it works perfectly   float physicsProcessCollisionBetweenSelfAndActorRect SPhysics  self  SPhysics  actor        float diff   99999       SVector relative position of circle   getDifference2DBetweenVectors  amp self- gt worldPosition   amp actor- gt worldPosition       rotateVector2DBy  amp relative position of circle  -actor- gt axis angleZ      This aligns the coord system so the rect becomes an AABB      float x clamped within rectangle   relative position of circle x      float y clamped within rectangle   relative position of circle y      LIMIT x clamped within rectangle  actor- gt physicsRect l  actor- gt physicsRect r       LIMIT y clamped within rectangle  actor- gt physicsRect b  actor- gt physicsRect t           Calculate the distance between the circle s center and this closest point     float distance to nearest edge x   relative position of circle x - x clamped within rectangle      float distance to nearest edge y   relative position of circle y - y clamped within rectangle          If the distance is less than the circle s radius  an intersection occurs     float distance sq x   SQUARE distance to nearest edge x       float distance sq y   SQUARE distance to nearest edge y       float radius sq   SQUARE self- gt physicsRadius       if distance sq x   distance sq y  lt  radius sq                   float half rect w    actor- gt physicsRect r - actor- gt physicsRect l    0 5f          float half rect h    actor- gt physicsRect t - actor- gt physicsRect b    0 5f           CREATE VECTOR push vector                        If we re at one of the corners of this object  treat this as a circular circular collision         if fabs relative position of circle x   gt  half rect w  amp  amp  fabs relative position of circle y   gt  half rect h                        SVector edges              if relative position of circle x  gt  0  edges x   half rect w  else edges x   -half rect w              if relative position of circle y  gt  0  edges y   half rect h  else edges y   -half rect h                  push vector   relative position of circle              moveVectorByInverseVector2D  amp push vector   amp edges                   We now have the vector from the corner of the rect to the point              float delta length   getVector2DMagnitude  amp push vector               float diff   self- gt physicsRadius - delta length     Find out how far away we are from our ideal distance                 Normalise the vector             push vector x    delta length              push vector y    delta length              scaleVector2DBy  amp push vector  diff      Now multiply it by the difference             push vector z   0                    else    Nope - just bouncing against one of the edges                       if relative position of circle x  gt  0     Ball is to the right                 push vector x    half rect w   self- gt physicsRadius  - relative position of circle x              else                 push vector x   -  half rect w   self- gt physicsRadius    relative position of circle x                if relative position of circle y  gt  0     Ball is above                 push vector y    half rect h   self- gt physicsRadius  - relative position of circle y              else                 push vector y   -  half rect h   self- gt physicsRadius    relative position of circle y                if fabs push vector x   lt  fabs push vector y                   push vector y   0              else                 push vector x   0                     diff   0     Cheat  since we don t do anything with the value anyway         rotateVector2DBy  amp push vector  actor- gt axis angleZ           SVector  from    amp self- gt worldPosition                 moveVectorBy2D from  push vector x  push vector y                return diff

User · Answer

Here is another solution that s pretty simple to implement  and pretty fast  too   It will catch all intersections  including when the sphere has fully entered the rectangle      clamp value  min  max  - limits value to the range min  max     Find the closest point to the circle within the rectangle float closestX   clamp circle X  rectangle Left  rectangle Right   float closestY   clamp circle Y  rectangle Top  rectangle Bottom       Calculate the distance between the circle s center and this closest point float distanceX   circle X - closestX  float distanceY   circle Y - closestY      If the distance is less than the circle s radius  an intersection occurs float distanceSquared    distanceX   distanceX     distanceY   distanceY   return distanceSquared  lt   circle Radius   circle Radius     With any decent math library  that can be shortened to 3 or 4 lines

User · Answer

This function detect collisions  intersections  between Circle and Rectangle  He works like e James method in his answer  but this one detect collisions for all angles of rectangle  not only right up corner    NOTE    aRect origin x and aRect origin y are coordinates of bottom left angle of rectangle   aCircle x and aCircle y are coordinates of Circle Center   static inline BOOL RectIntersectsCircle CGRect aRect  Circle aCircle         float testX   aCircle x      float testY   aCircle y       if  testX  lt  aRect origin x          testX   aRect origin x      if  testX  gt   aRect origin x   aRect size width           testX    aRect origin x   aRect size width       if  testY  lt  aRect origin y          testY   aRect origin y      if  testY  gt   aRect origin y   aRect size height           testY    aRect origin y   aRect size height        return   aCircle x - testX     aCircle x - testX     aCircle y - testY     aCircle y - testY    lt  aCircle radius   aCircle radius

User · Answer

def colision rect  circle   dx   rect x - circle x dy   rect y - circle y distance    dy  2   dx  2   0 5 angle to    rect angle   math atan2 dx  dy  3 1415 180 0    360 if  angle to gt 135 and angle to lt 225  or  angle to gt 0 and angle to lt 45  or  angle to gt 315 and angle to lt 360        if distance  lt   circle rad 2    rect height 2 0   1  0 5 abs math sin angle to math pi 180               return True else      if distance  lt   circle rad 2    rect width 2 0   1  0 5 abs math cos angle to math pi 180               return True return False

User · Answer

Here is another solution that s pretty simple to implement  and pretty fast  too   It will catch all intersections  including when the sphere has fully entered the rectangle      clamp value  min  max  - limits value to the range min  max     Find the closest point to the circle within the rectangle float closestX   clamp circle X  rectangle Left  rectangle Right   float closestY   clamp circle Y  rectangle Top  rectangle Bottom       Calculate the distance between the circle s center and this closest point float distanceX   circle X - closestX  float distanceY   circle Y - closestY      If the distance is less than the circle s radius  an intersection occurs float distanceSquared    distanceX   distanceX     distanceY   distanceY   return distanceSquared  lt   circle Radius   circle Radius     With any decent math library  that can be shortened to 3 or 4 lines

User · Answer

Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle  if its less then the radius  then the shapes are intersecting   if sqrt  rectangleRight x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleRight x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect

User · Answer

Here is how I would do it   bool intersects CircleType circle  RectType rect        circleDistance x   abs circle x - rect x       circleDistance y   abs circle y - rect y        if  circleDistance x  gt   rect width 2   circle r     return false        if  circleDistance y  gt   rect height 2   circle r     return false         if  circleDistance x  lt    rect width 2     return true         if  circleDistance y  lt    rect height 2     return true         cornerDistance sq    circleDistance x - rect width 2  2                             circleDistance y - rect height 2  2       return  cornerDistance sq  lt    circle r 2        Here s how it works        The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle  This collapses the four quadrants down into one  so that the calculations do not have to be done four times  The image shows the area in which the center of the circle must now lie  Note that only the single quadrant is shown  The rectangle is the grey area  and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle  The center of the circle has to be within this red border for the intersection to occur  The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle  in either direction  that no intersection is possible  This corresponds to the green area in the image  The third pair of lines handle the easy cases where the circle is close enough to the rectangle  in either direction  that an intersection is guaranteed  This corresponds to the orange and grey sections in the image  Note that this step must be done after step 2 for the logic to make sense  The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle  To solve  compute the distance from the center of the circle and the corner  and then verify that the distance is not more than the radius of the circle  This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area

User · Answer

Here is how I would do it   bool intersects CircleType circle  RectType rect        circleDistance x   abs circle x - rect x       circleDistance y   abs circle y - rect y        if  circleDistance x  gt   rect width 2   circle r     return false        if  circleDistance y  gt   rect height 2   circle r     return false         if  circleDistance x  lt    rect width 2     return true         if  circleDistance y  lt    rect height 2     return true         cornerDistance sq    circleDistance x - rect width 2  2                             circleDistance y - rect height 2  2       return  cornerDistance sq  lt    circle r 2        Here s how it works        The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle  This collapses the four quadrants down into one  so that the calculations do not have to be done four times  The image shows the area in which the center of the circle must now lie  Note that only the single quadrant is shown  The rectangle is the grey area  and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle  The center of the circle has to be within this red border for the intersection to occur  The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle  in either direction  that no intersection is possible  This corresponds to the green area in the image  The third pair of lines handle the easy cases where the circle is close enough to the rectangle  in either direction  that an intersection is guaranteed  This corresponds to the orange and grey sections in the image  Note that this step must be done after step 2 for the logic to make sense  The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle  To solve  compute the distance from the center of the circle and the corner  and then verify that the distance is not more than the radius of the circle  This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area

User · Answer

Actually  this is much more simple  You need only two things   First  you need to find four orthogonal distances from the circle centre to each line of the rectangle  Then your circle will not intersect the rectangle if any three of them are larger than the circle radius   Second  you need to find the distance between the circle centre and the rectangle centre  then you circle will not be inside of the rectangle if the distance is larger than a half of the rectangle diagonal length   Good luck

User · Answer

your sphere and rect intersect IIF  the distance between the circle-center and one vertex of your rect is smaller than the radius of your sphere  OR  the distance between the circle-center and one edge of your rect is smaller than the radius of your sphere   point-line distance     OR  the circle center is inside the rect  point-point distance     P1    x1 y1  P2    x2 y2  Distance   sqrt abs x1 - x2  abs y1-y2     point-line distance    L1    x1 y1  L2    x2 y2   two points of your line  ie the vertex points  P1    px py  some point  Distance d    abs   x2-x1  y1-py - x1-px  y2-y1      Distance L1 L2     circle center inside rect   take an seperating axis aproach  if there exists a projection onto a line that seperates the rectangle from the point  they do not intersect  you project the point on lines parallel to the sides of your rect and can then easily determine if they intersect  if they intersect not on all 4 projections  they  the point and the rectangle  can not intersect   you just need the inner-product   x   x1 x2    y    y1 y2    x y   x1 y1   x2 y2    your test would look like that       rectangle edges  TL  top left   TR  top right   BL  bottom left   BR  bottom right    point to test  POI  seperated   false for egde in    TL TR    BL BR    TL BL   TR-BR         the edges     D   edge 0  - edge 1      innerProd    D   POI     Interval min   min D edge 0  D edge 1       Interval max   max D edge 0  D edge 1       if not    Interval min  le  innerProd  le   Interval max               seperated   true            break     end for loop      end if end for if  seperated is true            return  no intersection  else        return  intersection  end if   this does not assume an axis-aligned rectangle and is easily extendable for testing intersections between convex sets

User · Answer

do a pre-check whether a circle fully encapsulating the rectangle collides with the circle  check for rectangle corners within the circle  For each edge  see if there is a line intersection with the circle  Project the center point C onto the line AB to get a point D   If the length of CD is less than radius  there was a collision       projectionScalar dot AC AB   mag AC  mag AB        if projectionScalar gt  0  amp  amp  projectionScalar lt  1            D A AB projectionScalar          CD D-C          if mag CD  lt circle radius                  there was a collision

User · Answer

To visualise  take your keyboard s numpad  If the key  5  represents your rectangle  then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle  with 5 being the inside    1  If the circle s center is in quadrant 5  i e  inside the rectangle  then the two shapes intersect   With that out of the way  there are two possible cases  a  The circle intersects with two or more neighboring edges of the rectangle  b  The circle intersects with one edge of the rectangle   The first case is simple  If the circle intersects with two neighboring edges of the rectangle  it must contain the corner connecting those two edges   That  or its center lies in quadrant 5  which we have already covered  Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well    2  If any of the corners A  B  C  D of the rectangle lie inside the circle  then the two shapes intersect   The second case is trickier  We should make note of that it may only happen when the circle s center lies in one of the quadrants 2  4  6 or 8   In fact  if the center is on any of the quadrants 1  3  7  8  the corresponding corner will be the closest point to it    Now we have the case that the circle s center is in one of the  edge  quadrants  and it only intersects with the corresponding edge  Then  the point on the edge that is closest to the circle s center  must lie inside the circle   3  For each line AB  BC  CD  DA  construct perpendicular lines p AB P   p BC P   p CD P   p DA P  through the circle s center P  For each perpendicular line  if the intersection with the original edge lies inside the circle  then the two shapes intersect   There is a shortcut for this last step  If the circle s center is in quadrant 8 and the edge AB is the top edge  the point of intersection will have the y-coordinate of A and B  and the x-coordinate of center P   You can construct the four line intersections and check if they lie on their corresponding edges  or find out which quadrant P is in and check the corresponding intersection  Both should simplify to the same boolean equation  Be wary of that the step 2 above did not rule out P being in one of the  corner  quadrants  it just looked for an intersection   Edit  As it turns out  I have overlooked the simple fact that  2 is a subcase of  3 above  After all  corners too are points on the edges  See  ShreevatsaR s answer below for a great explanation  And in the meanwhile  forget  2 above unless you want a quick but redundant check

User · Answer

There is an incredibly simple way to do this  you have to clamp a point in x and y  but inside the square  while the center of the circle is between the two square border points in one of the perpendicular axis you need to clamp those coordinates to the parallel axis  just make sure the clamped coordinates do not exeed the limits of the square  Then just get the distance between the center of the circle and the clamped coordinates and check if the distance is less than the radius of the circle  Here is how I did it  First 4 points are the square coordinates  the rest are circle points   bool DoesCircleImpactBox float x  float y  float x1  float y1  float xc  float yc  float radius       float ClampedX 0      float ClampedY 0           if xc gt  x and xc lt  x1       ClampedX xc                 if yc gt  y and yc lt  y1       ClampedY yc                 radius   radius 1           if xc lt x  ClampedX x      if xc gt x1  ClampedX x1-1      if yc lt y  ClampedY y      if yc gt y1  ClampedY y1-1           float XDif ClampedX-xc      XDif XDif XDif      float YDif ClampedY-yc      YDif YDif YDif           if XDif YDif lt  radius radius  return true           return false

User · Answer

First check if the rectangle and the square tangent to the circle overlaps  easy   If they do not overlaps  they do not collide  Check if the circle s center is inside the rectangle  easy   If it s inside  they collide  Calculate the minimum squared distance from the rectangle sides to the circle s center  little hard   If it s lower that the squared radius  then they collide  else they don t    It s efficient  because    First it checks the most common scenario with a cheap algorithm and when it s sure they do not collide  it ends  Then it checks the next most common scenario with a cheap algorithm  do not calculate square root  use the squared values  and when it s sure they collide it ends  Then it executes the more expensive algorithm to check collision with the rectangle borders

User · Answer

First check if the rectangle and the square tangent to the circle overlaps  easy   If they do not overlaps  they do not collide  Check if the circle s center is inside the rectangle  easy   If it s inside  they collide  Calculate the minimum squared distance from the rectangle sides to the circle s center  little hard   If it s lower that the squared radius  then they collide  else they don t    It s efficient  because    First it checks the most common scenario with a cheap algorithm and when it s sure they do not collide  it ends  Then it checks the next most common scenario with a cheap algorithm  do not calculate square root  use the squared values  and when it s sure they collide it ends  Then it executes the more expensive algorithm to check collision with the rectangle borders

User · Answer

I developed this algorithm while making this game  https   mshwf github io mates   If the circle touches the square  then the distance between the centerline of the circle and the centerline of the square should equal  diameter side  2  So  let s have a variable named touching that holds that distance  The problem was  which centerline should I consider  the horizontal or the vertical  Consider this frame   Each centerline gives different distances  and only one is a correct indication to a no-collision  but using our human intuition is a start to understand how the natural algorithm works  They are not touching  which means that the distance between the two centerlines should be greater than touching  which means that the natural algorithm picks the horizontal centerlines  the vertical centerlines says there s a collision    By noticing multiple circles  you can tell  if the circle intersects with the vertical extension of the square  then we pick the vertical distance  between the horizontal centerlines   and if the circle intersects with the horizontal extension  we pick the horizontal distance   Another example  circle number 4  it intersects with the horizontal extension of the square  then we consider the horizontal distance which is equal to touching  Ok  the tough part is demystified  now we know how the algorithm will work  but how we know with which extension the circle intersects  It s easy actually  we calculate the distance between the most right x and the most left x  of both the circle and the square   and the same for the y-axis  the one with greater value is the axis with the extension that intersects with the circle  if it s greater than diameter side then the circle is outside the two square extensions  like circle  7   The code looks like  right   Math max square x square side  circle x circle rad   left   Math min square x  circle x-circle rad    bottom   Math max square y square side  circle y circle rad   top   Math min square y  circle y-circle rad    if  right - left  gt  down - top       compare with horizontal distance   else      compare with vertical distance      These equations assume that the reference point of the square is at its top left corner  and the reference point of the circle is at its center

User · Answer

There are only two cases when the circle intersects with the rectangle    Either the circle s centre lies inside the rectangle  or One of the edges of the rectangle has a point in the circle    Note that this does not require the rectangle to be axis-parallel       One way to see this  if none of the edges has a point in the circle  if all the edges are completely  outside  the circle   then the only way the circle can still intersect the polygon is if it lies completely inside the polygon    With that insight  something like the following will work  where the circle has centre P and radius R  and the rectangle has vertices A  B  C  D in that order  not complete code    def intersect Circle P  R   Rectangle A  B  C  D        S   Circle P  R      return  pointInRectangle P  Rectangle A  B  C  D   or             intersectCircle S   A  B   or             intersectCircle S   B  C   or             intersectCircle S   C  D   or             intersectCircle S   D  A      If you re writing any geometry you probably have the above functions in your library already  Otherwise  pointInRectangle   can be implemented in several ways  any of the general point in polygon methods will work  but for a rectangle you can just check whether this works   0   AP  AB   AB  AB and 0   AP  AD   AD  AD   And intersectCircle   is easy to implement too  one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints  and check the endpoints otherwise   The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon     doesn t even have to be convex

User · Answer

To visualise  take your keyboard s numpad  If the key  5  represents your rectangle  then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle  with 5 being the inside    1  If the circle s center is in quadrant 5  i e  inside the rectangle  then the two shapes intersect   With that out of the way  there are two possible cases  a  The circle intersects with two or more neighboring edges of the rectangle  b  The circle intersects with one edge of the rectangle   The first case is simple  If the circle intersects with two neighboring edges of the rectangle  it must contain the corner connecting those two edges   That  or its center lies in quadrant 5  which we have already covered  Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well    2  If any of the corners A  B  C  D of the rectangle lie inside the circle  then the two shapes intersect   The second case is trickier  We should make note of that it may only happen when the circle s center lies in one of the quadrants 2  4  6 or 8   In fact  if the center is on any of the quadrants 1  3  7  8  the corresponding corner will be the closest point to it    Now we have the case that the circle s center is in one of the  edge  quadrants  and it only intersects with the corresponding edge  Then  the point on the edge that is closest to the circle s center  must lie inside the circle   3  For each line AB  BC  CD  DA  construct perpendicular lines p AB P   p BC P   p CD P   p DA P  through the circle s center P  For each perpendicular line  if the intersection with the original edge lies inside the circle  then the two shapes intersect   There is a shortcut for this last step  If the circle s center is in quadrant 8 and the edge AB is the top edge  the point of intersection will have the y-coordinate of A and B  and the x-coordinate of center P   You can construct the four line intersections and check if they lie on their corresponding edges  or find out which quadrant P is in and check the corresponding intersection  Both should simplify to the same boolean equation  Be wary of that the step 2 above did not rule out P being in one of the  corner  quadrants  it just looked for an intersection   Edit  As it turns out  I have overlooked the simple fact that  2 is a subcase of  3 above  After all  corners too are points on the edges  See  ShreevatsaR s answer below for a great explanation  And in the meanwhile  forget  2 above unless you want a quick but redundant check

User · Answer

Here is the modfied code 100  working   public static bool IsIntersected PointF circle  float radius  RectangleF rectangle        var rectangleCenter   new PointF  rectangle X    rectangle Width   2                                         rectangle Y   rectangle Height   2         var w   rectangle Width    2      var h   rectangle Height   2       var dx   Math Abs circle X - rectangleCenter X       var dy   Math Abs circle Y - rectangleCenter Y        if  dx  gt   radius   w     dy  gt   radius   h   return false       var circleDistance   new PointF                                                                 X   Math Abs circle X - rectangle X - w                                    Y   Math Abs circle Y - rectangle Y - h                                       if  circleDistance X  lt    w                 return true             if  circleDistance Y  lt    h                 return true             var cornerDistanceSq   Math Pow circleDistance X - w  2                                         Math Pow circleDistance Y - h  2        return  cornerDistanceSq  lt    Math Pow radius  2         Bassam Alugili

User · Answer

Improving a little bit the answer of e James  double dx   abs circle x - rect x  - rect w   2         dy   abs circle y - rect y  - rect h   2   if  dx  gt  circle r    dy  gt  circle r    return false    if  dx  lt   0    dy  lt   0    return true     return  dx   dx   dy   dy  lt   circle r   circle r    This subtracts rect w   2 and rect h   2 once instead of up to three times

User · Answer

There is an incredibly simple way to do this  you have to clamp a point in x and y  but inside the square  while the center of the circle is between the two square border points in one of the perpendicular axis you need to clamp those coordinates to the parallel axis  just make sure the clamped coordinates do not exeed the limits of the square  Then just get the distance between the center of the circle and the clamped coordinates and check if the distance is less than the radius of the circle  Here is how I did it  First 4 points are the square coordinates  the rest are circle points   bool DoesCircleImpactBox float x  float y  float x1  float y1  float xc  float yc  float radius       float ClampedX 0      float ClampedY 0           if xc gt  x and xc lt  x1       ClampedX xc                 if yc gt  y and yc lt  y1       ClampedY yc                 radius   radius 1           if xc lt x  ClampedX x      if xc gt x1  ClampedX x1-1      if yc lt y  ClampedY y      if yc gt y1  ClampedY y1-1           float XDif ClampedX-xc      XDif XDif XDif      float YDif ClampedY-yc      YDif YDif YDif           if XDif YDif lt  radius radius  return true           return false

User · Answer

do a pre-check whether a circle fully encapsulating the rectangle collides with the circle  check for rectangle corners within the circle  For each edge  see if there is a line intersection with the circle  Project the center point C onto the line AB to get a point D   If the length of CD is less than radius  there was a collision       projectionScalar dot AC AB   mag AC  mag AB        if projectionScalar gt  0  amp  amp  projectionScalar lt  1            D A AB projectionScalar          CD D-C          if mag CD  lt circle radius                  there was a collision

User · Answer

This is the fastest solution   public static boolean intersect Rectangle r  Circle c        float cx   Math abs c x - r x - r halfWidth       float xDist   r halfWidth   c radius      if  cx  gt  xDist          return false      float cy   Math abs c y - r y - r halfHeight       float yDist   r halfHeight   c radius      if  cy  gt  yDist          return false      if  cx  lt   r halfWidth    cy  lt   r halfHeight          return true      float xCornerDist   cx - r halfWidth      float yCornerDist   cy - r halfHeight      float xCornerDistSq   xCornerDist   xCornerDist      float yCornerDistSq   yCornerDist   yCornerDist      float maxCornerDistSq   c radius   c radius      return xCornerDistSq   yCornerDistSq  lt   maxCornerDistSq      Note the order of execution  and half the width height is pre-computed  Also the squaring is done  manually  to save some clock cycles

User · Answer

There are only two cases when the circle intersects with the rectangle    Either the circle s centre lies inside the rectangle  or One of the edges of the rectangle has a point in the circle    Note that this does not require the rectangle to be axis-parallel       One way to see this  if none of the edges has a point in the circle  if all the edges are completely  outside  the circle   then the only way the circle can still intersect the polygon is if it lies completely inside the polygon    With that insight  something like the following will work  where the circle has centre P and radius R  and the rectangle has vertices A  B  C  D in that order  not complete code    def intersect Circle P  R   Rectangle A  B  C  D        S   Circle P  R      return  pointInRectangle P  Rectangle A  B  C  D   or             intersectCircle S   A  B   or             intersectCircle S   B  C   or             intersectCircle S   C  D   or             intersectCircle S   D  A      If you re writing any geometry you probably have the above functions in your library already  Otherwise  pointInRectangle   can be implemented in several ways  any of the general point in polygon methods will work  but for a rectangle you can just check whether this works   0   AP  AB   AB  AB and 0   AP  AD   AD  AD   And intersectCircle   is easy to implement too  one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints  and check the endpoints otherwise   The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon     doesn t even have to be convex

User · Answer

Improving a little bit the answer of e James  double dx   abs circle x - rect x  - rect w   2         dy   abs circle y - rect y  - rect h   2   if  dx  gt  circle r    dy  gt  circle r    return false    if  dx  lt   0    dy  lt   0    return true     return  dx   dx   dy   dy  lt   circle r   circle r    This subtracts rect w   2 and rect h   2 once instead of up to three times

User · Answer

I created class for work with shapes hope you enjoy  public class Geomethry     public static boolean intersectionCircleAndRectangle int circleX  int circleY  int circleR  int rectangleX  int rectangleY  int rectangleWidth  int rectangleHeight       boolean result   false       float rectHalfWidth   rectangleWidth 2 0f      float rectHalfHeight   rectangleHeight 2 0f       float rectCenterX   rectangleX   rectHalfWidth      float rectCenterY   rectangleY   rectHalfHeight       float deltax   Math abs rectCenterX - circleX       float deltay   Math abs rectCenterY - circleY        float lengthHypotenuseSqure   deltax deltax   deltay deltay       do             check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle         if lengthHypotenuseSqure  gt    rectHalfWidth circleR   rectHalfWidth circleR     rectHalfHeight circleR   rectHalfHeight circleR                   System out println  distance between the centerse is more than the distance between the circumcircle of rectangle and circle                break                        check that distance between the centerse is less than the distance between the inscribed circle         float rectMinHalfSide   Math min rectHalfWidth  rectHalfHeight           if lengthHypotenuseSqure  lt    rectMinHalfSide circleR   rectMinHalfSide circleR                   System out println  distance between the centerse is less than the distance between the inscribed circle                result true              break                        check that the squares relate to angles         if  deltax  gt   rectHalfWidth circleR  0 9   amp  amp   deltay  gt   rectHalfHeight circleR  0 9                  System out println  squares relate to angles                result true                 while false        return result     public static boolean intersectionRectangleAndRectangle int rectangleX  int rectangleY  int rectangleWidth  int rectangleHeight  int rectangleX2  int rectangleY2  int rectangleWidth2  int rectangleHeight2       boolean result   false       float rectHalfWidth   rectangleWidth 2 0f      float rectHalfHeight   rectangleHeight 2 0f      float rectHalfWidth2   rectangleWidth2 2 0f      float rectHalfHeight2   rectangleHeight2 2 0f       float deltax   Math abs  rectangleX   rectHalfWidth  -  rectangleX2   rectHalfWidth2        float deltay   Math abs  rectangleY   rectHalfHeight  -  rectangleY2   rectHalfHeight2         float lengthHypotenuseSqure   deltax deltax   deltay deltay       do             check that distance between the centerse is more than the distance between the circumcircle         if lengthHypotenuseSqure  gt    rectHalfWidth rectHalfWidth2   rectHalfWidth rectHalfWidth2     rectHalfHeight rectHalfHeight2   rectHalfHeight rectHalfHeight2                   System out println  distance between the centerse is more than the distance between the circumcircle                break                        check that distance between the centerse is less than the distance between the inscribed circle         float rectMinHalfSide   Math min rectHalfWidth  rectHalfHeight           float rectMinHalfSide2   Math min rectHalfWidth2  rectHalfHeight2           if lengthHypotenuseSqure  lt    rectMinHalfSide rectMinHalfSide2   rectMinHalfSide rectMinHalfSide2                   System out println  distance between the centerse is less than the distance between the inscribed circle                result true              break                        check that the squares relate to angles         if  deltax  gt   rectHalfWidth rectHalfWidth2  0 9   amp  amp   deltay  gt   rectHalfHeight rectHalfHeight2  0 9                  System out println  squares relate to angles                result true                 while false        return result

User · Answer

There are only two cases when the circle intersects with the rectangle    Either the circle s centre lies inside the rectangle  or One of the edges of the rectangle has a point in the circle    Note that this does not require the rectangle to be axis-parallel       One way to see this  if none of the edges has a point in the circle  if all the edges are completely  outside  the circle   then the only way the circle can still intersect the polygon is if it lies completely inside the polygon    With that insight  something like the following will work  where the circle has centre P and radius R  and the rectangle has vertices A  B  C  D in that order  not complete code    def intersect Circle P  R   Rectangle A  B  C  D        S   Circle P  R      return  pointInRectangle P  Rectangle A  B  C  D   or             intersectCircle S   A  B   or             intersectCircle S   B  C   or             intersectCircle S   C  D   or             intersectCircle S   D  A      If you re writing any geometry you probably have the above functions in your library already  Otherwise  pointInRectangle   can be implemented in several ways  any of the general point in polygon methods will work  but for a rectangle you can just check whether this works   0   AP  AB   AB  AB and 0   AP  AD   AD  AD   And intersectCircle   is easy to implement too  one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints  and check the endpoints otherwise   The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon     doesn t even have to be convex

User · Answer

For those have to calculate Circle Rectangle collision in Geographic Coordinates with SQL  this is my implementation in oracle 11 of e James suggested algorithm   In input it requires circle coordinates  circle radius in km and two vertices coordinates of the rectangle   CREATE OR REPLACE FUNCTION  DETECT CIRC RECT COLLISION        circleCenterLat     IN NUMBER       -- circle Center Latitude     circleCenterLon     IN NUMBER       -- circle Center Longitude     circleRadius        IN NUMBER       -- circle Radius in KM     rectSWLat           IN NUMBER       -- rectangle South West Latitude     rectSWLon           IN NUMBER       -- rectangle South West Longitude     rectNELat           IN NUMBER       -- rectangle North Est Latitude     rectNELon           IN NUMBER       -- rectangle North Est Longitude   RETURN NUMBER AS     -- converts km to degrees  use 69 if miles      kmToDegreeConst     NUMBER    111 045       -- Remaining rectangle vertices      rectNWLat   NUMBER      rectNWLon   NUMBER      rectSELat   NUMBER      rectSELon   NUMBER       rectHeight  NUMBER      rectWIdth   NUMBER       circleDistanceLat   NUMBER      circleDistanceLon   NUMBER      cornerDistanceSQ    NUMBER   BEGIN     -- Initialization of remaining rectangle vertices       rectNWLat    rectNELat      rectNWLon    rectSWLon      rectSELat    rectSWLat      rectSELon    rectNELon       -- Rectangle sides length calculation     rectHeight    calc distance rectSWLat  rectSWLon  rectNWLat  rectNWLon       rectWidth    calc distance rectSWLat  rectSWLon  rectSELat  rectSELon        circleDistanceLat    abs   circleCenterLat   kmToDegreeConst  -   rectSWLat   kmToDegreeConst     rectHeight 2          circleDistanceLon    abs   circleCenterLon   kmToDegreeConst  -   rectSWLon   kmToDegreeConst     rectWidth 2           IF circleDistanceLon  gt    rectWidth 2    circleRadius  THEN         RETURN -1    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLat  gt    rectHeight 2    circleRadius  THEN         RETURN -1    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLon  lt    rectWidth 2  THEN         RETURN 0    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLat  lt    rectHeight 2  THEN         RETURN 0    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF        cornerDistanceSQ    POWER circleDistanceLon -  rectWidth 2   2    POWER circleDistanceLat -  rectHeight 2   2        IF cornerDistanceSQ  lt    POWER circleRadius  2  THEN         RETURN 0   --  -1   gt  NO Collision   0   gt  Collision Detected     ELSE         RETURN -1   --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       RETURN -1   --  -1   gt  NO Collision   0   gt  Collision Detected END

User · Answer

worked for me  only work when angle of rectangle is 180   function intersects circle  rect      let left   rect x   rect width  gt  circle x - circle radius    let right   rect x  lt  circle x   circle radius    let top   rect y  lt  circle y   circle radius    let bottom   rect y   rect height  gt  circle y - circle radius    return left  amp  amp  right  amp  amp  bottom  amp  amp  top

User · Answer

Works  just figured this out a week ago  and just now got to testing it   double theta   Math atan2 cir getX  -sqr getX   1 0                            cir getY  -sqr getY   1 0     radians of the angle double dBox    distance from box to edge of box in direction of the circle  if  theta  gt   Math PI 4  amp  amp  theta  lt   3 Math PI   4         theta  lt  -Math PI 4  amp  amp  theta  gt  -3 Math PI   4         dBox   sqr getS      2 Math sin theta      else       dBox   sqr getS      2 Math cos theta      boolean touching    Math abs dBox   gt                       Math sqrt Math pow sqr getX  -cir getX    2                                  Math pow sqr getY  -cir getY    2

User · Answer

To visualise  take your keyboard s numpad  If the key  5  represents your rectangle  then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle  with 5 being the inside    1  If the circle s center is in quadrant 5  i e  inside the rectangle  then the two shapes intersect   With that out of the way  there are two possible cases  a  The circle intersects with two or more neighboring edges of the rectangle  b  The circle intersects with one edge of the rectangle   The first case is simple  If the circle intersects with two neighboring edges of the rectangle  it must contain the corner connecting those two edges   That  or its center lies in quadrant 5  which we have already covered  Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well    2  If any of the corners A  B  C  D of the rectangle lie inside the circle  then the two shapes intersect   The second case is trickier  We should make note of that it may only happen when the circle s center lies in one of the quadrants 2  4  6 or 8   In fact  if the center is on any of the quadrants 1  3  7  8  the corresponding corner will be the closest point to it    Now we have the case that the circle s center is in one of the  edge  quadrants  and it only intersects with the corresponding edge  Then  the point on the edge that is closest to the circle s center  must lie inside the circle   3  For each line AB  BC  CD  DA  construct perpendicular lines p AB P   p BC P   p CD P   p DA P  through the circle s center P  For each perpendicular line  if the intersection with the original edge lies inside the circle  then the two shapes intersect   There is a shortcut for this last step  If the circle s center is in quadrant 8 and the edge AB is the top edge  the point of intersection will have the y-coordinate of A and B  and the x-coordinate of center P   You can construct the four line intersections and check if they lie on their corresponding edges  or find out which quadrant P is in and check the corresponding intersection  Both should simplify to the same boolean equation  Be wary of that the step 2 above did not rule out P being in one of the  corner  quadrants  it just looked for an intersection   Edit  As it turns out  I have overlooked the simple fact that  2 is a subcase of  3 above  After all  corners too are points on the edges  See  ShreevatsaR s answer below for a great explanation  And in the meanwhile  forget  2 above unless you want a quick but redundant check

User · Answer

This function detect collisions  intersections  between Circle and Rectangle  He works like e James method in his answer  but this one detect collisions for all angles of rectangle  not only right up corner    NOTE    aRect origin x and aRect origin y are coordinates of bottom left angle of rectangle   aCircle x and aCircle y are coordinates of Circle Center   static inline BOOL RectIntersectsCircle CGRect aRect  Circle aCircle         float testX   aCircle x      float testY   aCircle y       if  testX  lt  aRect origin x          testX   aRect origin x      if  testX  gt   aRect origin x   aRect size width           testX    aRect origin x   aRect size width       if  testY  lt  aRect origin y          testY   aRect origin y      if  testY  gt   aRect origin y   aRect size height           testY    aRect origin y   aRect size height        return   aCircle x - testX     aCircle x - testX     aCircle y - testY     aCircle y - testY    lt  aCircle radius   aCircle radius

User · Answer

def colision rect  circle   dx   rect x - circle x dy   rect y - circle y distance    dy  2   dx  2   0 5 angle to    rect angle   math atan2 dx  dy  3 1415 180 0    360 if  angle to gt 135 and angle to lt 225  or  angle to gt 0 and angle to lt 45  or  angle to gt 315 and angle to lt 360        if distance  lt   circle rad 2    rect height 2 0   1  0 5 abs math sin angle to math pi 180               return True else      if distance  lt   circle rad 2    rect width 2 0   1  0 5 abs math cos angle to math pi 180               return True return False

User · Answer

Here is how I would do it   bool intersects CircleType circle  RectType rect        circleDistance x   abs circle x - rect x       circleDistance y   abs circle y - rect y        if  circleDistance x  gt   rect width 2   circle r     return false        if  circleDistance y  gt   rect height 2   circle r     return false         if  circleDistance x  lt    rect width 2     return true         if  circleDistance y  lt    rect height 2     return true         cornerDistance sq    circleDistance x - rect width 2  2                             circleDistance y - rect height 2  2       return  cornerDistance sq  lt    circle r 2        Here s how it works        The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle  This collapses the four quadrants down into one  so that the calculations do not have to be done four times  The image shows the area in which the center of the circle must now lie  Note that only the single quadrant is shown  The rectangle is the grey area  and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle  The center of the circle has to be within this red border for the intersection to occur  The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle  in either direction  that no intersection is possible  This corresponds to the green area in the image  The third pair of lines handle the easy cases where the circle is close enough to the rectangle  in either direction  that an intersection is guaranteed  This corresponds to the orange and grey sections in the image  Note that this step must be done after step 2 for the logic to make sense  The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle  To solve  compute the distance from the center of the circle and the corner  and then verify that the distance is not more than the radius of the circle  This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area

User · Answer

There are only two cases when the circle intersects with the rectangle    Either the circle s centre lies inside the rectangle  or One of the edges of the rectangle has a point in the circle    Note that this does not require the rectangle to be axis-parallel       One way to see this  if none of the edges has a point in the circle  if all the edges are completely  outside  the circle   then the only way the circle can still intersect the polygon is if it lies completely inside the polygon    With that insight  something like the following will work  where the circle has centre P and radius R  and the rectangle has vertices A  B  C  D in that order  not complete code    def intersect Circle P  R   Rectangle A  B  C  D        S   Circle P  R      return  pointInRectangle P  Rectangle A  B  C  D   or             intersectCircle S   A  B   or             intersectCircle S   B  C   or             intersectCircle S   C  D   or             intersectCircle S   D  A      If you re writing any geometry you probably have the above functions in your library already  Otherwise  pointInRectangle   can be implemented in several ways  any of the general point in polygon methods will work  but for a rectangle you can just check whether this works   0   AP  AB   AB  AB and 0   AP  AD   AD  AD   And intersectCircle   is easy to implement too  one way would be to check if the foot of the perpendicular from P to the line is close enough and between the endpoints  and check the endpoints otherwise   The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon     doesn t even have to be convex

User · Answer

Works  just figured this out a week ago  and just now got to testing it   double theta   Math atan2 cir getX  -sqr getX   1 0                            cir getY  -sqr getY   1 0     radians of the angle double dBox    distance from box to edge of box in direction of the circle  if  theta  gt   Math PI 4  amp  amp  theta  lt   3 Math PI   4         theta  lt  -Math PI 4  amp  amp  theta  gt  -3 Math PI   4         dBox   sqr getS      2 Math sin theta      else       dBox   sqr getS      2 Math cos theta      boolean touching    Math abs dBox   gt                       Math sqrt Math pow sqr getX  -cir getX    2                                  Math pow sqr getY  -cir getY    2

User · Answer

Here s a fast one-line test for this   if  length max abs center - rect mid  - rect halves  0    lt   radius          They intersect      This is the axis-aligned case where rect halves is a positive vector pointing from the rectangle middle to a corner  The expression inside length   is a delta vector from center to a closest point in the rectangle  This works in any dimension

User · Answer

Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle  if its less then the radius  then the shapes are intersecting   if sqrt  rectangleRight x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleRight x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect

User · Answer

For those have to calculate Circle Rectangle collision in Geographic Coordinates with SQL  this is my implementation in oracle 11 of e James suggested algorithm   In input it requires circle coordinates  circle radius in km and two vertices coordinates of the rectangle   CREATE OR REPLACE FUNCTION  DETECT CIRC RECT COLLISION        circleCenterLat     IN NUMBER       -- circle Center Latitude     circleCenterLon     IN NUMBER       -- circle Center Longitude     circleRadius        IN NUMBER       -- circle Radius in KM     rectSWLat           IN NUMBER       -- rectangle South West Latitude     rectSWLon           IN NUMBER       -- rectangle South West Longitude     rectNELat           IN NUMBER       -- rectangle North Est Latitude     rectNELon           IN NUMBER       -- rectangle North Est Longitude   RETURN NUMBER AS     -- converts km to degrees  use 69 if miles      kmToDegreeConst     NUMBER    111 045       -- Remaining rectangle vertices      rectNWLat   NUMBER      rectNWLon   NUMBER      rectSELat   NUMBER      rectSELon   NUMBER       rectHeight  NUMBER      rectWIdth   NUMBER       circleDistanceLat   NUMBER      circleDistanceLon   NUMBER      cornerDistanceSQ    NUMBER   BEGIN     -- Initialization of remaining rectangle vertices       rectNWLat    rectNELat      rectNWLon    rectSWLon      rectSELat    rectSWLat      rectSELon    rectNELon       -- Rectangle sides length calculation     rectHeight    calc distance rectSWLat  rectSWLon  rectNWLat  rectNWLon       rectWidth    calc distance rectSWLat  rectSWLon  rectSELat  rectSELon        circleDistanceLat    abs   circleCenterLat   kmToDegreeConst  -   rectSWLat   kmToDegreeConst     rectHeight 2          circleDistanceLon    abs   circleCenterLon   kmToDegreeConst  -   rectSWLon   kmToDegreeConst     rectWidth 2           IF circleDistanceLon  gt    rectWidth 2    circleRadius  THEN         RETURN -1    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLat  gt    rectHeight 2    circleRadius  THEN         RETURN -1    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLon  lt    rectWidth 2  THEN         RETURN 0    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       IF circleDistanceLat  lt    rectHeight 2  THEN         RETURN 0    --  -1   gt  NO Collision   0   gt  Collision Detected     END IF        cornerDistanceSQ    POWER circleDistanceLon -  rectWidth 2   2    POWER circleDistanceLat -  rectHeight 2   2        IF cornerDistanceSQ  lt    POWER circleRadius  2  THEN         RETURN 0   --  -1   gt  NO Collision   0   gt  Collision Detected     ELSE         RETURN -1   --  -1   gt  NO Collision   0   gt  Collision Detected     END IF       RETURN -1   --  -1   gt  NO Collision   0   gt  Collision Detected END

User · Answer

Actually  this is much more simple  You need only two things   First  you need to find four orthogonal distances from the circle centre to each line of the rectangle  Then your circle will not intersect the rectangle if any three of them are larger than the circle radius   Second  you need to find the distance between the circle centre and the rectangle centre  then you circle will not be inside of the rectangle if the distance is larger than a half of the rectangle diagonal length   Good luck

User · Answer

Here s a fast one-line test for this   if  length max abs center - rect mid  - rect halves  0    lt   radius          They intersect      This is the axis-aligned case where rect halves is a positive vector pointing from the rectangle middle to a corner  The expression inside length   is a delta vector from center to a closest point in the rectangle  This works in any dimension

User · Answer

Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle  if its less then the radius  then the shapes are intersecting   if sqrt  rectangleRight x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleRight x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect

User · Answer

I ve a method which avoids the expensive pythagoras if not necessary - ie  when bounding boxes of the rectangle and the circle do not intersect   And it ll work for non-euclidean too   class Circle       create the bounding box of the circle only once  BBox bbox    public boolean intersect BBox b           test top intersect     if  lat  gt  b maxLat            if  lon  lt  b minLon              return normDist b maxLat  b minLon   lt   normedDist          if  lon  gt  b maxLon              return normDist b maxLat  b maxLon   lt   normedDist          return b maxLat - bbox minLat  gt  0                test bottom intersect     if  lat  lt  b minLat            if  lon  lt  b minLon              return normDist b minLat  b minLon   lt   normedDist          if  lon  gt  b maxLon              return normDist b minLat  b maxLon   lt   normedDist          return bbox maxLat - b minLat  gt  0                test middle intersect     if  lon  lt  b minLon          return bbox maxLon - b minLon  gt  0      if  lon  gt  b maxLon          return b maxLon - bbox minLon  gt  0      return true           minLat maxLat can be replaced with minY maxY and the same for minLon  maxLon  replace it with minX  maxX normDist ist just a bit faster method then the full distance calculation  E g  without the square-root in euclidean space  or without a lot of other stuff for haversine   dLat  lat-circleY   dLon  lon-circleX   normed dLat dLat dLon dLon  Of course if you use that normDist method you ll need to do create a normedDist   dist dist  for the circle   See the full BBox and Circle code of my GraphHopper project

User · Answer

I ve a method which avoids the expensive pythagoras if not necessary - ie  when bounding boxes of the rectangle and the circle do not intersect   And it ll work for non-euclidean too   class Circle       create the bounding box of the circle only once  BBox bbox    public boolean intersect BBox b           test top intersect     if  lat  gt  b maxLat            if  lon  lt  b minLon              return normDist b maxLat  b minLon   lt   normedDist          if  lon  gt  b maxLon              return normDist b maxLat  b maxLon   lt   normedDist          return b maxLat - bbox minLat  gt  0                test bottom intersect     if  lat  lt  b minLat            if  lon  lt  b minLon              return normDist b minLat  b minLon   lt   normedDist          if  lon  gt  b maxLon              return normDist b minLat  b maxLon   lt   normedDist          return bbox maxLat - b minLat  gt  0                test middle intersect     if  lon  lt  b minLon          return bbox maxLon - b minLon  gt  0      if  lon  gt  b maxLon          return b maxLon - bbox minLon  gt  0      return true           minLat maxLat can be replaced with minY maxY and the same for minLon  maxLon  replace it with minX  maxX normDist ist just a bit faster method then the full distance calculation  E g  without the square-root in euclidean space  or without a lot of other stuff for haversine   dLat  lat-circleY   dLon  lon-circleX   normed dLat dLat dLon dLon  Of course if you use that normDist method you ll need to do create a normedDist   dist dist  for the circle   See the full BBox and Circle code of my GraphHopper project

User · Answer

The simplest solution I ve come up with is pretty straightforward   It works by finding the point in the rectangle closest to the circle  then comparing the distance   You can do all of this with a few operations  and even avoid the sqrt function   public boolean intersects float cx  float cy  float radius  float left  float top  float right  float bottom       float closestX    cx  lt  left   left    cx  gt  right   right   cx       float closestY    cy  lt  top   top    cy  gt  bottom   bottom   cy       float dx   closestX - cx     float dy   closestY - cy      return   dx   dx   dy   dy    lt   radius   radius      And that s it  The above solution assumes an origin in the upper left of the world with the x-axis pointing down   If you want a solution to handling collisions between a moving circle and rectangle  it s far more complicated and covered in another answer of mine

User · Answer

Here is how I would do it   bool intersects CircleType circle  RectType rect        circleDistance x   abs circle x - rect x       circleDistance y   abs circle y - rect y        if  circleDistance x  gt   rect width 2   circle r     return false        if  circleDistance y  gt   rect height 2   circle r     return false         if  circleDistance x  lt    rect width 2     return true         if  circleDistance y  lt    rect height 2     return true         cornerDistance sq    circleDistance x - rect width 2  2                             circleDistance y - rect height 2  2       return  cornerDistance sq  lt    circle r 2        Here s how it works        The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle  This collapses the four quadrants down into one  so that the calculations do not have to be done four times  The image shows the area in which the center of the circle must now lie  Note that only the single quadrant is shown  The rectangle is the grey area  and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle  The center of the circle has to be within this red border for the intersection to occur  The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle  in either direction  that no intersection is possible  This corresponds to the green area in the image  The third pair of lines handle the easy cases where the circle is close enough to the rectangle  in either direction  that an intersection is guaranteed  This corresponds to the orange and grey sections in the image  Note that this step must be done after step 2 for the logic to make sense  The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle  To solve  compute the distance from the center of the circle and the corner  and then verify that the distance is not more than the radius of the circle  This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area

User · Answer

Here s my C code for resolving a collision between a sphere and a non-axis aligned box  It relies on a couple of my own library routines  but it may prove useful to some  I m using it in a game and it works perfectly   float physicsProcessCollisionBetweenSelfAndActorRect SPhysics  self  SPhysics  actor        float diff   99999       SVector relative position of circle   getDifference2DBetweenVectors  amp self- gt worldPosition   amp actor- gt worldPosition       rotateVector2DBy  amp relative position of circle  -actor- gt axis angleZ      This aligns the coord system so the rect becomes an AABB      float x clamped within rectangle   relative position of circle x      float y clamped within rectangle   relative position of circle y      LIMIT x clamped within rectangle  actor- gt physicsRect l  actor- gt physicsRect r       LIMIT y clamped within rectangle  actor- gt physicsRect b  actor- gt physicsRect t           Calculate the distance between the circle s center and this closest point     float distance to nearest edge x   relative position of circle x - x clamped within rectangle      float distance to nearest edge y   relative position of circle y - y clamped within rectangle          If the distance is less than the circle s radius  an intersection occurs     float distance sq x   SQUARE distance to nearest edge x       float distance sq y   SQUARE distance to nearest edge y       float radius sq   SQUARE self- gt physicsRadius       if distance sq x   distance sq y  lt  radius sq                   float half rect w    actor- gt physicsRect r - actor- gt physicsRect l    0 5f          float half rect h    actor- gt physicsRect t - actor- gt physicsRect b    0 5f           CREATE VECTOR push vector                        If we re at one of the corners of this object  treat this as a circular circular collision         if fabs relative position of circle x   gt  half rect w  amp  amp  fabs relative position of circle y   gt  half rect h                        SVector edges              if relative position of circle x  gt  0  edges x   half rect w  else edges x   -half rect w              if relative position of circle y  gt  0  edges y   half rect h  else edges y   -half rect h                  push vector   relative position of circle              moveVectorByInverseVector2D  amp push vector   amp edges                   We now have the vector from the corner of the rect to the point              float delta length   getVector2DMagnitude  amp push vector               float diff   self- gt physicsRadius - delta length     Find out how far away we are from our ideal distance                 Normalise the vector             push vector x    delta length              push vector y    delta length              scaleVector2DBy  amp push vector  diff      Now multiply it by the difference             push vector z   0                    else    Nope - just bouncing against one of the edges                       if relative position of circle x  gt  0     Ball is to the right                 push vector x    half rect w   self- gt physicsRadius  - relative position of circle x              else                 push vector x   -  half rect w   self- gt physicsRadius    relative position of circle x                if relative position of circle y  gt  0     Ball is above                 push vector y    half rect h   self- gt physicsRadius  - relative position of circle y              else                 push vector y   -  half rect h   self- gt physicsRadius    relative position of circle y                if fabs push vector x   lt  fabs push vector y                   push vector y   0              else                 push vector x   0                     diff   0     Cheat  since we don t do anything with the value anyway         rotateVector2DBy  amp push vector  actor- gt axis angleZ           SVector  from    amp self- gt worldPosition                 moveVectorBy2D from  push vector x  push vector y                return diff

User · Answer

The simplest solution I ve come up with is pretty straightforward   It works by finding the point in the rectangle closest to the circle  then comparing the distance   You can do all of this with a few operations  and even avoid the sqrt function   public boolean intersects float cx  float cy  float radius  float left  float top  float right  float bottom       float closestX    cx  lt  left   left    cx  gt  right   right   cx       float closestY    cy  lt  top   top    cy  gt  bottom   bottom   cy       float dx   closestX - cx     float dy   closestY - cy      return   dx   dx   dy   dy    lt   radius   radius      And that s it  The above solution assumes an origin in the upper left of the world with the x-axis pointing down   If you want a solution to handling collisions between a moving circle and rectangle  it s far more complicated and covered in another answer of mine

User · Answer

To visualise  take your keyboard s numpad  If the key  5  represents your rectangle  then all the keys 1-9 represent the 9 quadrants of space divided by the lines that make up your rectangle  with 5 being the inside    1  If the circle s center is in quadrant 5  i e  inside the rectangle  then the two shapes intersect   With that out of the way  there are two possible cases  a  The circle intersects with two or more neighboring edges of the rectangle  b  The circle intersects with one edge of the rectangle   The first case is simple  If the circle intersects with two neighboring edges of the rectangle  it must contain the corner connecting those two edges   That  or its center lies in quadrant 5  which we have already covered  Also note that the case where the circle intersects with only two opposing edges of the rectangle is covered as well    2  If any of the corners A  B  C  D of the rectangle lie inside the circle  then the two shapes intersect   The second case is trickier  We should make note of that it may only happen when the circle s center lies in one of the quadrants 2  4  6 or 8   In fact  if the center is on any of the quadrants 1  3  7  8  the corresponding corner will be the closest point to it    Now we have the case that the circle s center is in one of the  edge  quadrants  and it only intersects with the corresponding edge  Then  the point on the edge that is closest to the circle s center  must lie inside the circle   3  For each line AB  BC  CD  DA  construct perpendicular lines p AB P   p BC P   p CD P   p DA P  through the circle s center P  For each perpendicular line  if the intersection with the original edge lies inside the circle  then the two shapes intersect   There is a shortcut for this last step  If the circle s center is in quadrant 8 and the edge AB is the top edge  the point of intersection will have the y-coordinate of A and B  and the x-coordinate of center P   You can construct the four line intersections and check if they lie on their corresponding edges  or find out which quadrant P is in and check the corresponding intersection  Both should simplify to the same boolean equation  Be wary of that the step 2 above did not rule out P being in one of the  corner  quadrants  it just looked for an intersection   Edit  As it turns out  I have overlooked the simple fact that  2 is a subcase of  3 above  After all  corners too are points on the edges  See  ShreevatsaR s answer below for a great explanation  And in the meanwhile  forget  2 above unless you want a quick but redundant check

User · Answer

I developed this algorithm while making this game  https   mshwf github io mates   If the circle touches the square  then the distance between the centerline of the circle and the centerline of the square should equal  diameter side  2  So  let s have a variable named touching that holds that distance  The problem was  which centerline should I consider  the horizontal or the vertical  Consider this frame   Each centerline gives different distances  and only one is a correct indication to a no-collision  but using our human intuition is a start to understand how the natural algorithm works  They are not touching  which means that the distance between the two centerlines should be greater than touching  which means that the natural algorithm picks the horizontal centerlines  the vertical centerlines says there s a collision    By noticing multiple circles  you can tell  if the circle intersects with the vertical extension of the square  then we pick the vertical distance  between the horizontal centerlines   and if the circle intersects with the horizontal extension  we pick the horizontal distance   Another example  circle number 4  it intersects with the horizontal extension of the square  then we consider the horizontal distance which is equal to touching  Ok  the tough part is demystified  now we know how the algorithm will work  but how we know with which extension the circle intersects  It s easy actually  we calculate the distance between the most right x and the most left x  of both the circle and the square   and the same for the y-axis  the one with greater value is the axis with the extension that intersects with the circle  if it s greater than diameter side then the circle is outside the two square extensions  like circle  7   The code looks like  right   Math max square x square side  circle x circle rad   left   Math min square x  circle x-circle rad    bottom   Math max square y square side  circle y circle rad   top   Math min square y  circle y-circle rad    if  right - left  gt  down - top       compare with horizontal distance   else      compare with vertical distance      These equations assume that the reference point of the square is at its top left corner  and the reference point of the circle is at its center

User · Answer

Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle  if its less then the radius  then the shapes are intersecting   if sqrt  rectangleRight x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleRight x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleTop y - circleCenter y  2   lt  radius    then they intersect  if sqrt  rectangleLeft x - circleCenter x  2            rectangleBottom y - circleCenter y  2   lt  radius    then they intersect

[geometry] Circle-Rectangle collision detection (intersection)

Examples related to geometry

Examples related to collision-detection