
A Simple Circle Packing AlgorithmThe 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:
Let's look at each of these steps in more detail. TriangulationThe 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 stairstep of triangles down the page. As long as the initial set of triangles don't overlap, the circles won't either. Computing the incircleComputation of the incircle for a triangle is easy: compute the center point for the incircle. The radius will be the distance from that point to the nearest point on an edge (any edge). If the triangle has vertices (a*PA + b*PB + b*PC) / (a + b + c) The closest distance between a point v + ((pt  v)·(w  v)/l²)*(w  v) (Edge case: If The original triangulation is shown in red. The incircles 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 subtrianglesEach corner of the existing triangle will give us a new subtriangle. Compute the tangent line at the point on the incircle 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 incircles are drawn in black. The new subtriangles are shown in blue.
The intersection between two lines (det(B,C)/det(A,B), dep(A,C)/det(A,B)) In this case, 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. IterateWe 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 incircles, 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 subtriangles are shown in blue. All incircles are drawn in black. Notice how the new incircles lie tangent to their parent incircle. The incircle 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 incircle is the largest inscribed circle in the original triangle.
