Tuesday, June 07, 2016

[tebaqzie] Circle packing by nudging

Pack a given collection of discs of different sizes into a given region without overlap, scaling the region larger if necessary.  Minimize the scaling factor.

Start by placing the discs randomly.  They will overlap as well as extend outside the region.  Pick two discs that overlap and nudge one or both so that their centers move diametrically away from each other, so that there is locally less overlap.  This can also be done with a disc extending beyond an edge.  Accept if this improves a scoring function of total overlap.  If after enough steps and nothing seems to improve things, then scale up the size of the region.  Apply simulated annealing, including large jumps.

Improvement: for a selected circle, examine what it overlaps. Compute a vector sum of pushes from the overlaps and nudge in that direction.

No comments :