{x}
blog image

Circle and Rectangle Overlapping

You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return true if the circle and rectangle are overlapped otherwise return false. In other words, check if there is any point (xi, yi) that belongs to the circle and the rectangle at the same time.

 

Example 1:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0).

Example 2:

Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Example 3:

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

 

Constraints:

  • 1 <= radius <= 2000
  • -104 <= xCenter, yCenter <= 104
  • -104 <= x1 < x2 <= 104
  • -104 <= y1 < y2 <= 104

Solution Explanation: Circle and Rectangle Overlapping

This problem asks whether a circle and a rectangle overlap. The solution uses a mathematical approach to efficiently determine this without iterating through all points.

Core Idea:

The solution leverages the fact that the shortest distance between a point and a line segment (or a rectangle's edge in this case) is along a perpendicular line. We find the closest point on the rectangle to the circle's center and check if that distance is less than or equal to the circle's radius.

Algorithm:

  1. Find Closest Point on Rectangle: For each axis (x and y), we determine the closest point on the rectangle's boundary to the circle's center. This involves simple comparisons:

    • If the circle's center's x-coordinate (xCenter) lies within the rectangle's x-range (x1 to x2), the closest x-coordinate is xCenter itself. Otherwise, it's either x1 or x2, whichever is closer. The same logic applies to the y-coordinate.

  2. Calculate Distance: We calculate the squared Euclidean distance between the circle's center and the closest point found in step 1. Squaring the distance avoids the computationally expensive square root operation and is sufficient for comparison.

  3. Check for Overlap: If the squared distance is less than or equal to the square of the circle's radius (radius * radius), the circle and rectangle overlap. Otherwise, they do not.

Time Complexity: O(1) - The algorithm performs a fixed number of comparisons and calculations regardless of the input size.

Space Complexity: O(1) - The algorithm uses a constant amount of extra space.

Code Explanation (Python):

class Solution:
    def checkOverlap(
        self,
        radius: int,
        xCenter: int,
        yCenter: int,
        x1: int,
        y1: int,
        x2: int,
        y2: int,
    ) -> bool:
        def f(i: int, j: int, k: int) -> int:
            if i <= k <= j:
                return 0
            return i - k if k < i else k - j
 
        a = f(x1, x2, xCenter)
        b = f(y1, y2, yCenter)
        return a * a + b * b <= radius * radius

The f function efficiently determines the distance between the circle's center and the closest edge of the rectangle along a single axis. It handles three cases:

  1. i <= k <= j: The circle's center is within the rectangle's range, distance is 0.
  2. k < i: The circle's center is to the left (or below) the rectangle, distance is i - k.
  3. k > j: The circle's center is to the right (or above) the rectangle, distance is k - j.

The main function then uses f to get the distances along the x and y axes, squares them, and sums them to get the squared distance. Finally, it checks if this squared distance is less than or equal to the squared radius.

The Java, C++, Go, and TypeScript code follow the same logic, simply using the syntax of their respective languages. They all have the same time and space complexity.