A Simple Circle Packing Algorithm

The concept of this algorithm is very simple: instead of adding a new circle and then checking whether it overlaps with existing circles, divide up space in such a way that any circle created is guaranteed to not overlap existing circles. The algorithm also produces circles tangent to each other.

Here are the steps:

1. Start with an initial set of non-overlapping triangles.
2. Compute the in-circle for each triangle.
3. Carve off subtriangles tangent to the in-circle.
4. Iterate using the new set of subtriangles.

Let's look at each of these steps in more detail.

Triangulation

The simplest thing to do is start with a Delaunay triangulation over a set of points arranged in some interesting way. But one could also just perform a construction, such as a set of pie slices from a center point, or a stair-step of triangles down the page. As long as the initial set of triangles don't overlap, the circles won't either.

Computing the in-circle

Computation of the in-circle for a triangle is easy: compute the center point for the in-circle. The radius will be the distance from that point to the nearest point on an edge (any edge).

If the triangle has vertices PA, PB, and PC, with the lengths of the opposing edges being a, b, and c, respectively, then the center of the in-circle is:

(a*PA + b*PB + b*PC) / (a + b + c)
        

The closest distance between a point pt and an edge from v to w, where l is the length of the edge, is the distance between pt and:

v + ((pt - v)·(w - v)/l²)*(w - v)
       

(Edge case: If v is the same as w then compute the distance between pt and v instead.

The original triangulation is shown in red. The in-circles are drawn in black. Their centers are shown in red and the nearest point to the center on each edge is shown in blue.

Computing sub-triangles

Each corner of the existing triangle will give us a new subtriangle. Compute the tangent line at the point on the in-circle in the direction of the vertex. Then take the intersection points of that line with the edges meeting at that vertex as the other two vertices of the new subtriangle.

The original triangulation is shown in red. The in-circles are drawn in black. The new sub-triangles are shown in blue.

The intersection between two lines A1x + B1y + C1 = 0 and A2x + B2y + C2 = 0 can be computed using determinants (det((x1,y1),(x2,y2)) = x1*y2 - x2*y1). If A = (A1, A2) and similarly for B and C, then the intersection point exists only if det(A,B) is non-zero, and is:

(-det(B,C)/det(A,B), dep(A,C)/det(A,B))
        

In this case, A, B, and C for an edge from (x1,y1) to (x2,y2) can be calculated so:

A = y2 - y1
B = x1 - x2
C = Ax1 + By1
        

The tangent line has an angle 90° from the angle between the vertex and the center and goes through a point at the distance of the radius from the center at that angle.

Iterate

We know the new set of triangles do not intersect with each other or with any existing circles. We can perform the same procedure all over again with that new set, repeating the process however many times we want.

It is a good idea to add a minimum limit to the acceptable radius of the in-circles, so we don't get too ridiculous. You can also adjust the "frothiness" by choosing not to subdivide a certain percentage of the triangles.

The original triangulation is shown in red. The new sub-triangles are shown in blue. All in-circles are drawn in black.

Notice how the new in-circles lie tangent to their parent in-circle. The in-circle for the triangle formed tangent to the parent circle must fit at the place where the subtriangle is largest, and that must be at that tangent point, as the original in-circle is the largest inscribed circle in the original triangle.