java – 给定一些可以旋转的矩形,找到一个最小面积的封闭矩形
|
因此,我正在尝试实现一种算法,该算法将许多矩形作为输入,并尝试将它们打包成最小面积的矩形.矩形都可以旋转90度.
我意识到这类似于bin打包问题,但是我无法找到一个考虑轮换的好算法.我发现了一篇论文,在here篇讨论了这个问题,虽然我理解文章本身,但我希望能找到更简单的东西. 有什么建议？ -编辑- 我想我早些时候误解了这个问题.我们给出了许多矩形,使得每个矩形可以旋转90度.我们需要找到一个适合所有给定矩形的矩形,这样就不会有两个矩形重叠,同时最小化封闭矩形的面积. 我在这里遇到的问题是我们被要求找到最小值,而不是给出一个封闭的矩形,并检查给定的矩形是否适合或类似的东西. 解决方法
我使用这个算法得到了很好的结果：
http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy 编辑： 我提供的链接中描述的算法将给出一个“是”或“否”的答案,关于是否可以将给定的矩形集打包到特定的封闭矩形中.要查找最小的包围矩形,可以重复运行算法.基本上,计算包围矩形的下限和上限,然后进行二分查找以找到落在这些边界内的最小解.我假设封闭的矩形在一个维度上是固定的大小(即,宽度是恒定的,寻找最小长度,反之亦然).如果允许包围矩形的宽度和长度都变化,那么它就更难了,这可能不起作用. 计算下限和上限的简单(但天真)方法如下： 下界 – 最好的情况是所有矩形都可以完美打包而不会浪费任何空间.因此,对所有输入矩形的面积求和,并计算该区域所需的包围矩形长度. 上限 – 最坏的情况是每个矩形必须打包在一个单独的“行”上,因此对于每个输入矩形,计算min(宽度,高度)并求和(即假装输入矩形使用最小值相互堆叠)每个输入的宽度或高度,使得输入的另一个维度不超过包围矩形的宽度). 如果你更努力地工作,你可以显着改善下限和上限以减少搜索空间,但这应该给你起点. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |