以最佳方式将矩形装配在一起
我想知道是否有人知道任何适合将 N 个未知大小的矩形组装成可能的最小包含矩形的算法。
我所说的最佳是指减少生成的包含矩形中剩余的空白量。
我想用它从一系列图像生成 css 精灵。
非常感谢，
伊恩
I was wondering if anyone knows of any algorithms suited to fitting together N number of rectangles of unknown size into the smallest possible containing rectangle.
By optimal I mean with reducing the amount of white space left over in the resulting containing rectangle.
I would like to use this to generate css sprites from a series of images.
Many Thanks,
Ian
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为你所描述的是“二维装箱”问题的一个变体。唯一的区别是您拥有这些项目并正在尝试找到最小的矩形。
这篇调查文章是一个好的开始。
I think what you describe is a variant of the "two dimensional bin packing" problem. The only difference is that you have the items and are trying to find the smallest rectangle.
This survey article is a good start.
通过将图像打包成方形纹理和西蒙的回答我到达此链接http://code.activestate.com/recipes/442299/
我没有检查食谱，但它似乎允许使用非方形容器。
Through packing images into square texture and Simon's answer I got to this link http://code.activestate.com/recipes/442299/
I did not check the recipe, but it seems to allow using non-square containers.
保证最优解的唯一方法就是暴力破解答案。当您有多个矩形并允许旋转时，这对于个人计算机来说很快就会变得难以管理。
维基百科有一篇关于打包问题的好文章
http://en.wikipedia.org/wiki/Packing_problem
The only way to guarantee and optimal solution is to brute force the answer. This quickly becomes unmanagable for personal computers when you have several rectangles, and allow for the possibility of rotation.
Wikipedia has a good article on packing problem
http://en.wikipedia.org/wiki/Packing_problem
这是快速打包算法的一个很好的描述 - http://www.codeproject。 com/KB/web-image/rectanglepacker.aspx
Here is a good description of a fast packing algorithm - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx