Problem Breakdown
We need to determine whether there is any intersection between a given circle (defined by radius, x_center, y_center) and an axis-aligned rectangle (defined by bottom-left x1, y1 and top-right x2, y2).
- Inputs: Circle parameters
(radius, x_center, y_center); Rectangle boundaries(x1, y1, x2, y2). - Output: Boolean (
True) if they overlap or touch,Falseotherwise. - Overlap Definition: Intersection includes the interior of both shapes and their shared boundary (e.g., a corner touching the circle’s edge).
Intuition
The shortest distance from an arbitrary point (the circle’s center) to any region defined by axis-aligned boundaries is found along orthogonal projections onto those boundaries.
- Projection: Projecting the circle’s center
(x_center, y_center)onto the rectangle’s x-range[x1, x2]and y-range[y1, y2]yields a specific point on or inside the rectangle that is closest to the center. - Distance Check: If this “closest” point lies within distance
radiusfrom(x_center, y_center), then they overlap. - Optimization: By comparing squared distances (
dist_sq <= radius^2) instead of calculating Euclidean distance (using square roots), we avoid floating-point precision errors and improve performance slightly ( arithmetic operations).
Approach
- Clamp X-Coordinate: Determine the x-coordinate on the rectangle boundary closest to
x_center.- If
x_centeris less thanx1, clamp tox1. - If
x_centeris greater thanx2, clamp tox2. - Otherwise, keep
x_center(center lies within x-range).
- If
- Clamp Y-Coordinate: Repeat the logic for y-coordinates using
[y1, y2]. - Compute Squared Distance: Calculate .
- Compare: Return
Trueif squared distance , elseFalse.
Complexity Analysis
- Time Complexity: . The solution involves a constant number of comparisons and arithmetic operations regardless of input magnitude (within integer limits).
- Space Complexity: . Only primitive variables for coordinates are stored; no auxiliary data structures or recursion is used.
Solution
def is_overlapping(radius, x_center, y_center, x1, y1, x2, y2):
# Clamp x-coordinate: find projection of center onto [x1, x2]
if x_center < x1:
closest_x = x1
elif x_center > x2:
closest_x = x2
else:
closest_x = x_center
# Clamp y-coordinate: find projection of center onto [y1, y2]
if y_center < y1:
closest_y = y1
elif y_center > y2:
closest_y = y2
else:
closest_y = y_center
# Calculate squared distance between circle center and the clamped point
dist_sq = (x_center - closest_x)**2 + **(y_center - closest_y)2
return dist_sq <= radius**2