Domain 2MediumMEDIUM

Circle and Rectangle Overlapping

Determine if a circle overlaps with an axis-aligned rectangle by clamping the center to find the closest point and comparing squared distances.

Domain: geometry•Updated: 2026-09-15
#clamping#math#O(1)#O(1)

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, False otherwise.
  • 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.

  1. 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.
  2. Distance Check: If this “closest” point lies within distance radius from (x_center, y_center), then they overlap.
  3. 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 (O(1)O(1) arithmetic operations).

Approach

  1. Clamp X-Coordinate: Determine the x-coordinate on the rectangle boundary closest to x_center.
    • If x_center is less than x1, clamp to x1.
    • If x_center is greater than x2, clamp to x2.
    • Otherwise, keep x_center (center lies within x-range).
  2. Clamp Y-Coordinate: Repeat the logic for y-coordinates using [y1, y2].
  3. Compute Squared Distance: Calculate (xcenter−closest_x)2+(ycenter−closest_y)2(x_{center} - closest\_x)^2 + (y_{center} - closest\_y)^2.
  4. Compare: Return True if squared distance ≤radius2\le radius^2, else False.

Complexity Analysis

  • Time Complexity: O(1)O(1). The solution involves a constant number of comparisons and arithmetic operations regardless of input magnitude (within integer limits).
  • Space Complexity: O(1)O(1). 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