18. Oktober 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:

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:

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: