18. October 2013

Recursive circle packing with PostScript

Ten lines of PostScript are sufficient to draw a pretty self-similar pattern constructed by packing circles into circles.

The self-similar pattern above right is constructed by packing N circles in an outer circle such that each smaller circle is tangential to its two neighbors and the outer circle (with an optional circle in the center). The figure to the left shows how to determine the radius of the smaller circles, assuming the outer circle to have unit diameter. Doing the necessary maths:

5c41ef97cac19f2cc62a1fa435e90e5089514055

The maths translates to PostScript as follows:

/r 180 N div sin dup 1 add div

For N=2,3,4,5,6 (and only one recursion level), the drawings correspond to optimal solutions of the circle packing problem, where N unit-diameter circles have to be packed into an outer circle with the smallest diameter possible. This can be confirmed by computing the radius R of the outer circles of the optimal circle packings for N=2,3,4,5,6:

4ff1c51c038d62c0a0f66df0ee793fa9b01d4b3e

My original intention was not about doing maths. It was not about doing arts either. I was rather interested in learning PostScript. A condensed version of the hand-written PostScript implementation covers ten lines:

%!PS-Adobe-2.0
%%BoundingBox: 45 245 555 755
/N 8 def /D 4 def /r 180 N div sin dup 1 add div def /nroot { 360 mul
N div } bind def /drawunitcircle { dup 0.1 exch dup mul 1 add div
setlinewidth sqrt sqrt 1 add 1 exch div 1.75 div setgray 0 0 1 0 360
arc closepath stroke } bind def /circlepattern { dup drawunitcircle
dup 0 gt { 1 sub gsave 1 r 2 mul sub dup scale dup circlepattern
grestore 1 1 N { gsave nroot rotate 1 r sub 0 translate r dup scale
dup circlepattern grestore } for } if pop } bind def 300 500 translate
250 250 scale 0.35 setgray D circlepattern

Of course, the original version was a little bit more verbose.