矩形中的圆填充算法
我需要一种打包算法,可以将一组不同半径的圆(如果这些圆适合的话)放入矩形中。我在 Wikipedia 和其他网站上看到过各种页面,但实现本身太复杂或者只是一个数学定理,我都没有经验或知识可以利用。
有人问了这个问题,这是一个相反的问题——我需要矩形中的圆,反之亦然,我更喜欢 Java,而不是 MATLAB,尽管我想如果有必要我可以移植它。
谢谢!
编辑:
我不需要找到适合圆圈的最小矩形,我只需要知道圆圈是否适合具有指定尺寸的给定矩形。
I need a packing algorithm that fits a set of circles of varying radii, if the circles fit, in a rectangle. I've seen various pages on Wikipedia and other sites, but the implementation itself is either too complicated or simply a mathematical theorem, neither of which I have the experience or knowledge to utilize.
Someone asked this question, which is sort of the inverse--I need circles in rectangles not vice versa, and I would prefer Java, not MATLAB, though I suppose if necessary I could port it.
Thanks!
EDIT:
I don't need to find the smallest rectangle in which the circles would fit, I just need to know if the circles would fit within a given rectangle with specified dimensions.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
谷歌:算法,将圆包装在矩形中
http://www.jstor.org/stable/4102107
显示在这个堆栈溢出问题的正下方。
jstor.org 论文阐述了矩形打包算法中的贪心圆。
Google: algorithm, pack circles in rectangle
http://www.jstor.org/stable/4102107
Shows up right underneath this stack overflow question.
The jstor.org paper spells out a greedy circles in rectangle packing algorithm.
这个问题似乎与装箱密切相关,所以我怀疑它是 NP 困难的。所以不幸的是,我认为没有一个好的算法可以有效地解决这个问题(又名非暴力)。
我什至不认为有一个好的、简单的、贪婪的方法来接近它。
如果您能够访问的话,已经有许多关于该主题的研究论文。这是一个: http://www.sciencedirect.com/science/article/pii/S0377221707004274
This problem is appears heavily related to bin packing and so I suspect it is NP-hard. So unfortunately I don't think there's a good algorithm for solving this efficiently (aka non-brute force).
I don't even think there's a good, simple, greedy way of approaching it.
There have been many research papers written on the subject though if you have access to them. Here is one: http://www.sciencedirect.com/science/article/pii/S0377221707004274