问题描述
我正在寻找一些算法的指针,这些算法应允许平铺不重叠的不同大小的矩形.
I am looking for some pointers to algorithms that should allow to tile with no overlap different size rectangles.
给出一组不同大小的矩形,将它们平铺在H x W大小的区域上,不重叠.目标将是最大化使用的空间,或者反过来-最小化间隙区域.如果没有足够的空间,请继续使用相同大小的第二个区域,依此类推.
Given a set of different sized rectangles, tile them on an area of size H x W with no overlap. The objective would be to maximize the space used or conversely - minimize area of gaps. If there is not enough space, proceed on the second area of the same size and so on.
假定每个矩形的宽度和高度小于拼贴区域的相应尺寸.矩形不会旋转或以其他方式变形-即矩形的侧面是水平的还是垂直的.
It is assumed that each rectangle's width and height are smaller than respective dimensions of the tiling area. Rectangles are not rotated or otherwise transformed - i.e. their sides are either horizontal or vertical.
我不是在寻找完成的代码,只是想知道哪种方法/算法是解决该问题的最佳方法.
I am not looking for finished code, just curious what approaches/algorithms are the best to use to solve this problem.
推荐答案
最简单的方法是使用kd-tree将树细分为垂直和水平euklidian二维空间.然后,您可以将矩形打包到所创建的空间之一中,然后递归地细分树.在线有一个Jquery树形图插件示例. jQuery插件砌体可以做同样的事情,但它更像是一维装箱求解器. 2D箱式装箱要复杂得多,并且还可能意味着旋转矩形.这是打包光照图的示例: http://www.blackpawn.com/texts/lightmaps /default.html .
Most simple is to use a kd-tree to subdivide the tree into vertical and horizontal euklidian 2d space. Then you can pack a rectangle into one of the created space and recursively subdivide the tree. There is a Jquery treemap plugin example available online. The jquery plugin masonry can do the same but it's more like a 1d bin-packing solver. 2d bin-packing is much more complicated and can also mean to rotate rectangles. Here is an example for packing lightmaps: http://www.blackpawn.com/texts/lightmaps/default.html.
这篇关于平铺不同大小的矩形的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!