Vla*_*ecs 5 algorithm optimization tiling
我正在寻找一些指向算法的指针,这些算法应该允许平铺不重叠不同大小的矩形.
给定一组不同大小的矩形,将它们平铺在大小为H x W且没有重叠的区域上.目标是最大化使用的空间或相反 - 最小化间隙面积.如果没有足够的空间,请继续进行相同大小的第二个区域,依此类推.
假设每个矩形的宽度和高度小于拼接区域的相应尺寸.矩形不会旋转或以其他方式转换 - 即它们的边是水平的或垂直的.
我不是在寻找完成的代码,只是好奇什么方法/算法最适合用来解决这个问题.
最简单的是使用 kd 树将树细分为垂直和水平欧氏二维空间。然后，您可以将一个矩形打包到创建的空间之一中，并递归地细分树。在线有一个 Jquery 树形图插件示例。jquery 插件 masonry 可以做同样的事情，但它更像是一个一维装箱求解器。2d 装箱要复杂得多，也可能意味着旋转矩形。以下是打包光照贴图的示例：http://www.blackpawn.com/texts/lightmaps/default.html。