Circle and Rectangle Overlapping

Circle and Rectangle Overlapping

What is this problem about?

This "Medium" geometry problem asks you to determine if a circle and an axis-aligned rectangle overlap. You are given the radius and center coordinates of the circle, as well as the coordinates of the bottom-left and top-right corners of the rectangle. Overlapping includes cases where the circle is inside the rectangle, the rectangle is inside the circle, or they just touch.

Why is this asked in interviews?

Companies like Microsoft and Google use this to test your ability to handle geometric logic and edge cases. It requires you to simplify a continuous problem (all points in a circle) to a discrete comparison. It evaluations your skill in finding the "nearest point" on a shape and using the distance formula.

Algorithmic pattern used

The primary pattern is the Nearest Point on Rectangle logic. To check if a circle overlaps with a rectangle, you find the point $(x, y)$ on the rectangle that is closest to the circle's center $(xCenter, yCenter)$. If the distance from this closest point to the center is less than or equal to the radius, they overlap. The closest $x$ is max(x1, min(xCenter, x2)) and the closest $y$ is max(y1, min(yCenter, y2)).

Example explanation

Rectangle: [0, 0] to [4, 4]. Circle: Center (5, 2), Radius 2.

1. Find closest $x$ on rectangle to $xCenter=5$. min(5, 4) = 4, max(0, 4) = 4. Closest $x = 4$.
2. Find closest $y$ on rectangle to $yCenter=2$. min(2, 4) = 2, max(0, 2) = 2. Closest $y = 2$.
3. Closest point is (4, 2).
4. Distance from (4, 2) to center (5, 2) is 1.
5. $1 \le$ Radius (2). Result: True.

Common mistakes candidates make

A common error is trying to check only the corners of the rectangle. A circle could overlap with the side of a rectangle without covering any of its corners. Another mistake is using the square root in the distance formula, which can lead to precision errors; it's always better to compare dx^2 + dy^2 to radius^2.

Interview preparation tip

For any "overlap" or "collision" problem between a circle and another shape, the most robust method is finding the "shortest distance" from the circle center to the shape.