This weekend, I started to work on a program that will take any shape and fill it with the largest possible inscribed circles. Something like this:

One of the reasons I am interested in doing this is to create a music visualizer. If similar shapes produce similar sets of circles, I can manipulate the shape using sound and get smoothly shifting circles. But to test the algorithm, I started with a random shape generator.

Each point is based on a random radius and angle, but the angle is always increased to avoid looping the shape over itself.

The algorithm I’ve drafted on paper has changed a lot, but it always has these components:

• A spline which provides information about the nearest points to a location.
• A seed method, which chooses a starting point for a seed circle of radius 0. It selects the center of the spline if there are no circles yet. Later it will select from known open spaces in a “fit bin” – if no such spaces are stored, it will choose a tangent point on the largest circle.
• An expansion method, which repeats certain steps until the seed fills its surroundings and has 3 tangent points with the spline or other circles.
• A resolution method, which uses the expansion method to expand the seed, but then attempts to fit this seed into other spaces to see if it can get any bigger. If there is a larger space for the seed, the current seed location and size are saved as an entry to the fit bin, the seed is placed in the larger space, and the method starts over.

I also hope to develop a system for limiting the portions of the spline and circle set that need to be checked continuously during the expansion method. This could take the form of data stored by circles about the places they touch the spline. (If a seed next to a large circle is between two of the large circle’s tangent points to the spline, a and b, then only points in the spline between the indexes a and b need to be checked)

This range could be limited further, to within the outer tangent points of any connected circles around the seed. In the ideal program, the spline will be ignored completely for a seed surrounded on all sides by circles.

The first basic step to my expansion function is to find the 3 nearest points of either circles or the spline, and to set the seed’s radius to the average of their distances.

Using the basic seed method with only a spline present, the seed often looks perfect after the first step. However, it is guaranteed to overlap at least one point. The next step is to move it directly away from the closest/most overlapped point until it is tangent to that point, and start over. It will be closer to the other two points after moving away from the first, usually…

…unless they’re all bunched together. (I caused this problem by smoothing a spline with many points.) In this case, the seed will still expand and move away from the spline until it touches other points, but it may do so very slowly. Luckily, the seed will never have this problem when interacting with placed circles, because a circle will only provide one point as the nearest to a location.

The greatest challenge of this project? speed. I want to save enough frames to render a 30fps music video, with at least 64 circles in each frame. It could easily take days if I approach this the wrong way.