How to fill random spaces with random circles in tikz?

Question

Does anybody know how to efficiently draw either one of the following pictures in tikz?

Specifically the "Well Graded" interests me, as one would have to fill random spaces between circles - with different random smaller circles (of multiple sizes).

 \documentclass{standalone}
 % Possibly some code here

 \begin{document}
 % Possibly some code here

 \begin{tikzpicture}
 % Definitely some code here
 \end{tikzpicture}

 \end{document}

Thanks for your help and interest.

Answer 1

Opening notes

There is a lot of interesting examples created in the D3js library, see e.g. mbostock's blocks or this gallery. It's quite inspiring. Those examples are fast and we could get SVG files at a JavaScript level, if needed (easily convertible to PDF, TikZ etc.).

Let me focus on these types of graphs. I believe these examples belong to a field of collision detection with/out reserve distance of the individual circles/objects.

In the following experiments, I'm testing spiral as it is used in creating wordclouds, see Jason Davies's webpage. For drawing/emulating a spiral, we need a fixed point, an addition to an angle and a addition to a distance from the fixed point. Next thing we need is a database of already defined circles. I'm using Lua and its data table.

I separated examples to a series of individual files for easy manipulation and experimenting. Each Lua file generates own TeX file which is loaded to a main TeX file at the end.

Poorly graded type, first variant

I convert an angle and a distance to a point. Nearby this point I randomly select another point which is a candidate for the centre point of the new circle. We test if there is no collision with already created circles, if there is not (a change in yes variable), we add that candidate to a Lua table. After we reach requested number of circles (steps), we stop an algorithm and the snippet generates a TeX file.

-- Poorly Graded type, mal-circles-a.lua

io.write("Creating a poorly graded type...    ")
steps=70 -- number of circles
angles=25 -- angle of the spiral
distances=.01 -- distance from the center of the spiral

circles={ } -- Lua table with (x,y),r of the circles
r=1.8 -- diameter of the circle
dx=2.5 -- a window for random number generation (x axis)
dy=2.5 -- the same for the y axis

-- a distance between two points (circle centers)
function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end


for step=1,steps do -- how many circles do we want
angle=0 -- a starting angle for each new spiral
distance=0 -- a starting distance for each new spiral

while true do -- do spiral as long a circle cannot be inserted
angle=angle+angles -- increase an angle
distance=distance+distances -- insce a distance
y=distance*math.sin(math.rad(angle)) -- convert an angle to a point
x=distance*math.cos(math.rad(angle)) -- the same for the y axis

newx=math.random()*dx-dx/2+x -- find a new possible location nearby spiral
newy=math.random()*dy-dy/2+y -- the same for the y axis
yes=1
for l=1,#circles do -- test if there is no intersection among circles
d=dist(circles[l][1],circles[l][2],newx,newy)
m=circles[l][3]/2+.05*circles[l][4]+r/2 -- there is a reserse
if d<m then yes=nil; break end -- circles intersect! skip this try
end -- for, l

if yes then table.insert(circles, {newx,newy,r}); break end -- circles don't intersect, use that new one
end -- while, spin spiral as long as it is necessary
end -- no. of circles we need

-- generate a TeX file for later loading
writeme=io.open("mal-a.tex","w")
for circle=1,#circles do
writeme:write("\\node[c, minimum width="..circles[circle][5].."cm] at ("..circles[circle][6]..", "..circles[circle][7]..") {};\n")
end 
writeme:close()
print("I'm done!")

Poorly graded type, the second variant

I like an alternative with touching circles and sort of gravity effect (to be as close as possible to the centre point). I tried quite time-consuming algorithm, but it works. The algorithm tries to draw many circles around existing ones and picks up only one which is closest to the centre point of the graph (zero, zero) and has no intersection point with other circles. (Maybe I could pick up more points after sorting them by distance? But they are intersecting themselves...)

In case we need exact touch of the circles, we would need to do correction of linewidth/2. There is a faster way, at a TikZ level we can set draw=none, fill=black.

-- Touching circles type, mal-circles-a-alt.lua

io.write("Creating a touching circles type... ")
steps=150
d0=1.0
steps=steps-1
coef=0.3
circles={ {0,0,d0+coef*math.random()} }
--print("")

function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end


for step=1,steps do -- number of touching circles to be generated
--print(step)
r=d0+coef*math.random() -- to be randomized;
tosaver=r; 
dmin=nil

for l=1,#circles do
   m=circles[l][9]
   distance=(r+m)/2
   --print(l,distance)

for angle=0,360,5 do
y=distance*math.sin(math.rad(angle))
x=distance*math.cos(math.rad(angle))
newx=circles[l][10]+x
newy=circles[l][11]+y

crossing=nil
for k=1,#circles do
   mnew=circles[k][12]
   distancenew=(r+mnew)/2
  d=dist(circles[k][13],circles[k][14],newx,newy)
  --if step==steps then print(l,k,d,distance,newx,newy) end
  if d<distancenew then crossing=true --do nothing; circles intersect
  end
end -- k

if not crossing then
     value=dist(newx,newy,0,0)
     if not dmin or dmin>value then tosavex=newx; tosavey=newy; 
     --print(step,l,angle,dmin,value);  --newx,newy,
     dmin=value end
end     

--m=circles[l][15]/2+.25*circles[l][16]+r/2
 -- if step>21 then m=circles[l][17]/2+r/2 end
--if d<m then yes=nil; break end
end -- for, angle

--if yes then table.insert(circles, {x,y,r}); break end
end -- for, l

--print(tosavex,tosavey,r)
if dmin then table.insert(circles, {tosavex, tosavey, tosaver}) end
--[[for circle=1,#circles do
print(circles[circle][18], circles[circle][19], circles[circle][20])
end]]

end -- for, steps, no . of circles


-- Printing results to the TeX document...
writeme=io.open("mal-a-alt.tex","w")
for circle=1,#circles do
towrite="\\node[c, minimum width="..circles[circle][21].."cm] at ("..circles[circle][22]..", "..circles[circle][23]..") {};\n" -- "..circle.."
--print(towrite)
writeme:write(towrite)
end 
writeme:close()
print("I'm done!")

Gap graded type

Once we get so far, we can start changing the parameters during the run of the algorithm. In the following example, I change the diameter of the remaining circles. A small trick is that the snippet sets a reserve distance (25% of the diameter) for the big ones (m variable) which is set to zero for the smaller ones.

-- Gap Graded type, mal-circles-b.lua

io.write("Creating a gap graded type...       ")
steps=600
bigones=20
angles=25
distances=.02

circles={ }
rfix=1.8
r=rfix
dx=2.5
dy=2.5

function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end

for step=1,steps do
--print(step,angle,distance)
--tex.print("\\node at ("..angle..":"..distance..") {a};")
--print(x,y)
--tex.print("\\node at ("..x..","..y..") {b};")
angle=0
distance=0
if step>bigones then r=.3 end -- .4*math.random()*rfix+
--if step>100 then r=.2*math.random()*rfix+.2 end

while true do
angle=angle+angles
distance=distance+distances
y=distance*math.sin(math.rad(angle))
x=distance*math.cos(math.rad(angle))

newx=math.random()*dx-dx/2+x
newy=math.random()*dy-dy/2+y
yes=1
for l=1,#circles do
d=dist(circles[l][25],circles[l][26],newx,newy)
m=circles[l][27]/2+.25*circles[l][28]+r/2
if step>bigones then m=circles[l][29]/2+r/2 end
if d<m then yes=nil; break end
end -- for, l

if yes then table.insert(circles, {newx,newy,r}); break end
end -- while
end -- No. of circles

writeme=io.open("mal-b.tex","w")
for circle=1,#circles do
writeme:write("\\node[c, minimum width="..circles[circle][30].."cm] at ("..circles[circle][31]..", "..circles[circle][32]..") {};\n")
end 
writeme:close()
print("I'm done!")

Well graded type

Once we know these tricks, we can change other parameters. In the next example, I change size of the circles randomly. I set three levels, the biggest ones (circles 1-20), the middle ones in size (circles no. 21-100) and small ones (100+). The second and the third groups can have common sizes. The reason is I'm not setting minimum amount when dealing with math.random(). We cannot recognize it until we use some styles, each for separate group.

-- Well Graded type, mal-circles-c.lua

io.write("Creating a well graded type...      ")
steps=555
angles=25
distances=.01

circles={ }
rfix=1.8
r=rfix
dx=2.5
dy=2.5

function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end

for step=1,steps do
--print(step,angle,distance)
--tex.print("\\node at ("..angle..":"..distance..") {a};")
--print(x,y)
--tex.print("\\node at ("..x..","..y..") {b};")
angle=0
distance=0
if step>20 then r=.4*math.random()*rfix+.2 end
if step>100 then r=.2*math.random()*rfix+.2 end

while true do
angle=angle+angles
distance=distance+distances
y=distance*math.sin(math.rad(angle))
x=distance*math.cos(math.rad(angle))

newx=math.random()*dx-dx/2+x
newy=math.random()*dy-dy/2+y
yes=1
for l=1,#circles do
d=dist(circles[l][34],circles[l][35],newx,newy)
m=circles[l][36]/2+r/2 -- +.25*circles[l][37]
 -- if step>21 then m=circles[l][38]/2+r/2 end
if d<m then yes=nil; break end
end -- for, l

if yes then table.insert(circles, {newx,newy,r}); break end
end -- while
end -- No. of circles

writeme=io.open("mal-c.tex","w")
for circle=1,#circles do
writeme:write("\\node[c, minimum width="..circles[circle][39].."cm] at ("..circles[circle][40]..", "..circles[circle][41]..") {};\n")
end 
writeme:close()
print("I'm done!")

Island type, a variant without colors

When we start changing distance reserve, different types in size, we can get different pictures. I call this one an island type. Each circle has its own distance reserve, sizes change randomly in the predefined groups as in the previous example. This is what we get.

-- Island type without colors, mal-circles-d.lua

io.write("Creating an island type...          ")
steps=555
angles=25
distances=.01

circles={ }
rfix=1.8
r=rfix
dx=2.5
dy=2.5

