Title: Draw an Apollonian circle packing fractal in Python

$[An Apollonian circle packing fractal drawn in Python]$

To make an Apollonian circle packing, you start with a large circle and then fit three circles inside it so they are tangent to the outer circle and to each other.

Next, you find the areas between the circles and place another circle inside each one so it is tangent to the circles that define its areas. The picture on the left below shows the packing at this stage with the four areas between the circles numbered. The picture on the right shows the result after this step.

$[The first steps in an Apollonian circle packing fractal]$ Notice that there are two kinds of areas to fill. The first, numbered 1 in the picture on the left above, is surrounded by three circles. The second kind of area lies inside one circle and outside two others. In the picture, the areas of this kind are numbered 2, 3, and 4.

The next step in building the circle packing is to find all of the newly defined areas and put circles inside them. You continue adding more circles until you reach a desired depth of recursion or the radii of the circles is smaller than 1 pixel so adding more doesn't change the resulting picture.

That's how Apollonian circle packings work. Now let's look at some code.

Creating Circle Packings

Building a circle packing from scratch would be a daunting task. Fortunately, we've already laid the groundwork in earlier posts. There's still some work to do, but some of the important details were already covered by these posts:

The first post lets us figure out where the first three inscribed circles belong. The second finds circles that are tangent to the circles that define one of the areas.

The following function organizes the drawing process.

def make_apollonian_circle_packing(max_depth, cx, cy, radius): '''Return a list of circles (x, y, radius, depth) for a circle packing.''' # Make the big outer circle. depth = 0 big_circle = [cx, cy, radius, depth] circles = [big_circle] if depth >= max_depth: return circles depth += 1 # Make the three second-to-largest circles. centers = get_inner_circles(cx, cy, radius, depth) circles += [(x, y, r, depth) for x, y, r, depth in centers] if depth >= max_depth: return circles depth += 1 # Find the central circle. c0, c1, c2 = centers find_circle_outside_all(circles, max_depth, depth, c0, c1, c2) # Find circles tangent to the big circle. find_circle_outside_two(circles, max_depth, depth, c0, c1, big_circle) find_circle_outside_two(circles, max_depth, depth, c1, c2, big_circle) find_circle_outside_two(circles, max_depth, depth, c2, c0, big_circle) return circles

The code first makes the outer circle with the desired center and radius. For the convenience of my next post, each circle used by this program is stored in the form (x, y, radius, depth) where depth is the circle's depth of recursion.

Having defined the outer circle, the function adds it to a new circles list.

Next, the code calls the get_inner_circles function (highlighted in green) from the post Place three small circles inside a larger circle so they are all tangent in Python. It appends the depth 1 to those three circles and adds them to the circles list.

Now the function calls two recursive functions to define the rest of the packing's circles. To find the central circle (inside area 1 in the earlier picture), the code calls find_circle_outside_all (highlighted in blue). To find the other circles (areas 2, 3, and 4 in the earlier picture), the function calls find_circle_outside_two (also highlighted in blue).

find_circle_outside_all

The find_circle_outside_all function shown in the following code finds a circle that is outside of all of the circles that define its area.

def find_circle_outside_all(circles, max_depth, depth, c0, c1, c2): '''Find a circle tangent to these three and outside all three.''' # Circles are of the form (x, y, radius, depth). if depth > max_depth: return # Find the circle. new_circle = find_apollonian_circle(c0, c1, c2, 1, 1, 1) new_circle[2] = abs(new_circle[2]) if new_circle is None or new_circle[2] < 0.1: return new_circle.append(depth) # Save the new circle. circles.append(new_circle) # Recursively find other circles. depth += 1 find_circle_outside_all(circles, max_depth, depth, c0, c1, new_circle) find_circle_outside_all(circles, max_depth, depth, c0, c2, new_circle) find_circle_outside_all(circles, max_depth, depth, c1, c2, new_circle)

To actually find the circle, the function calls find_apollonian_circle (highlighted in green), which was described in my post Find circles that are tangent to three given circles (Apollonius' Problem) in Python. As you undoubtedly recall (or can learn if you look at that post), finding a circle tangent to three other circles requires you to solve an equation that uses ± three times. There are eight possible combinations:

(+1, +1, +1) (+1, +1, -1) (+1, -1, +1) (+1, -1, -1) (-1, +1, +1) (-1, +1, -1) (-1, -1, +1) (-1, -1, -1)

Each of those possible combinations for the ± terms leads to a different solution, so there are eight possible circles tangent to three given circles. The trick for finding the Apollonian circle packing is to know which of those terms should be +1 and which should be -1.

To find a circle with the three other circles all outside it, you use the terms (+1, +1, +1), so that's what the find_circle_outside_all function does. It passes 1 for the last three arguments to find_apollonian_circle and adds the new circle to the circles list.

If you look at the earlier pictures, you'll see that adding the central circle creates three new smaller areas that are bounded by two of the previous circles plus the new one. To add circles to those areas, the function calls itself recursively three times (highlighted in blue).

find_circle_outside_two

The find_circle_outside_two function shown in the following code finds a circle that is outside of two circles and inside a third.

def find_circle_outside_two(circles, max_depth, depth, c0, c1, c_contains): '''Draw a circle tangent to these three and outside two of them.''' if depth > max_depth: return # Find the circle. new_circle = find_apollonian_circle(c0, c1, c_contains, 1, 1, -1) new_circle[2] = abs(new_circle[2]) if new_circle is None or new_circle[2] < 0.1: return new_circle.append(depth) # Save the new circle. circles.append(new_circle) # Recursively find other circles. depth += 1 find_circle_outside_two(circles, max_depth, depth, new_circle, c0, c_contains) find_circle_outside_two(circles, max_depth, depth, new_circle, c1, c_contains) find_circle_outside_all(circles, max_depth, depth, c0, c1, new_circle)

This function is somewhat similar to find_circle_outside_all. It calls find_apollonian_circle (orange) described in my post Find circles that are tangent to three given circles (Apollonius' Problem) in Python to find the next circle. This time it passes that function the parameters (1, 1, -1) to find the tangent circle that lies inside one circle and outside the others.

The new circle defines three areas, one that lies outside three circles and two that lie inside one of the circles. (See the earlier picture again to see those areas.) The function calls find_circle_outside_two (green) twice and find_circle_outside_all (blue) once to recursively find those circles.

Conclusion

Drawing an Apollonian circle packing isn't trivial, but it's not too bad if you already have a function to position the first three circles inside the outer circle and another function to find tangent circles. The key to the packing lies in the find_circle_outside_all and find_circle_outside_two functions, which are each less than a dozen lines long (if you ignore blank lines and comments).

In my next two posts, I'll describe ways to make the packing more interesting. Until then, download the example to experiment with it and to see additional details.