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:
Let's look at each of these steps in more detail.
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
(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 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.
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
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.
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.