algorithm - 将 N 个不同半径的圆放在一个较大的圆内而不重叠

Question

给定 n 个半径为 r1 ... rn 的圆，将它们放置在没有圆重叠且边界圆具有“小”半径的位置。

该程序将列表 [r1, r2, ... rn] 作为输入并输出圆心。

1. 我要求“小”是因为“最小”半径将它转化为一个更困难的问题(最小版本已经被证明是 NP 困难/完整的 - 参见问题末尾的脚注)。我们不需要最低限度。如果圆圈形成的形状看起来很圆，那就足够了。
2. 如果有帮助，您可以假设 Rmax/Rmin < 20。
3. 低优先级问题 - 该程序应该能够处理 2000 多个圈子。一开始，即使是 100-200 圈也应该没问题。
4. 您可能已经猜到，这些圆圈不需要紧紧地挤在一起，甚至不需要相互接触。

目标是对给定的圆圈进行视觉上令人愉悦的排列，这些圆圈可以容纳在更大的圆圈内并且不会留下太多空白空间。 (就像 color blindness test picture 中的圆圈)。

您可以使用下面的 Python 代码作为起点(此代码需要 numpy 和 matplotlib - 在 Linux 上“sudo apt-get install numpy matplotlib”)...

import pylab
from matplotlib.patches import Circle
from random import gauss, randint
from colorsys import hsv_to_rgb

def plotCircles(circles):
    # input is list of circles
    # each circle is a tuple of the form (x, y, r)
    ax = pylab.figure()
    bx = pylab.gca()
    rs = [x[2] for x in circles]
    maxr = max(rs)
    minr = min(rs)
    hue = lambda inc: pow(float(inc - minr)/(1.02*(maxr - minr)), 3)

    for circle in circles:
        circ = Circle((circle[0], circle[1]), circle[2])
        color = hsv_to_rgb(hue(circle[2]), 1, 1)
        circ.set_color(color)
        circ.set_edgecolor(color)
        bx.add_patch(circ)
    pylab.axis('scaled')
    pylab.show()

def positionCircles(rn):
    # You need rewrite this function
    # As of now, this is a dummy function
    # which positions the circles randomly
    maxr = int(max(rn)/2)
    numc = len(rn)
    scale = int(pow(numc, 0.5))
    maxr = scale*maxr

    circles = [(randint(-maxr, maxr), randint(-maxr, maxr), r)
               for r in rn]
    return circles

if __name__ == '__main__':
    minrad, maxrad = (3, 5)
    numCircles = 400

    rn = [((maxrad-minrad)*gauss(0,1) + minrad) for x in range(numCircles)]

    circles = positionCircles(rn)
    plotCircles(circles)

---

补充信息:google搜索结果中常用的circle packing算法不适用于此问题。

因此，另一个“Circle packing algorithm”的问题陈述是:给定复数 K(本文中的图称为单纯复形，简称为复数)和适当的边界条件，计算相应的圆填充的半径为K....

它基本上从一个图表开始，说明哪些圆圈相互接触(图表的顶点表示圆圈，边表示圆圈之间的接触/相切关系)。必须找到圆的半径和位置，以满足图形表示的接触关系。

另一个问题确实有一个有趣的观察(独立于这个问题):

圆堆积定理 - 每个圆堆积都有对应的平面图(这是容易/明显的部分)，每个平面图都有对应的圆堆积(不太明显的部分)。图表和包装互为对偶，并且是唯一的。

在我们的问题中，我们没有平面图或切线关系作为起点。

这篇论文 - Robert J. Fowler、Mike Paterson、Steven L. Tanimoto:平面中的最优打包和覆盖是 NP 完全 - 证明了这个问题的最小版本是 NP 完全.但是，无法在线获取该论文(至少不容易)。

Answer 1

不是解决方案，只是头脑 Storm 的想法:IIRC 获得 TSP 近似解决方案的一种常见方法是从随机配置开始，然后应用局部操作(例如“交换”路径中的两条边)来尝试和得到越来越短的路径。 ( Wikipedia link )

我认为类似的东西在这里是可能的:

1. 从随机的中心位置开始
2. 通过增加重叠圆之间的距离并减少其他圆之间的距离，“优化”这些位置，因此没有重叠的圆，因此圆尽可能靠近，直到它们紧密排列。这可以通过某种能量最小化来完成，或者可能有更有效的贪婪解决方案。
3. 将迭代改进算子应用于中心位置
4. 转到 2，在最大迭代次数后中断，或者如果最后一次迭代没有发现任何改进

有趣的问题是:您可以在第 3 步中使用哪种“迭代改进运算符”？我们可以假设该阶段的位置是局部最优的，但可以通过重新排列大部分圆圈来改善它们。我的建议是通过圆圈任意选择一条线。然后取该线“左侧”的所有圆圈，并在垂直于该线的某个轴上镜像它们: 您可能会尝试多行并选择导致最紧凑解决方案的那一行。

想法是，如果某些圆圈已经处于或接近其最佳配置，则此操作很可能不会打扰它们。

我能想到的其他可能的操作:

• 取离中心最远的圆圈之一(一个接触边界圆圈)，并将其随机移动到其他地方:
• 选择一组彼此靠近的圆(例如，如果它们的中心位于随机选择的圆中)并将它们旋转一个随机角度。
• 另一种选择(虽然有点复杂)是在圆圈紧密排列时测量圆圈之间的面积:

然后您可以选择与最大圆圈间区域(图中红色区域)相邻的圆圈中的一个，并将其与另一个圆圈交换，或者将其移动到边界的某处。

(对评论的回应:)请注意，几乎可以保证这些“改进”中的每一个都会在圆圈之间产生重叠和/或不必要的空间。但在下一次迭代中，第 2 步将移动圆圈，使它们再次紧密排列且不重叠。这样，我可以一步进行局部优化(不关心全局优化)，一步进行全局优化(这可能会创建局部次优解决方案)。这比一个复杂的步骤同时完成这两项操作要容易得多。