5

I am implementing (in C++) a method to detect when an overlap is occurring between two static, axis-aligned shapes on a 2d plane. The shapes are either squares or circles, and therefore there are three cases I need to consider for overlap: square-square, circle-circle, and circle-square.

Square-square and circle-circle were simple enough, but I am struggling to find any solid information online about what the correct algorithm is for calculating square-circle overlap.

I am aware that I could embed the square inside a circle (or vice versa) as a rough method, but I'm interested in what would be considered the cleanest way to do this more precisely?

Researching it online suggests there is a 'correct' answer to this question, but it isn't made clear what exactly that answer is.

transiti0nary
  • 493
  • 6
  • 25
  • 1
    https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection – Michael Dorgan Dec 04 '17 at 18:13
  • 1
    More generally, find the closest point on the rectangle (square) to the center of the circle. If the shape is AA, this is trivial. If not, a dot product will give this. If this distance is less than radius of circle, there is a collision. Unless ciricle is completely within square, then you need to check each point for inclusion (distance of each vertex from center vs radius.) – Michael Dorgan Dec 04 '17 at 18:19
  • The cleanest method depends on which information are stored for your figure. Is your circle modeled by the coordinate of 3 point, or you have the center and radius. And for your rectangle, idem 3 points, or anything else? If you provide me that I'll be happy to get back to high school mathematics! – Oliv Dec 04 '17 at 19:47
  • Or I just give you a tip: let's `A` and `B` be the extremity of a side of your rectangle of lenght `l`, let's `C` be the center of the circle. Let's `d` be the distance of `C` to the line (AB), you have this relation `abs(ABxAC)=l*d` where `x` is the cross product AB and AC are vectors. Moreover the sign of the product can indicate weither the circul center is toward the inside or the outside. – Oliv Dec 04 '17 at 20:03

1 Answers1

2

Here's a simple and fast algorithm:

bool doesSquareCircleOverlap(float squareCenterX, float squareCenterY, float squareHalfSize, float circleCenterX, float circleCenterY, float circleRadius) {
    float x = fabs(circleCenterX - squareCenterX) - squareHalfSize;
    float y = fabs(circleCenterY - squareCenterY) - squareHalfSize;

    if (x>0) {
        if (y>0) {
            return x*x + y*y<circleRadius*circleRadius;
        } else {
            return x<circleRadius;
        }
    } else {
        return y<circleRadius;
    }
}

Note that the square is represented by the center and half-size.

Basically, what it does is:

  • it removes symmetrical cases with fabs()
  • puts the corner into the origin
  • checks which area the center of circle is, to determine the closest point on the square from the circle. If this closes point is nearer than circleRadius, then there is an overlap.
geza
  • 28,403
  • 6
  • 61
  • 135