Circle and Rectangle Overlapping Solution in C++

Problem Description

So, you think you can just throw a circle and a rectangle together and expect them to get along? Well, think again! The problem at hand is to determine whether a circle and a rectangle overlap. Imagine a circle trying to squeeze into a rectangle-shaped room—awkward, right?

In this problem, you are given the radius of the circle and its center coordinates, along with the coordinates of the rectangle’s bottom-left and top-right corners. Your task is to figure out if the circle and rectangle are having a little overlap party or if they are just avoiding each other like two exes at a wedding.

Code Solution


class Solution {
 public:
  bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1,
                    int x2, int y2) {
    auto clamp = [&](int center, int mn, int mx) {
      return max(mn, min(mx, center));
    };

    // the closest point to the circle within the rectangle
    int closestX = clamp(x_center, x1, x2);
    int closestY = clamp(y_center, y1, y2);

    // the distance between the circle's center and its closest point
    int distanceX = x_center - closestX;
    int distanceY = y_center - closestY;

    // If the distance < the circle's radius, an intersection occurs.
    return (distanceX * distanceX) + (distanceY * distanceY) <=
           (radius * radius);
  }
};

Approach

The approach taken in this solution is quite clever. It first determines the closest point on the rectangle to the center of the circle. This is done using a clamping function that ensures the point lies within the rectangle's boundaries. Then, it calculates the distance from the circle's center to this closest point. If this distance is less than or equal to the circle's radius, we have an overlap!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(1)
Space Complexity	O(1)

Real-World Example

Imagine you are at a park where a circular fountain is surrounded by a rectangular flower bed. You want to know if the fountain's water splashes into the flower bed. This problem is akin to determining if the circle (fountain) overlaps with the rectangle (flower bed). If the fountain's radius is large enough to reach the edges of the flower bed, then yes, they overlap!