Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers 3

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.

share|improve this answer
    
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
add comment

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.)

share|improve this answer
add comment

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.

share|improve this answer
    
All of them? :-( –  Richard Nov 2 '12 at 12:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.