将N个不同半径的圆圈放置在一个较大的圆圈内，不要重叠
给定n个半径为r1 ... rn的圆，将它们定位，使得圆不重叠，边界圆的半径为“小”。
该程序将列表[r1，r2，... rn]作为输入并输出圆的中心。
其目的是想出一个视觉上令人愉快的给定圈子的安排，它可以适应更大的圈子，而不会留下太多的空白空间。 （如色盲测试图片中的圆圈）。 
你可以使用下面的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)
补充信息：谷歌搜索结果中通常提到的圆圈包装算法不适用于此问题。
因此，另一个“圆形包装算法”的问题陈述是：给定一个复数K（在这种情况下的图形称为单纯形复合体，简称复合体）和适当的边界条件，计算相应圆形包装的半径。 ..
它基本上从描述哪些圆相互接触的图形开始（图的顶点表示圆，边表示圆之间的触摸/相切关系）。 人们必须找到圆的半径和位置，以便满足由图表表示的触摸关系。
另一个问题确实有一个有趣的观察（独立于这个问题）：
圆包装定理 - 每一个圆包装都有一个相应的平面图（这是简单/明显的部分），每个平面图都有相应的圆包装（不是那么明显的部分）。 图表和包装是相互对立的并且是独一无二的。
我们没有从我们的问题开始的平面图或切线关系。
本文 - Robert J. Fowler，Mike Paterson，Steven L. Tanimoto：平面中的最佳包装和覆盖是NP完全的 - 证明了这个问题的最小版本是NP完全的。 然而，这篇论文并没有在线提供（至少不太容易）。
我有一个非常天真的一次传球（通过半径）解决方案，产生了良好的结果，虽然肯定有改进的余地。 我在这个方向上有一些想法，但是我想我也可以分享我的情况，以防其他人想要破解它。
看起来他们在中心相交，但他们不相交。 我使用嵌套循环来装饰放置函数，该循环检查每个圆圈与其他圆圈（两次），并在存在交叉点时引发AssertionError 。
此外，我可以通过简单地对列表进行反向排序来获得接近完美的边缘，但我认为该中心看起来不错。 它（几乎是唯一的东西;）在代码的评论中讨论。
我们的想法是只查看圆圈可能存在的离散点，并使用以下生成器对它们进行迭代：
def base_points(radial_res, angular_res):
circle_angle = 2 * math.pi
r = 0
while 1:
theta = 0
while theta <= circle_angle:
yield (r * math.cos(theta), r * math.sin(theta))
r_ = math.sqrt(r) if r > 1 else 1
theta += angular_res/r_
r += radial_res
这只是从原点开始，沿着它的同心圆追踪点。 我们根据一些参数对半径进行排序来处理半径，以保持大圆在中心附近（列表的开头），但是在开始附近有足够的小圆以填充空格。 然后我们遍历半径。 在主循环中，我们首先循环已经看过并保存的点。 如果这些都不合适，我们开始从发生器中拉出新的点并保存它们（按顺序），直到找到合适的点。 然后，我们放置圆圈并通过我们的保存点列表，将所有属于新圆圈的点拉出来。 然后我们重复。 在下一个半径上。
我会提出一些想法，让它变成现实。 对于基于物理学的想法来说，这可能是一个很好的第一步，因为你可以从没有重叠的地方开始。 当然，它可能已经足够紧凑，所以你没有太多空间。
另外，我从来没有玩过numpy或matplotlib，所以我只写了香草python。 那里可能有东西会让它跑得快得多，我得看看。
这不是一个解决方案，只是一个头脑风暴的想法：IIRC获得TSP近似解决方案的一种常见方法是从随机配置开始，然后应用本地操作（例如“交换”路径中的两条边）尝试并缩短较短的路径。 （维基百科链接）
我认为在这里可能会有类似的情况：
有趣的问题是：步骤3中可以使用什么样的“迭代改进算子”？ 我们可以假设那个阶段的位置是局部最优的，但是可以通过重新排列大部分的圆来改善它们的位置。 我的建议是任意选择通过圈子的一条线。 然后将线条的所有圆圈“左”并在垂直于该线的某个轴上镜像它们： 
你可能会尝试多条线路并选择一条导致最紧凑解决方案的线路。
这个想法是，如果一些圈子已经或者接近他们的最佳配置，那么很可能这个操作不会打扰他们。
我能想到的其他可能的操作：
然后，您可以选择与最大的圆圈区域（图像中的红色区域）相邻的一个圆圈，并将其与另一个圆圈交换，或将其移动到边界的某处。
（回应评论:)请注意，这些“改进”中的每一个几乎都能保证在圈子之间产生重叠和/或不必要的空间。 但在接下来的迭代中，第2步将移动这些圆，以便它们紧密排列并且不重叠。 通过这种方式，我可以采取一步进行本地优化（不关心全局优化），还可以进行全局优化（可能会创建本地次优解决方案）。 这比一个复杂的步骤要容易得多。
你可以将圆圈视为带电腔中的带电粒子并寻找稳定的解决方案吗？ 也就是说，圆圈根据邻近度相互排斥，但被吸引到原点。 几个步骤的模拟可能会给你一个体面的答案。
链接地址: http://www.djcxy.com/p/84977.html上一篇: Position N circles of different radii inside a larger circle without overlapping