改进区域划分的圆Packing变分算法

Improved Domain Partitions for Variational Circle Packing

通过改进基于Power图的区域划分,提出一种收敛速度更快的圆packing算法.首先固定容器面积,将输入圆缩小一定的倍数,随机撒在容器中;之后对圆心点进行三角化,并根据相邻圆的半径比值对容器进行区域划分;再让所有圆在不超出自己区域边界的条件下尽量等比例增长至最大;最后将划分区域-长大的过程迭代下去,得到最大增长倍数.实验结果表明,该算法能够使得圆packing的过程更快地达到收敛.

This paper presents a circle packing algorithm which converges faster by improving the domain partitions based on power diagram. By setting the area of the container fixed, we firstly shrank the input circles so that they wouldn＇t overlap when scattered randomly in the container. Secondly, we triangulated the circle center points, and divided the container area into sub-regions according to the radius ratio of adjacent circles. And then all circles grew by the same ratio within their own regions. By repeating the ＂partition-and-grow＂ operations, we finally got the packing result. Experimental results show that our method can converge more quickly.