平铺不同大小的矩形 [英] Tiling different size rectangles

问题描述

我正在寻找一些算法的指针，这些算法应允许平铺不重叠的不同大小的矩形.

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.

这篇关于平铺不同大小的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！