# Do an axis-aligned rectangle and a circle overlap?

Given a circle of radius $r$ located at $(x_c, y_c)$ and a rectangle defined by the points $(x_l, y_l), (x_l+w, y_l+h)$ is there a way to determine whether the the two overlap? The square's edges are parallel to the $x$ and $y$ axes.

I am thinking that overlap will occur if one of the rectangle's corners is contained in the circle or one of the circle's circumference points at ($n\frac{\pi}{2}, n=\{0,1,2,3\}$ radians) is contained in the rectangle. Is this true?

EDIT: One answer has pointed out a case not covered by the above which is resolved by also checking whether the center of the circle is contained.

Is there a method which doesn't involve checking all points on the circle's circumference?

-
Oh, do I feel foolish, @AD.! I have repaired the question. – Richard Nov 2 '12 at 15:00
Don't worry Richard it is a common typo. (Removed that comment of mine) – AD. Nov 3 '12 at 7:00

Corners are certainly not enough but, fortunately, the life is not that bad. The overlap occurs exactly in the following cases, each of which is easy to check:

1) The center of the circle lies in the rectangle

2) One of the vertices lies in the circle

3) The projection of the center of the circle to one of the sides lies on the corresponding side (not on its extension) and in the circle simultaneously (since the sides of the rectangle are parallel to the axis, projecting to them is totally trivial).

Thus, you have to check 9 points in the worst case scenario.

-
Thank you, fedja, #3 is cunning. Do you happen to know if there is a proof of this anywhere? – Richard Nov 2 '12 at 15:02
I doubt anyone would bother to write it down but you can easily figure it out yourself if you realize that the domains overlap if and only if the center of the circle lies in the $r$-neighborhood of the rectangle and bother to draw the picture of that neighborhood. This, by the way, will give you an idea how to optimize the checking even more :). – fedja Nov 2 '12 at 16:32
I'll give it a try, @fedja. Thanks :-) – Richard Nov 2 '12 at 16:39

This sort of problem has a simple solution that requires no case analysis at all! The point on the rectangle closest to the center of the circle is at coordinates \begin{align} x^* &= \operatorname{clamp}(x_c, [x_l, x_l+w]),\\ y^* &= \operatorname{clamp}(y_c, [y_l, y_l+h]),\\ \end{align} where $\operatorname{clamp}(x, [a,b]) = \min(\max(x,a),b)$. The circle and the rectangle overlap if the distance between $(x_c,y_c)$ and $(x^*,y^*)$ is not more than the radius of the circle.

(I'm assuming you care about filled circles and filled rectangles, so you count them as overlapping even if one is entirely inside the other and their boundaries don't meet.)

-

No. Imagine a square and enlarge its incircle a bit. They will overlap, but wouldn't satisfy neither of your requirement.

Unfortunately, you have to check all points of the circle. Or, rather, solve the arising inequalities (I assume you are talking about filled idoms): \begin{align} (x-x_c)^2+(y-y_c)^2 & \le r \\ x\in [x_l,x_l+w]\ &\quad y\in [y_l,y_l+h] \end{align} Or.. Perhaps it is enough to add to your requirements, that the center of the circle is contained in the rectangle.

-
All of them? :-( – Richard Nov 2 '12 at 12:36