Here’s my first, failed attempt at an optimization. The area of a new circle cannot be greater than the remaining area inside the polygon. I thought I could use that fact to avoid testing circles whose areas were greater than the area of the remaining space in the polygon.
I started by measuring how much space was left over inside of the polygon after the packing completed. Unfortunately, I found that, even after packing 2,000 circles, the area of the polygon minus the sum of the area of the circles was still greater than the area of the largest circle I tried packing at the very beginning.
Take, for example, this hexagon:
Its area is 256,000 pixels. Even after packing all 2,000 circles, the sum of their areas is 151,731 pixels. That leaves an area of 104,269 pixels. If we were to somehow recombine that leftover area into a circle, that circle would have a radius of 182 pixels, which is more than the 64-pixel radius of the largest possible circle. As Toph Tucker might say, there’s plenty of room in the corners.
I still like the idea of testing progressively smaller circles, but they need to get smaller some other way.