function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end

for step=1,steps do
--print(step,angle,distance)
--tex.print("\\node at ("..angle..":"..distance..") {a};")
--print(x,y)
--tex.print("\\node at ("..x..","..y..") {b};")
angle=0
distance=0
if step>20 then r=.4*math.random()*rfix+.2 end
if step>100 then r=.2*math.random()*rfix+.2 end

while true do
angle=angle+angles
distance=distance+distances
y=distance*math.sin(math.rad(angle))
x=distance*math.cos(math.rad(angle))

newx=math.random()*dx-dx/2+x
newy=math.random()*dy-dy/2+y
yes=1
for l=1,#circles do
d=dist(circles[l][43],circles[l][44],newx,newy)
m=circles[l][45]/2+.25*circles[l][46]+r/2
 -- if step>21 then m=circles[l][47]/2+r/2 end
if d<m then yes=nil; break end
end -- for, l

if yes then table.insert(circles, {newx,newy,r}); break end
end -- while
end -- No. of circles

writeme=io.open("mal-d.tex","w")
for circle=1,#circles do
writeme:write("\\node[c, minimum width="..circles[circle][48].."cm] at ("..circles[circle][49]..", "..circles[circle][50]..") {};\n")
end 
writeme:close()
print("I'm done!")

Island type, a variant with colors

We can change different things, in the last example I am changing a style. It differs in circle size (less than 0.45 in diameter, bigger then 0.45 and less than 1 and bigger than 1). As a proof, I prepared a couple of styles at a TeX/TikZ level.

-- Island type with colors, mal-circles-d-alt.lua

io.write("Creating an island type in color... ")
steps=555
angles=25
distances=.01

circles={ }
rfix=1.8
r=rfix
dx=2.5
dy=2.5

function dist(xz,yz,nx,ny)
return math.sqrt( (nx-xz)^2 + (ny-yz)^2 )
end

for step=1,steps do
--print(step,angle,distance)
--tex.print("\\node at ("..angle..":"..distance..") {a};")
--print(x,y)
--tex.print("\\node at ("..x..","..y..") {b};")
angle=0
distance=0
malstyle="style1"
if step>20 then r=.4*math.random()*rfix+.2 end
if step>100 then r=.2*math.random()*rfix+.2 end
if r<1 then malstyle="style2" end
if r<0.45 then malstyle="style3" end

while true do
angle=angle+angles
distance=distance+distances
y=distance*math.sin(math.rad(angle))
x=distance*math.cos(math.rad(angle))

newx=math.random()*dx-dx/2+x
newy=math.random()*dy-dy/2+y
yes=1
for l=1,#circles do
d=dist(circles[l][52],circles[l][53],newx,newy)
m=circles[l][54]/2+.25*circles[l][55]+r/2
 -- if step>21 then m=circles[l][56]/2+r/2 end
if d<m then yes=nil; break end
end -- for, l

if yes then table.insert(circles, {newx,newy,r,malstyle}); break end
end -- while
end -- No. of circles

writeme=io.open("mal-d-alt.tex","w")
for circle=1,#circles do
writeme:write("\\node[c, minimum width="..circles[circle][57].."cm, "..circles[circle][58].."] at ("..circles[circle][59]..", "..circles[circle][60]..") {};\n")
end 
writeme:close()
print("I'm done!")

Closing notes: using the Lua snippets

After saving snippets to separate Lua files, we run Lua outside the TeX engines as follows (quite slow is the second snippet):

texlua mal-circles-a.lua
texlua mal-circles-a-alt.lua
texlua mal-circles-b.lua
texlua mal-circles-c.lua
texlua mal-circles-d.lua
texlua mal-circles-d-alt.lua

If everything is working as should be, we'll spot several messages in the terminal:

Creating a poorly graded type...    I'm done!
Creating a touching circles type... I'm done!
Creating a gap graded type...       I'm done!
Creating a well graded type...      I'm done!
Creating an island type...          I'm done!
Creating an island type in color... I'm done!

These snippets generate a series of TeX files which we load by the main TeX file. We run any LaTeX engine, e.g. lualatex mal-circles.tex.

% *latex mal-circles.tex
\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage{tikz}
% small improvements to the mirror
\addtolength{\hoffset}{-1in}
\paperwidth=1.4\paperwidth
\pdfpagewidth=\paperwidth
\textwidth=2\textwidth

\begin{document}
% preparing styles for nodes
\tikzset{inner sep=0pt, outer sep=0pt, 
   every node/.style={circle, draw=black, thick}, 
   c/.style={fill=none},
   style1/.style={fill=green, line width=1pt},
   style2/.style={fill=red},
   style3/.style={fill=yellow},
   }

% definition for loading generated TeX files
\def\malinput#1 {%
\newpage % one example per page
\begin{tikzpicture}
%\draw (-5,-2) grid (5,2); % fast grid drawing, if needed
\input #1.tex % loading a generated file
\end{tikzpicture}
}

\malinput mal-a
\malinput mal-a-alt
\malinput mal-b
\malinput mal-c
\malinput mal-d
\malinput mal-d-alt
\end{document}