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.

$\endgroup$
1
  • $\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
    Commented Dec 5, 2012 at 9:20

2 Answers 2

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.

$\endgroup$
6
  • $\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
    Commented Dec 12, 2012 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
    Commented Dec 12, 2012 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
    Commented Dec 12, 2012 at 21:07
  • $\begingroup$ @mjqxxxx: Thanks; I've updated my answer. $\endgroup$ Commented Dec 13, 2012 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
    Commented Dec 14, 2012 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}}} $$

$\endgroup$
5
  • $\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
    Commented Dec 12, 2012 at 12:16
  • $\begingroup$ @joriki: I adjusted things $\endgroup$
    – robjohn
    Commented Dec 12, 2012 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
    Commented Dec 12, 2012 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
    Commented Dec 12, 2012 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
    Commented Dec 14, 2012 at 2:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .