1401. Circle and Rectangle Overlapping - Detailed Explanation
Problem Statement
Given a circle and a rectangle, determine if they overlap. The circle is specified by its center coordinates (xCenter, yCenter) and its radius, while the rectangle is given by its bottom-left corner (x1, y1) and top-right corner (x2, y2). Two shapes are said to overlap if they share at least one common point (including touching).
Example 1
- Input: xCenter = 1, yCenter = 3, radius = 1, x1 = 0, y1 = 0, x2 = 2, y2 = 2
- Output: true
- Explanation: The circle centered at (1, 3) with radius 1 touches the rectangle at (1, 2). Their boundaries meet, so they overlap.
Example 2
- Input: xCenter = 1, yCenter = 1, radius = 1, x1 = 1, y1 = -1, x2 = 3, y2 = 1
- Output: true
- Explanation: The circle centered at (1, 1) with radius 1 overlaps with the rectangle since part of the circle extends into the rectangle area.
Example 3
- Input: xCenter = 1, yCenter = 1, radius = 1, x1 = -1, y1 = -1, x2 = 0, y2 = 0
- Output: false
- Explanation: The rectangle is completely away from the circle; the closest point on the rectangle is (0, 0) which is farther than the circle’s radius from the circle’s center.
Constraints
- All coordinates and the radius are integers.
- The circle and rectangle dimensions can be such that they just touch at a point or along an edge, which is considered overlapping.
Hints
-
Closest Point on the Rectangle:
Find the point in the rectangle that is closest to the circle’s center. You can do this by "clamping" the x-coordinate of the circle’s center between x1 and x2, and similarly clamping the y-coordinate between y1 and y2. -
Distance Comparison:
Once you have the closest point, compute the squared distance between this point and the circle’s center. If the squared distance is less than or equal to the square of the radius, then the circle and rectangle overlap.
Approaches Overview
Approach: Closest Point and Distance Check
- Step 1: Clamp the circle's center coordinates to the rectangle boundaries.
- For the x-coordinate:
( \text{closestX} = \max(x1, \min(xCenter, x2)) ) - For the y-coordinate:
( \text{closestY} = \max(y1, \min(yCenter, y2)) )
- For the x-coordinate:
- Step 2: Calculate the squared distance between (xCenter, yCenter) and (closestX, closestY):
( \text{distanceSquared} = (closestX - xCenter)^2 + (closestY - yCenter)^2 ) - Step 3: Compare this squared distance with the square of the radius. If
( \text{distanceSquared} \leq \text{radius}^2 )
then the circle and rectangle overlap.
Why This Works
-
If the circle’s center lies inside the rectangle, the clamped coordinates will be the same as the center. The distance will be zero, which is always less than or equal to ( \text{radius}^2 ).
-
If the circle’s center is outside the rectangle, the clamped point is the nearest point on the rectangle boundary. Checking the distance from the circle’s center to this point tells us whether the circle reaches the rectangle.
Python Implementation
Java Implementation
Complexity Analysis
-
Time Complexity: O(1)
All operations (clamping, arithmetic calculations) are done in constant time. -
Space Complexity: O(1)
Only a few extra variables are used regardless of the input size.
Step-by-Step Walkthrough and Visual Example
-
Clamping the Circle’s Center:
- Suppose the circle’s center is at (xCenter, yCenter) = (1, 3) and the rectangle spans from (0, 0) to (2, 2).
- Clamp x: ( \text{closestX} = \max(0, \min(1, 2)) = 1 )
- Clamp y: ( \text{closestY} = \max(0, \min(3, 2)) = 2 )
- The closest point on the rectangle is (1, 2).
-
Distance Calculation:
- Compute ( \text{distanceSquared} = (1 - 1)^2 + (2 - 3)^2 = 0 + 1 = 1 ).
-
Comparison with the Radius:
- The radius is 1, so ( \text{radius}^2 = 1 ).
- Since ( \text{distanceSquared} ) (1) is equal to ( \text{radius}^2 ), the circle and rectangle overlap.
Common Mistakes
-
Incorrect Clamping:
Not clamping the circle’s center properly to the rectangle boundaries can lead to an incorrect closest point. -
Using Euclidean Distance Without Squaring:
To avoid dealing with square roots, always compare the squared distance with the squared radius. -
Ignoring Edge Cases:
Consider the scenario when the circle is completely inside the rectangle or when it just touches the rectangle’s boundary.
Edge Cases
-
Circle Inside Rectangle:
The clamped coordinates will equal the circle’s center, resulting in a zero distance which always satisfies the overlap condition. -
Rectangle Inside Circle:
Even if the rectangle is completely inside the circle, the method still correctly identifies that they overlap. -
Touching Boundaries:
When the circle exactly touches the rectangle (distance equals radius), the algorithm correctly returns true.
Alternative Variations
-
Different Shapes:
This approach can be adapted for problems involving other shapes by adjusting the way you compute the closest point. -
Non-Axis Aligned Rectangles:
For rotated rectangles, a more general approach using projection onto the rectangle’s axes is required.
Related Problems
GET YOUR FREE
Coding Questions Catalog
