5

给定一个标准的嵌套圆形树图,你如何计算放置圆圈的位置?

4

1 回答 1

1

您的主要问题可以描述为:“ Given a set of circles of varying radius, how does one place them within a larger circle, so that none of them overlap”。

这是一个难题,但这里有一个强力解决方案可以帮助您入门:

  1. 按大小对圆圈进行排序
  2. 将最大的圆放在边界圆的内缘
  3. 对于其余的圆圈 (r1),请执行以下操作:
    1. 迭代所有已放置的圆对(r2,r3)(包括外部圆)
    2. 找到到第一个圆的距离为 r1+r2 和到第二个圆的距离为 r1+r3 的(一个或两个)点。
    3. 尝试将新圆圈放在这里。

以上使用的观察结果是,在完美包装中,每个圆圈必须与至少两个其他圆圈接壤。您可以使用该算法提供完整搜索,或者您可以随机迭代并贪婪地选择第一个可用点。

于 2013-04-30T12:26:01.367 回答