12
$\begingroup$

I have a set of circles of arbitrary radii: $r_1, r_2, r_3, ... r_n$.

I wish to arrange them around an inner circle so that they are all touching the perimeter of the inner circle, and do not overlap each other.

What I don't know how to do is figure out the inner radius $r_{inner}$.

I can figure out the angle each circle will use given an inner radius: $\theta_i = 2\sin^{-1} \frac{r_i}{r_i+r_{inner}}$, so I can test whether an inner radius is correct.

My first guess was to solve $2\pi = \sum_i (2\sin^{-1} \frac{r_i}{r_i+r_{inner}})$ for $r_{inner}$, but that's beyond my skills.

I also considered whether the sum of the diameters would equal the circumference of the circle, but that's a set of line segments rather than a smooth arc, and correcting that is also beyond me.

How do I figure out $r_{inner}$?

Numbers of circles around a circle is related, but assumes the circles are identical, which mine are not.

Improve this question
$\endgroup$
  • $\begingroup$ @l_e_a_h_c_i_m pointed out on twitter that the order of the circles matters - it will be different if it goes large-small-large vs large-middle-small. I'm most interested in the case where the circles are sorted large to small ($r_1$ largest), but I'm interested in the general case too. $\endgroup$ – dja Dec 5 '12 at 9:20
6
$\begingroup$

Using the cosine rule, the angle at the centre of the inner circle between lines through the centres of two adjacent touching circles is given by $$ \varphi(i,{i+1}) \;=\; \cos^{-1}\left(\frac{R^2+R r_i+R r_{i+1}-r_i r_{i+1}}{(R+r_i) (R+r_{i+1})}\right) $$ where I've used $R$ instead of $r_{inner}$ for simplicity.

So, we need $$ \qquad\qquad\qquad \qquad\qquad\qquad \sum\limits_{i=1}^n\varphi(i,{i+1})\;=\;2\pi \qquad\qquad\qquad \qquad\qquad\qquad(1) $$ where we consider $r_{n+1}=r_1$.

Using trigonometric identities, for a given $n$, it is possible to convert this into a very complex expression full of square roots, but there seems to be no easy way of solving the result in general (although for $n=3$ and $r_i=1,2,3$, we somewhat surprisingly get $R=\frac{6}{23}$).

Numerical solution is probably the best approach. (The diagram below was generated using Mathematica to solve numerically.)

Moreover, although this is a necessary condition, it is not sufficient in general because a sequence of small circles between two large circles may not fit tightly, causing the solution above to give an incorrect result (with the large circles overlapping):

$\qquad\qquad\qquad\qquad$ Overlapping circles

So for all $i\neq j$, for the above solution to be correct we also need $$ \varphi(i,j) \;\geqslant\; \sum_{k=i}^{j-1}\varphi(k,{k+1}) $$ with appropriate wrapping around of indexes if $i>j$. If this does not hold for some $i$ and $j$, then the correct solution for $R$ is obtained from $(1)$ by discarding circles $i+1,\ldots,j-1$. Due to the possibility of nested overlapping, the testing and discarding needs to be done iteratively, considering increasing values of $|i-j|$ in order.

Improve this answer
$\endgroup$
  • $\begingroup$ perhaps more aesthetic is $$ \mathrm{haversin}(\varphi(i,i+1))=\frac{r_ir_{i+1}}{(R+r_i)(R+r_{i+1})} $$ where $\mathrm{haversin}(\varphi)=\frac{1-\cos(\varphi)}{2}$ $\endgroup$ – robjohn♦ Dec 12 '12 at 12:48
  • $\begingroup$ Upvotes can be so arbitrary -- seven people upvoted this question, you wrote a good answer with a nice diagram, and noone upvotes the answer... $\endgroup$ – joriki Dec 12 '12 at 18:03
  • $\begingroup$ I can imagine situations where the "discard" rule is more complicated. For example, take circles $12345$, where $1$ and $5$ are two large circles flanking two much smaller circles ($2$ and $4$) flanking a single very small circle ($3$). If $234$ are placed "naively" ($2$ tangent to $3$ which is tangent to $4$), then they are close enough together that they allow $1$ and $5$ to overlap, suggesting that the correct answer is found by discarding $234$. But if $3$ is small enough, then $2$ and $4$ overlap, and when this is corrected (by discarding $3$), $234$ can no longer be discarded. $\endgroup$ – mjqxxxx Dec 12 '12 at 21:07
  • $\begingroup$ @mjqxxxx: Thanks; I've updated my answer. $\endgroup$ – David Bevan Dec 13 '12 at 10:02
  • $\begingroup$ So ultimately it's a matter of solving numerically... Fair enough. I'll test that out and then accept it in the next couple of days. $\endgroup$ – dja Dec 14 '12 at 2:13
