一种2D装箱算法 | a house in the woods

前言

前段时间在做项目的时候，遇到某组图标需要从iconfont改为使用png的情况。这种情况，由于图标本身是比较小的而数量又比较多，为了减少大量http请求的成本，需要把这些图标做成一张sprite图。在不劳烦UI的同学的情况下，那我自行去生成了。
本身就有一些现成的网站有这类的服务了，如toptal.com；命令行的话，有spritesmith。其中里面的有一个叫binary-tree的排列方式引起我的兴趣，查看spritesmith的源码，他其实是用了bin-pack提供的算法的。下面开始介绍这种算法。

算法思路

1. 把图片数组按照它们的面积大小，从大到小排列，并把最大的那张图片放到左上角，并把他的x,y,width,height作为初始root的数值
2. 遍历所有的图片，一个个对他们进行放置。
3. 放置的规则是从root出发，
   1. 如果当前遍历的图片的width和height都不大于当前node（条件1）， 把当前的遍历的图片A放在node的左上角, 然后进行分裂操作，给node添加down和right两个子node, 分别为A的右上方到node的右下方和
      A的左下方到node的右下方两个区域。
   2. 第1步中用的是当前node这个词的原因是，假如一个node（包括root）分裂过，那么第一步就会从他的down或者right的子node中，寻找具有足够空间放置的一方（是一个递归的过程）。
   3. 假如不满足条件1，root就会进行grow操作，grow在放置新图片在右方还是下方的问题上会考虑两个因素：
      1. 如果新图片的宽小于root的宽表示可以向下增长，高小于root的高，表示可以向右增长。
      2. 第二个是非必要因素，主要是遵循增长以后root的宽高，差距能缩小的原则。假设第1步显示两个方向都允许的，但如果往右增长，高依然是大于宽的，那就会优先往右增长。增长分别就相当于在root的右上角和左下角，放置新的那个图片。同时根据放置的位置，更新root的right或者down 子node的位置和大小。

想法

在bin-pack的github上也提到了这个算法提供的并不是最优解，但是算法十分简洁，效果也能在使用它的库中得到体现，可以说是相当实用的，也给我们在解决这类问题的时候，提供了一个行之有效的方法。