NMinimize
Norm
EuclideanDistance
Element
Circle
BlockRandom
SeedRandom

Optimization
Mathematics
Geometry

Pack Circles in the Smallest Square

Find circles that fit inside a square without overlap and visualize the resulting layout

Open in Cloud
Download Notebook

Specify the number of circles and the radius of each circle:

In[1]:=

n=20;r=BlockRandom[RandomReal[{0.5,1.5},n],RandomSeeding234];

is the center and

is the radius of circle

, then the objective is to minimize

max

i=1,..,n

(||

∞

)

which defines the size of the smallest containing square. The objective can be transformed so as to minimize

where 𝑠 is the half-side length of the square,

-s<=||

∞

<=s,i=1,...,n

In[2]:=

objectiveConstraint=Table[-s≤Norm[c[i],Infinity]+r〚i〛≤s,{i,n}];

The circles must not overlap:

In[3]:=

nonOverlapConstraint=Table[Norm[c[i]-c[j]]≥r〚i〛+r〚j〛,{i,1,n},{j,i+1,n}];

Declare decision variables and their domains. Each circle center

𝑐

is a 2D real vector:

In[4]:=

vars=Append[Table[Element[c[i],Vectors[2,Reals]],{i,n}],Element[s,Reals]];

Optimize for the smallest containing square:

In[5]:=

res=NMinimize[{s,objectiveConstraint,nonOverlapConstraint},vars,Method"DifferenceOfConvex"]

Out[5]=

{4.82251,{c[1]{1.86079,1.65518},c[2]{4.0541,-4.0541},c[3]{4.00936,4.00936},c[4]{3.59736,-2.11356},c[5]{-4.17262,1.89291},c[6]{2.21501,3.83263},c[7]{-2.70348,4.24},c[8]{-1.09633,4.11118},c[9]{-2.16171,-1.98307},c[10]{0.270939,2.59453},c[11]{1.23013,-3.3684},c[12]{-3.55448,0.0773346},c[13]{3.98465,-0.0858889},c[14]{1.68573,-0.287259},c[15]{3.58977,2.00695},c[16]{-3.99734,3.68548},c[17]{-1.11471,-3.87721},c[18]{-3.71501,-3.71501},c[19]{-2.31699,2.41915},c[20]{-0.974313,0.228077},s4.82251}}

Substitute the optimizer’s solution into the graphics and draw all circles, along with the bounding square:

In[6]:=

Graphics[{Table[{RandomColor[],Disk[c[i],r〚i〛]},{i,n}],{FaceForm[None],EdgeForm[Black],Rectangle[{-s,-s},{s,s}]}}]/.res〚2〛

Out[6]=

Compute the fraction of the square covered by circles:

In[7]:=

Sum[Area[Disk[c[i],r〚i〛]],{i,n}]/Area[Rectangle[{-s,-s},{s,s}]]/.res〚2〛

Out[7]=

0.745045

Related Symbols

NMinimize
Norm
EuclideanDistance
Element
Circle
BlockRandom
SeedRandom

Publisher Information

Contributed by: Wolfram Staff

Wolfram Language Example Repository

Pack Circles in the Smallest Square

See Also

Publisher Information