We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Circle and Rectangle Overlapping

Number: 1501

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Determine if a given circle (defined by its radius and center coordinates) and an axis-aligned rectangle (defined by its bottom-left and top-right coordinates) overlap. In other words, check if there exists any point that lies inside both the circle and the rectangle.

Key Insights

  • The circle and rectangle overlap if the shortest distance from the circle's center to the rectangle is less than or equal to the radius.
  • The closest point on the rectangle to the circle's center can be found by "clamping" the circle's center coordinates to the rectangle’s bounds.
  • Calculating the squared Euclidean distance between the circle's center and this closest point avoids unnecessary square root operations.

Space and Time Complexity

Time Complexity: O(1) Space Complexity: O(1)

Solution

The idea is to compute the closest point on the rectangle to the circle's center. For the x-coordinate, if the center is between x1 and x2, use the center’s x; otherwise, use the nearer boundary. Similarly, do this for the y-coordinate. Once the closest point is identified, calculate the squared distance between this point and the actual circle center. If this distance is less than or equal to the square of the radius, then the circle overlaps with the rectangle.

Code Solutions

# Function to determine if circle and rectangle are overlapping
def check_overlap(radius, xCenter, yCenter, x1, y1, x2, y2):
    # Clamp the x coordinate of the circle center to the rectangle's x boundaries
    closest_x = xCenter if x1 <= xCenter <= x2 else (x1 if xCenter < x1 else x2)
    # Clamp the y coordinate of the circle center to the rectangle's y boundaries
    closest_y = yCenter if y1 <= yCenter <= y2 else (y1 if yCenter < y1 else y2)
    # Compute the squared distance from the circle center to the closest point
    distance_sq = (xCenter - closest_x) ** 2 + (yCenter - closest_y) ** 2
    # Check if the squared distance is less than or equal to the square of the radius
    return distance_sq <= radius ** 2

# Example usage:
print(check_overlap(1, 0, 0, 1, -1, 3, 1))  # Expected output: True
← Back to All Questions