# tikz: Distribute evenly and randomly circles

I want to fill a part of a picture with more or less evenly and randomly distributed circles which should not overlap. It would be okay if circles are only partly inside the shape. The density should be like what you see on this page http://zoada.com/html5/brute.html with values 80-100. (But I do not need so many circles, 30 should be enough, I could repeat the pattern).

I cannot use a grid and "wobble" the circles a bit: The circles are too large and it simply does not look randomly.

Currently I am thinking about a random attempt: Get some random point, measure its distance to existing circles, either paint or throw the point away. Try 100 times and hope that you get the right number of circles (and that it does not take too long). But perhaps someone has a better idea.

The example draws the circles simply manually:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{backgrounds}
\begin{document}

\draw[red](0,0) rectangle (5,5);
\draw (1,1) circle;
\draw (2.3,1.1) circle ;
\draw (4.5,0.8) circle ;
\draw (5.1,1.8) circle ;
\draw (0.4,3.3) circle ;
\draw (2.1,2.8) circle ;
\draw (3.8,3.5) circle ;
\draw (4.8,4.2) circle ;
\draw (0.8,4.9) circle ;
\draw (2.1,4.1) circle ;
\draw (3.8,2.0) circle ;
\draw (3.5,0.6) circle ;
\draw (3.0,5.0) circle ;
\draw (4.1,5.1) circle ;
\draw (0.9,2.1) circle ;
\end{tikzpicture}
\end{document}

-
I haven't thought so deep about this, but when you say Try 100 time and hope that you get the right number of circles, you can add a counter and get EXACTLY the number of circles you want. Anyway, (may be) you don't need to get a new different random distribution anytime you compile the document, so you could do the math with a program and write in the document just the numbers (previously calculated). –  Manuel Dec 18 '12 at 13:15
@Manuel: With hope I meant more "that I get a pleasing looking result with enough and not to much circles". I don't have an idea yet how many circle would look like I want it to look. –  Ulrike Fischer Dec 18 '12 at 13:35
Is this problem well defined? It seems to me that you can implement the constraint that the disks are not allowed to overlap in several ways, which are not equivalent. –  Jesper Ipsen Dec 18 '12 at 14:20
@Ipsen: I don't care much why the disks don't overlap. There is no mathematical background or model behind the disks. They simply should look pleasingly spread out without some obvious order. –  Ulrike Fischer Dec 18 '12 at 14:29

Here's a macro that implements what you described. It takes four arguments: The width and height of the rectangle to be filled, the radius of the circles, and the number of attempts.

For each attempt, a random position is generated. The distances between this position and all existing circles are calculated, and if there's a collision, no circle is drawn. If the circle does not collide, it is drawn, and its coordinates are added to the list of existing circles.

This approach is far from efficient, but it works:

\fillrandomly{3}{2}{0.2}{50}


\pgfmathsetseed{2}
\fillrandomly{5}{5}{0.5}{300}


\documentclass{article}
\usepackage{tikz}

\begin{document}
\def\xlist{4}
\def\ylist{4}

\newcommand{\fillrandomly}[4]{
\pgfmathsetmacro\diameter{#3*2}
\draw (0,0) rectangle (#1,#2);
\foreach \i in {1,...,#4}{
\pgfmathsetmacro\x{rnd*#1}
\pgfmathsetmacro\y{rnd*#2}
\xdef\collision{0}
\foreach \element [count=\i] in \xlist{
\pgfmathtruncatemacro\j{\i-1}
\pgfmathsetmacro\checkdistance{ sqrt( ({\xlist}[\j]-(\x))^2 + ({\ylist}[\j]-(\y))^2 ) }
\ifdim\checkdistance pt<\diameter pt
\xdef\collision{1}
\breakforeach
\fi
}
\ifnum\collision=0
\xdef\xlist{\xlist,\x}
\xdef\ylist{\ylist,\y}
\draw [red, thick] (\x,\y) circle [radius=#3];
\fi

}
}

\begin{tikzpicture}
\pgfmathsetseed{2}
\fillrandomly{5}{5}{0.5}{300}

\end{tikzpicture}
\end{document}

-
Regarding the efficiency, I found a paper from 2002 on this problem and the algorithm for generating the points was essentially this one: generate the points and then let them "compete". –  Loop Space Dec 18 '12 at 15:37
@AndrewStacey: Interesting! Do you have the DOI for that paper? –  Jake Dec 18 '12 at 15:38
Perfect. It is not very fast, but I can export the lists and reuse them. I will also add a bit distance between the circles so that don't touch. Thank you! –  Ulrike Fischer Dec 18 '12 at 15:47
doi:10.1239/aap/1037990950 –  Loop Space Dec 18 '12 at 16:03
@AndrewStacey: Oh no, it's actual maths! I was hoping for an easy-to-digest explanation with diagrams and example code... Well then, I look forward to your implementation! –  Jake Dec 18 '12 at 16:10

Here's a different variation. The idea is to generate a bunch of circles, and then to cull those that intersect. For the culling phase, I used a halfway implementation of Sweep & Prune which speeds things up a bit as far as collision detection goes for large n.

• Generate points randomly
• Sort their x-coordinates
• Save pairs whose x-coordinates overlap for further testing, discard the rest
• For saved pairs, determine whether y-coordinates overlap as well
• If so, then they potentially collide, so do the actual collision test on them
• If they collide, then discard one of the pair

The macro is \circles{n}{rad}{width}{height} and \circles{500}{.1}{10}{5} gives:

\documentclass{article}
\usepackage{luacode}
\usepackage{tikz}
\usetikzlibrary{backgrounds}

\begin{luacode*}

local rand = math.random
local abs = math.abs
local pts = {}
local tstpairs = {}

-- generate the points
local function genpts(n,x,y)
for i = 1,n do
pts[i]={}
pts[i][1] = rand()*x
pts[i][2] = rand()*y
end
end

-- for sorted pairs, check if x-coords overlap
-- if so, store the pair in table tstpairs
local function getpairs(t,r)
for i = 1,#t do
tstpairs[i] = {}
for j = 1,#t-i do
if t[i+j][1]-t[i][1]<2*r then
tstpairs[i][#tstpairs[i]+1]=i+j
else
break
end
end
end
end

-- this is the actual collision test
-- it's less expensive to use x^2+y^2<d^2 than sqrt(x^2+y^2)<d
local function testcol(a,b,r)
local x = pts[b][1]-pts[a][1]
local y = pts[b][2]-pts[a][2]
if x*x+y*y<4*r*r then
return true
end
end

-- this is a bit of a mess, deleting pairs on the fly was causing some
-- problems, so I had to include some checks "if pts[k1]..." etc.
local function delpairs(r)
for k1,v1 in pairs(tstpairs) do
if pts[k1] then
for k2,v2 in pairs(v1) do
if pts[v2] then
if abs(pts[v2][2]-pts[k1][2])<2*r then
if testcol(k1,v2,r) then
pts[v2]=nil
end
end
end
end
end
end
end

-- quickSort helper
local function partition(array, p, r)
local x = array[r][1]
local i = p - 1
for j = p, r - 1 do
if array[j][1] <= x then
i = i + 1
local temp = array[i][1]
array[i][1] = array[j][1]
array[j][1] = temp
end
end
local temp = array[i + 1][1]
array[i + 1][1] = array[r][1]
array[r][1] = temp
return i + 1
end

-- quickSort to sort by x
-- taken from https://github.com/akosma/CodeaSort/blob/master/QuickSort.lua
local function quickSort(array, p, r)
p = p or 1
r = r or #array
if p < r then
q = partition(array, p, r)
quickSort(array, p, q - 1)
quickSort(array, q + 1, r)
end
end

-- draw output
local function showout(n,r,x,y)
tex.print("\\draw[red](0,0) rectangle ("..x..","..y..");")
for k,v in pairs(pts) do
tex.print("\\draw ("..pts[k][1]..","..pts[k][2]..") circle ;")
end
tex.print("\\end{tikzpicture}")
end

-- wrapper
function circles(n,r,x,y)
genpts(n,x,y)
quickSort(pts)
getpairs(pts,r)
delpairs(r)
showout(n,r,x,y)
end

\end{luacode*}

\def\circles#1#2#3#4{\directlua{circles(#1,#2,#3,#4)}}

\begin{document}

\circles{500}{.1}{10}{5}

\end{document}

-
Your code works well and is very fast - I had no problems with values of 1500/10/10 (but I don't know if this is because of the code or because you are using luatex ;-)). In my real document I rewrote the code of Jake to export the values in files to reuse them and so to save some time (and to be able to change the look of the output a bit if wanted). –  Ulrike Fischer Jan 3 '13 at 8:18
I did some tests when I was playing around with this, and for reasonably sized n, the brute force approach and this one take a very similar amount of time (both using lua to do the calculations). The use of lua accounts for the vast majority of the speed difference between this and Jake's nice solution. –  Scott H. Jan 3 '13 at 16:01

Just discovered this old question, and for completeness I decided to add the following answer.

Poisson disc sampling seems to be the right way to create this kind of patterns. This question/answer provides an implementation of this algorithm in pure lualatex, allowing its use from pgf/tikz.

Provided that you have poisson.sty and poisson.lua (which you can get from the mentioned answer), and a working install of lualatex, the solution will be:

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{backgrounds}
\usepackage{poisson}

\begin{document}
\edef\mylist{\poissonpointslist{5}{5}{1}{20}}
% 5 x 5 is the size of the area to fill
% 1 is the minimum distance between centers
\draw[red](0,0) rectangle (5,5);
\foreach \x/\y in \mylist \draw (\x,\y) circle;
\end{tikzpicture}
\end{document}


And the result (compiled with lualatex) is:

-

I know this is a pretty old question, but I've been looking to do something similar. Jake's code above almost works for me, but I want finer control over the number of circles that actually appear. So I've modified Jake's code like so (I've also optimised slightly by comparing squared distances rather than absolute distances):

\newcommand{\fillrandomly}[4]{
\xdef\xlist{4}
\xdef\ylist{4}
\pgfmathsetmacro\diametersqr{(#3*2)^2}
\draw (0,0) rectangle (#1,#2);
\foreach \i in {1,...,#4}{
\foreach \k in {1,...,20}{
\pgfmathsetmacro\x{rnd*#1}
\pgfmathsetmacro\y{rnd*#2}
\xdef\collision{0}
\foreach \element [count=\i] in \xlist{
\pgfmathtruncatemacro\j{\i-1}
\pgfmathsetmacro\checkdistancesqr{ ( ({\xlist}[\j]-(\x))^2 + ({\ylist}[\j]-(\y))^2 ) }
\ifdim\checkdistancesqr pt<\diametersqr pt
\xdef\collision{1}
\breakforeach
\fi
}
\ifnum\collision=0
\xdef\xlist{\xlist,\x}
\xdef\ylist{\ylist,\y}
\draw [red, thick] (\x,\y) circle [radius=#3];
\breakforeach
\fi
}
}
}


This loops through trying to place n circles, for each circle it will attempt to place it up to 20 times before giving up. If you've got tightly packed circles it's not much better but for relatively loosely placed circles you can be pretty sure of getting the requested number of circles in a relatively short time frame.

-