logo标签列表

圆在矩形中的排列算法

javaalgorithmcomputational-geometry
3
我需要一个适合一组不同半径圆的装箱算法，如果这些圆可以放入矩形中，则符合条件。我已经看过维基百科Wikipedia和其他网站上的各种页面，但实现本身要么太复杂，要么只是一个数学定理，我没有使用它们的经验或知识。
有人问了this question，这有点相反——我需要矩形中的圆而不是相反，我更喜欢Java而不是MATLAB，虽然如果必要，我可以转换它。
谢谢！
编辑：
我不需要找到最小的矩形来容纳这些圆，我只需要知道这些圆是否能够放入指定尺寸的矩形中。
您可以使用遗传算法，编写起来通常很简单，但这取决于您的目标，这是否是正确的方法。 - austinbv
这里有一个链接：http://goo.gl/wrxXV，不过我应该说一下（并更新问题），我不需要找到最小的矩形或其他什么，我需要弄清楚给定的一组圆是否适合在指定的矩形内。 - skeggse
2个回答
2
这个问题似乎与装箱问题密切相关，因此我怀疑它是NP难的。所以不幸的是，我认为没有一个好的算法可以高效地解决它（即非暴力搜索）。
我甚至认为没有一个好的、简单的、贪心的方法来处理它。
虽然如果你能够获得相关的研究论文，那么关于这个问题已经有很多论文写过了。这里是其中的一篇：http://www.sciencedirect.com/science/article/pii/S0377221707004274
2

Google：算法，将圆形装在矩形中 http://www.jstor.org/stable/4102107 此链接位于此堆栈溢出问题的正下方。 jstor.org 的论文详细阐述了一种贪婪的圆形装入矩形算法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接