给定一个标准的嵌套圆形树图,你如何计算放置圆圈的位置?
问问题
802 次
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
”。
这是一个难题,但这里有一个强力解决方案可以帮助您入门:
- 按大小对圆圈进行排序
- 将最大的圆放在边界圆的内缘
- 对于其余的圆圈 (r1),请执行以下操作:
- 迭代所有已放置的圆对(r2,r3)(包括外部圆)
- 找到到第一个圆的距离为 r1+r2 和到第二个圆的距离为 r1+r3 的(一个或两个)点。
- 尝试将新圆圈放在这里。
以上使用的观察结果是,在完美包装中,每个圆圈必须与至少两个其他圆圈接壤。您可以使用该算法提供完整搜索,或者您可以随机迭代并贪婪地选择第一个可用点。
于 2013-04-30T12:26:01.367 回答