# Dense packing of disks with different radii

1. Let's consider a disk ($$D_{1}$$) whose center position is randomly generated, but the radius is fixed at $$r_{1}$$.

2. A second disk ($$D_{2}$$) of fixed radius $$r_{2}$$ (with $$r_{2} < r_{1}$$) is randomly generated such that it is tangent to $$D_{1}$$.

3. A third disk ($$D_{3}$$) of fixed radius $$r_{3}$$ (with $$r_{3} < r_{2}$$) is randomly generated such that $$D_{3}$$ is tangent to $$D_{1}$$ (and not necessarily to $$D_{2}$$). If there is no space for this (i.e. the disks shall not overlap), then the center position is generated such that $$D_{3}$$ is tangent to $$D_{2}$$.

4. A fourth disk ($$D_{4}$$) of fixed radius $$r_{4}$$ (with $$r_{4} < r_{3}$$) is generated such that $$D_{4}$$ is tangent to $$D_{1}$$. If there is no space for this, then the center position is generated such that $$D_{4}$$ is tangent to $$D_{2}$$. If there is no space, then the center position is generated such that $$D_{4}$$ is tangent to $$D_{3}$$.

...

1. Generally, the $$n$$-th disk ($$D_{n}$$) of fixed radius $$r_{n}$$ (with $$r_{n} < r_{n-1} < \cdots < r_{2} < r_{1}$$) is generated such that it shall be tangent to $$D_{1}$$. If there is no space, then it shall be tangent to $$D_{2}$$, and so on until eventually is tangent to $$D_{n-1}$$.

Thus, given a list of radii $$r_{i}$$ with $$i=1,\cdots, n$$ such that $$r_{n} < r_{n-1} < \cdots < r_{2} < r_{1}$$, how to efficiently generate in Mathematica the non-overalping set of disks described by the above algorithm for large values of $$n$$ (at least higher than $$10^{4}$$)?

I found a related approach here at the answer provided by Istvan Zachar and probably the functions randomPoint and distance he defined, could be useful for the alghoritm presented here.

A second related algorithm can be found here at the answer provided by Simon Woods where he uses Mathematica built-in optimisation tools based on graphs. However, besides of the different algorithm used, it seems that such approach can not handle large graphs.

Update: I have tried the following code:

(*generate the list of radii*)
r = {1, 0.7, 0.5, 0.3}

(*generate disk D1 (black color, see figure below). Center is fixed at {0,0} and radius at 1*)
D1 = Disk[{0, 0}, r[[1]]];

(*generate the sample space (blue dashed line) from which one can choose the radius of disk D2 (blue color)*)
samplespace1 = RandomPoint[Circle[{0, 0}, r[[1]] + r[[2]]], {10000}];

(*choose a random point from samplespace1 and assign it as a center coordinate of disk D2*)
c1 = RandomChoice[samplespace1];
D2 = Disk[c1, r[[2]]];

(*generate the sample space (dashed green line) from which one can choose the the radius of disk D3 (green color).
In order to avoid overlapping of D2 and D3, only those points are selected for which the EuclideanDistance is higher than the sum of their radii*)
samplespace2 =
Select[RandomPoint[Circle[{0, 0}, r[[1]] + r[[3]]], {10}],
Sqrt[(c1[[1]] - #[[1]])^2 + (c1[[2]] - #[[2]])^2] >= (r[[2]] +
r[[3]]) &];

(*Finally disk D3 is generated as:*)
D3 = Disk[RandomChoice[samplespace2], r[[3]]];

(*The results are shown graphically here:*)


By continuing in this way, I think is possible to add few more disks, and I do no think this is an efficient way to write good code in Mathematica. Thus, It would be nice to have a fast and compact code (even if cryptic) which takes the input the list of radii and the number of disks, and plot them according to the algorithm described above.

• What code have you tried? An example of your code would go a long way to helping us solve your problem. Sep 23 '21 at 11:07
• @creidhne, I have updated the post with the code I tried. Sep 23 '21 at 14:38