相关疑难解决方法(0)

给定具有半径r1 ... rn的n个圆,以这样的方式定位它们,使得没有圆重叠并且边界圆具有"小"半径.

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

1. 我要求"小",因为"最小"半径将其转换为更难的问题(最小版本已被证明是NP难/完全 - 请参阅问题末尾附近的脚注).我们不需要最低限度.如果圆圈形状看起来相当圆,那就足够了.
2. 如果有帮助,您可以假设Rmax/Rmin <20.
3. 一个低优先级的问题 - 该计划应该能够处理2000多个圈子.首先,即使100-200圈也应该没问题.
4. 你可能已经猜到圆圈不需要紧紧地包在一起,甚至不能互相接触.

目的是提出给定圆圈的视觉上令人愉悦的布置,其可以适合更大的圆圈并且不留下太多的空白空间.(如色盲测试图中的圆圈).

你可以使用下面的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 = …