Problem Description

The "Circle and Rectangle Overlapping" problem asks you to determine if a given circle overlaps with a given axis-aligned rectangle. The circle is defined by its center coordinates (x_center, y_center) and its radius radius. The rectangle is defined by its bottom-left corner (x1, y1) and its top-right corner (x2, y2).

Your task is to return true if the circle and the rectangle overlap, and false otherwise. Overlap is defined as having at least one point in common (including touching at the edge or corner).

• Inputs: radius, x_center, y_center, x1, y1, x2, y2
• Constraints:
  • All values are integers.
  • Rectangle sides are parallel to the axes.
  • The rectangle's bottom-left corner is at (x1, y1) and top-right is at (x2, y2).
• Return: true if the circle and rectangle overlap, false otherwise.

Thought Process

At first glance, you might think about checking every point of the rectangle to see if it lies within the circle, or vice versa. However, iterating over all points is inefficient and unnecessary.

Instead, the key insight is to find the closest point on the rectangle to the center of the circle. If the distance between this point and the circle's center is less than or equal to the radius, then the circle and rectangle overlap.

This approach avoids brute force by leveraging geometry: for any point outside a rectangle, the closest point on the rectangle can be found by "clamping" each coordinate to the rectangle's bounds.

Solution Approach

• Step 1: For the circle's center at (x_center, y_center), find the closest point on the rectangle to this center.
  • For the x-coordinate: clamp x_center to the interval [x1, x2].
  • For the y-coordinate: clamp y_center to the interval [y1, y2].
• Step 2: Compute the squared distance between the circle's center and this closest point.
  • Let this point be (closestX, closestY).
  • Squared distance: (x_center - closestX)^2 + (y_center - closestY)^2
• Step 3: Compare this squared distance to radius^2.
  • If the squared distance is less than or equal to radius^2, the circle and rectangle overlap.
  • Otherwise, they do not overlap.
• Why this works: If the circle's center is inside the rectangle, the closest point is the center itself (distance 0). If the center is outside, clamping finds the rectangle edge or corner nearest to the center.

Example Walkthrough

Example:
radius = 2, x_center = 4, y_center = 4, x1 = 1, y1 = 1, x2 = 3, y2 = 3

1. Find the closest point on the rectangle to the circle's center:
   • Clamp x_center (4) to [1, 3] ⇒ closestX = 3
   • Clamp y_center (4) to [1, 3] ⇒ closestY = 3
2. Compute squared distance:
   • (4 - 3)^2 + (4 - 3)^2 = 1 + 1 = 2
3. Compare to radius^2 = 4:
   • 2 <= 4, so the circle and rectangle overlap.

Another Example:
radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = 3, x2 = 3, y2 = 5

• Clamp x_center (1) to [1, 3] ⇒ closestX = 1
• Clamp y_center (1) to [3, 5] ⇒ closestY = 3
• Distance squared: (1-1)^2 + (1-3)^2 = 0 + 4 = 4
• radius^2 = 1. Since 4 > 1, no overlap.

Time and Space Complexity

• Brute-force approach:
  • Checking all points on the rectangle or circle would be O(Area of rectangle) or O(Area of circle), which is highly inefficient for large inputs.
• Optimized approach (current solution):
  • All operations are basic arithmetic and clamping, which are O(1).
  • Time Complexity: O(1)
  • Space Complexity: O(1)
• Why? No loops, no extra data structures, just a few calculations.

Summary

The problem of checking overlap between a circle and a rectangle can be solved efficiently by finding the closest point on the rectangle to the circle's center and checking if it lies within the circle's radius. This approach is both simple and optimal, avoiding unnecessary brute-force checks and relying on geometric intuition and arithmetic operations.

The key insight is to use "clamping" to find the closest rectangle point and then use the distance formula. The solution is elegant, efficient, and easy to implement in any programming language.

Code Implementation

class Solution:
    def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # Clamp circle center to rectangle
        closestX = min(max(x_center, x1), x2)
        closestY = min(max(y_center, y1), y2)
        # Compute squared distance
        dx = x_center - closestX
        dy = y_center - closestY
        return dx * dx + dy * dy <= radius * radius
      

class Solution {
public:
    bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        int closestX = std::max(x1, std::min(x_center, x2));
        int closestY = std::max(y1, std::min(y_center, y2));
        int dx = x_center - closestX;
        int dy = y_center - closestY;
        return dx * dx + dy * dy <= radius * radius;
    }
};
      

class Solution {
    public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
        int closestX = Math.max(x1, Math.min(x_center, x2));
        int closestY = Math.max(y1, Math.min(y_center, y2));
        int dx = x_center - closestX;
        int dy = y_center - closestY;
        return dx * dx + dy * dy <= radius * radius;
    }
}
      

var checkOverlap = function(radius, x_center, y_center, x1, y1, x2, y2) {
    const clamp = (val, min, max) => Math.max(min, Math.min(val, max));
    let closestX = clamp(x_center, x1, x2);
    let closestY = clamp(y_center, y1, y2);
    let dx = x_center - closestX;
    let dy = y_center - closestY;
    return dx * dx + dy * dy <= radius * radius;
};