1
$\begingroup$

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?

  • 0
    Don't worry Richard it is a common typo. (Removed that comment of mine)2012-11-03

3 Answers 3

2

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

1

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.

  • 0
    I'll give it a try, @fedja. Thanks :-)2012-11-02
0

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.

  • 0
    _All_ of them? :-(2012-11-02