Formula for maximum square size so as not to intersect with an inscribed circle, given two points

Question

I have a geometrical dilemma. We have a set of circles that are each inscribed in equally-sized squares. Given the two circle-centres, I need to quickly calculate the maximum size I can give the squares such that a square will not intersect another square's circle. The circles always stay inscribed in the squares so the circle radius could also be calculated from the solution.

The quickest simplest approximation seems to me just to extend each square

min( abs(y - y'), abs(x - x') ) / 2

so the squares just touch. But in some cases, this still leaves room we could have grown the squares.

For example, here the squares cannot be enlarged as the squares would immediately intersect each other's inscribed circles:

But in this case, we could still grow the squares a bit:

Please keep in mind that I'd like some hints on how to find a formula for the maximum square size just given the two circle/square centres.

Any help would be appreciated, thanks!

Answer 1

For simplicity, assume one circle is around $(0,0)$, the other is around $(a,b)$ with $a,b\ge 0$ and the radius is $1$.

If the line at 45° slope through $(a,b)$ intersects the circle $x^2+y^2=1$ in the first quadrant, that determines the point where a vertex of the second square and first circle touch. If the intersection is outside the first quadrant or there is no intersection at all, an edge of the second square touches the first circle at $(1,0)$ or at $(0,1)$.

As our 45° line intersects the $x$-axis at $(a-b,0)$, the first case applies when $|a-b|\le 1$, the second when $a>b+1$, the third when $a<b-1$. We need additional computations only in the first case: The square vertex will be at $(a-t,b-t)$ such that $(a-t)^2+(b-t)^2=1$. Hence we solve $2t^2-2(a+b)t+a^2+b^2-1=0$ for its smaller solution, which is $$t_1=\frac{a+b-\sqrt{(a+b)^2-2(a^2+b^2-1)}}{2}=\frac{a+b-\sqrt{2-(a-b)^2}}{2} .$$ In summary, the side length of our squares is $$\begin{cases}2(a-1)&\text{if }a>b+1\\ 2(b-1)&\text{if }a<b-1\\ a+b-\sqrt{2-(a-b)^2}&\text{otherwise}\end{cases} $$

Answer 2

W.l.o.g. place one of the centers at the origin and let the coordinates of the other center be $(x,y)$. The near corner of the bounding box centered at $(x,y)$ lies on the circle at the origin when the common radius satisfies $$(x-r\operatorname{sgn}(x))^2+(y-r\operatorname{sgn}(y))^2=r^2.$$ You want the smaller of the two possible solutions, which is $$r=|x|+|y|-\sqrt{2|xy|}.$$ This will overshoot and cause a bounding box edge to cross the other circle when either of the intervals $[x-r,x+r]$ and $[y-r,y+r]$ has a zero crossing. If that’s the case, fall back to $r=\frac12\min(|x|,|y|)$.