September 19Medium

Circle and rectangle overlapping

Math
Geometry

Problem

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.

Solution

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        def get_dist(x, y):
            return sqrt((x - xCenter) ** 2 + (y - yCenter) ** 2)
        # circle equation: (x - xCenter)^2 + (y - yCenter)^2 = r^2
        # rectangle equation: x = x1 | x = x2 | y = y1 | y = y2
        # if they intersect:
        # solve for possible x1, x2 -> check if y is in range (y1 to y2)
        # solve for possible y1, y2 -> check if x is in range (x1 to x2)

        # if they don't intersect, either the rectangle in the circled:
        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:
            return True

        # or the other way around:
        if get_dist(x1, y1) < radius or get_dist(x1, y2) < radius or get_dist(x2, y1) < radius or get_dist(x2, y2) < radius:
            return True

        def solve(y, xCenter, yCenter):
            # x^2 - 2x*xCenter - r^2 + (y-yCenter)^2 + xCenter ^ 2 = 0
            # D = 4xCenter ^ 2 - 2k
            # x = (2xCenter +- sqrt(D)) / 2
            k = -(radius**2) + (y - yCenter) ** 2 + xCenter ** 2
            D = 4 * (xCenter**2) - 4*k
            if D < 0:
                return None, None
            return (2*xCenter + sqrt(D)) / 2, (2*xCenter - sqrt(D)) / 2

        for sol in *solve(y1, xCenter, yCenter), *solve(y2, xCenter, yCenter):
            if sol is not None and x1 <= sol <= x2:
                return True

        for sol in *solve(x1, yCenter, xCenter), *solve(x2, yCenter, xCenter):
            if sol is not None and y1 <= sol <= y2:
                return True
 
        return False