0
$\begingroup$

In the following diagram, $R$ is the radius of the center circle and $r_1$ and $r_2$ are two of the surrounding circles.

$\hspace{3cm}$enter image description here

The Law of Cosines says $$ (r_1+r_2)^2=(R+r_1)^2+(R+r_2)^2-2(R+r_1)(R+r_2)\cos(\varphi_{12})\tag{1} $$ which implies that $$ \begin{align} \cos(\varphi_{12}) &=\frac{(R+r_1)^2+(R+r_2)^2-(r_1+r_2)^2}{2(R+r_1)(R+r_2)}\\[6pt] &=\frac{(R+r_1)(R+r_2)-2r_1r_2}{(R+r_1)(R+r_2)}\\[6pt] &=1-2\frac{r_1}{R+r_1}\frac{r_2}{R+r_2}\tag{2} \end{align} $$ We need to find $R$ so that $$ \pi=\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{R+r_i}\frac{r_{i+1}}{R+r_{i+1}}\right)\tag{3} $$ where $r_{n+1}=r_1$. To this end, define $$ f(x)=\pi-\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{x+r_i}\frac{r_{i+1}}{x+r_{i+1}}\right)\tag{4} $$ and then $$ f'(x)=\sum_{i=1}^n\frac{\frac1{x+r_i}+\frac1{x+r_{i+1}}} {\sqrt{\frac{x+r_i}{r_i}\frac{x+r_{i+1}}{r_{i+1}}-1}}\tag{5} $$ So we can use Newton's method to get the recursion $$ x_{k+1}=x_k- \frac{\displaystyle\pi-\sum_{i=1}^n\cos^{-1}\left(1-2\frac{r_i}{x_k+r_i}\frac{r_{i+1}}{x_k+r_{i+1}}\right)} {\displaystyle\sum_{i=1}^n\frac{\frac1{x_k+r_i}+\frac1{x_k+r_{i+1}}} {\sqrt{\frac{x_k+r_i}{r_i}\frac{x_k+r_{i+1}}{r_{i+1}}-1}}} $$

Improve this answer
$\endgroup$
  • $\begingroup$ This seems to be requiring that the angular ranges of the circles don't overlap. I think the intended requirement was only that the circles themselves don't overlap, which doesn't preclude their angular ranges from overlapping. $\endgroup$ – joriki Dec 12 '12 at 12:16
  • $\begingroup$ @joriki: I adjusted things $\endgroup$ – robjohn♦ Dec 12 '12 at 19:19
  • $\begingroup$ Much better, but you don't mention the problem of large circles overlapping above small circles -- see David's answer. $\endgroup$ – joriki Dec 12 '12 at 20:16
  • $\begingroup$ @joriki: nor do I address the issue of whether $R$ changes for differing orders of the outer circles. Soddy's theorem would be useful for detecting the overlaps. I will add something about using Soddy's theorem. $\endgroup$ – robjohn♦ Dec 12 '12 at 20:26
  • $\begingroup$ This appears to be very similar to the other answer: apart from different simplification of the angle and some extra solving of Newton's method, is there any real difference between the two? $\endgroup$ – dja Dec 14 '12 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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