Dense packing of congruent circles in free-form non-convex containers

摘要

This paper proposes an algorithm for computing dense packings of congruent circles inside general 2D containers. Unlike the previous approaches which accept as containers, only simple, symmetric shapes such as circles, rectangles and triangles, our method works for any container with a general, freeform (spline) boundary. In contrast to most previous approaches which cast the problem into a non-convex optimization problem, our method attempts to maximize the number of packed circles via a perturbation approach and consists of two main phases. In the first phase, an initial packing is computed by placing circles in spiraling layers, starting along the boundary of the container. The next phase simulates the shaking of a container under gravity, thereby making room for additional circles by perturbing the existing circles. While the general circle packing problem is known to be NP-hard (Hifi et al, 2004), our method proposes heuristics which lead to dense packings. Comparison of results with previous approaches on simple, symmetric shapes shows the effectiveness of our algorithm while results of packing inside freeform containers demonstrates the generality of our algorithm.