快速优化建设CSS精灵矩形包装算法

简介
本文介绍了一种快速算法包了一系列不同成一个单一的封闭矩形的宽度和高度的矩形，没有重叠的方式，最大限度地减少浪费的空间，在封闭的矩形金额。一个算法的实现是在下载，伴随着一个网站，以图形显示如何一步步到达最佳的封闭矩形的算法。重要的是产生
有一个这样的算法。
，那肯定是可能的手动相结合的图像与图形程序。但每次添加或删除的图像，你必须手动重做精灵。要好得多精灵自动生成，坐落于飞在页面加载时。然而，这意味着你想有一个快速算法生成精灵，即使你随后的页面加载缓存的结果。
此外，你想包的方式，最大限度地减少精灵的整体规模在sprite图像的算法 - 尺寸越小，浏览器加载雪碧和更少的带宽，你承担的花费的时间少:{S0}
为了简化事情有点，你能想到的矩形，和作为一个封闭的矩形雪碧图像。它比成为一个发现的最小面积（宽x高），您可以在其中包所有的矩形封闭矩形的问题。本文所述的矩形包装算法的设计，这样做比较快，因此可用于动态生成的精灵，并做一个合理的工作发现的最小的封闭矩形。需要注意的是不能保证生成绝对最好的封闭矩形，每次，因为这将需要很长时间。
哦，顺便说一下，{A2}。这样，我知道人们欣赏我的工作。目录{A3}{A5}{A6}{A7}{A8}{A9}安装
下载包含与一个Visual Studio 2010解决方案:一个简单的ASP.NET网站 - 运行此看到图形，如何一步的算法一步到达最好的封闭的矩形。你会看到各种参数表单 - 这是最简单的运行与默认值的第一个，然后实验了一下。完整说明的形式提供。测试现场将运行得更快，在发行模式，而不是调试模式，如果你编译。A类项目包含代码执行本文中所描述的矩形打包机的映射。平凡解{A10}
有一个关于如何打包成一个封闭的矩形矩形的几个琐碎的解决方案:你可以将所有的矩形字符串水平，像这样:
这是非常简单和快速，实际上是最佳的，如果所有的矩形有相同的高度。或者你可以将所有矩形串在一起垂直，像这样:
{S2}
这也很简单，快速，而且实际上是最优的，如果所有矩形的宽度相同。
然而，这些解决方案留下了很多浪费的空间时，不同的宽度和高度的矩形。他们也有点沉闷。因此本文的其余部分主要集中在一个解决方案，并最大限度地减少浪费的空间，不同的宽度和高度的矩形，这也是合理的快速和简单。 {A11}基本算法
包装成一个封闭矩形的最小尺寸的矩形的基本算法描述，例如，理查德E.科尔夫的文件:{A12}。排序矩形的高度，最大高度第一。开始与封闭的矩形，它是作为最高矩形的高，并具有无限的宽度。由一个放置在封闭矩形的矩形，开始矩形的最高与最低的矩形结束。将尽可能留下每个矩形。如果有几个左边的大多数地方，使用最高的国家之一。例如:
{S3}
{S4}的
{五}
{中六}
{七}使封闭的矩形，矩形所采取的总宽度等于的宽度。也就是说，将封闭的矩形的右边缘到左，直到它触及的最右边的矩形的右边缘。这样一来，封闭的矩形没有比需要的更广泛的。你管理所有矩形放置在封闭的矩形？在这种情况下:如果你已经有了现在是封闭的矩形最小"; successfulquot封闭矩形到目前为止，这个封闭的矩形至今保存最好的封闭矩形。 它的时间尝试一个更小的封闭矩形 - 减少由一个封闭的矩形的宽度。不过，如果你没有管理的地方所有矩形，封闭的矩形显然太小。在这种情况下，增加一个封闭的矩形的高度。
注意效果，减少宽度，增加高度，意味着我们正在测试的封闭低而宽的矩形高而窄的范围。例如，在宽度已经下降了几次，高度增加，你可能会收到以下顺序:
{S8}
{S9}
{S10}
{S11}
{S12}如果你现在已经封闭的矩形（宽x高）的总面积比你要尝试把里面的所有矩形的总面积较小，那么这显然不是一个可行的封闭矩形。直到你得到一个可行的封闭矩形增加一个高度。然后进入下一步。如果你已经有了现在是封闭的矩形大于最好的封闭矩形到目前为止，有没有在这个封闭的矩形测试点。宽度减1，回到第7步，以确保它现在不能太小。否则转到下一步。如果您的新的封闭矩形比最宽的矩形窄的，你可以停下来，并报告最好的封闭矩形迄今发现的。这是因为算法不增加封闭的矩形的宽度，最宽的矩形，如果不适合，显然没有封闭的矩形测试点。现在，您的新的封闭矩形既不太小也不太大，回到步骤3如果你可以把它里面的所有矩形。
该算法已实施类MapperOptimalEfficiency方法映射在下载的映射项目。
后来，我们将会看到这个基本算法，可快了很多。但首先，让我们来看看如何放置在封闭的矩形的矩形，并高于一切如何保持那里已经是矩形的轨道，所以我们不重叠在现有的矩形的一个新的矩形。{A13}配售不重叠的其它矩形在一个给定的封闭矩形的矩形
上面的基本算法的第3步说quot;由一个放置在封闭矩形矩形，具有最高的矩形，并开始与最低的矩形结束。将尽可能留下每个矩形。如果有几个左边的最地点，使用最高的one.quot;
为了找到最左边的/最高位置与给定的宽度和高度的矩形可以不重叠其他矩形，我们需要使用一些数据结构来存储封闭的矩形范围内，现在占领。这个数据结构必须使其既简单（即不容易出错），并快速找到最左边的/最高位置可放置的矩形。
，这将有可能在封闭的矩形的每个像素单元中使用两个布尔值的二维数组。每个布尔表示的像素是否是由一个矩形或免费占用。然而，你需要找到一个矩形的地方时，访问大量的像素，使这个选项简单，但效率低下。
另一种方法是将存储在封闭的矩形的宽度/高度和每个矩形的X / Y偏移。这个数据结构会比二维像素阵列的个别项目要少得多，但最左边/最高足够的空间，这竟然是非常复杂或很慢的数据结构的一个给定的矩形的位置。
我想出了解决方案是使用一个动态的两维数组占用/免费布尔值，而是存储每一列和每一行的高度与宽度，所以列和行数可保持在最低限度。这最大限度地降低复杂性和需要访问（因此所花费的时间）的细胞数量。这里是如何工作时加入矩形（白细胞无人居住，浅绿色的细胞都被占用，墨绿色的细胞刚刚被占领的最后添加矩形）:起初，有一排同一高度封闭的矩形，并与封闭的矩形的宽度相同的一列。这意味着只有一个细胞。
{S13}当加入的第一个矩形，找到最左边的/最高的细胞是容易的，因为只有一个。也很容易建立，它是足够大的矩形。所以我们继续前进，放置在矩形的左上角上的细胞。
我们现在有一个细胞，这部分是被占领的部分空置。然而，一个细胞可以在只有一个国家。为了解决这个问题，分裂单列单列，所以我们得到了四个单元，占用或空置:
{S14}添加第二个矩形的时间。首先，检查最左边的列。访问在这列从最上面的底部最的所有细胞，直到找到一个免费的细胞。然后看看是否可以放置矩形。
原来是在最左边的列自由的单元格，但没有足够的垂直空间放置矩形。因此，移动到右侧立柱，经过相同的步骤，与最左边的一栏。
有了这个第二列，最上面的细胞是免费的，它是足够大的矩形，这样很容易。有放置的矩形。由于是第一个矩形的情况下，这里太矩形比细胞小 - 领先的一个细胞，是部分被占领，部分空置。因此，拆分行和列的位置，以确保细胞是所有细胞都占用或空置再次。请注意，作为一个结果，现在是一个被占领的第一个矩形的细胞分裂成两个，这是罚款。
{S15}第三个矩形经过完全相同的过程。然而，因为这个矩形是有点低，有足够的空间，在矩形的最左边的列单元格。再次，行和列相交的细胞分裂，以确保所有细胞都占用或空置。
{S16}第四矩形经过相同的过程。没有足够的垂直空间，在最左边的一栏遗留下来的，所以要尽量在其右侧之一。在该列中的自由的最高细胞原来要高到足以容纳矩形，但它是不够广泛。所以测试朝着正确的列，看看是否有足够的游离细胞，以适应矩形。事实证明，原列的权利在一起，有足够的水平，为矩形空间，所以可以放在矩形使用两种细胞。再次，行和列被分割，以确保所有细胞都被占用或空置。
{S17}第五矩形，再检查列由左到右。第二列有一个免费的细胞，但没有足够的垂直的矩形空间。第三列有两个独立的游离细胞，但既不是足够高在自己的权利，也可以结合另一个单元格的垂直矩形找到足够的垂直空间。
在第四列中，有一个免费的细胞，这本身就是既不高也不足够宽的矩形。因此，检查的细胞列的权利，并在下面的行的细胞，如果有足够的自由细胞可以结合起来，以适应矩形。在这种情况下，原来是有可能的。同样，行和列的分裂发生，以确保所有细胞都被占用或空置。
{S18}
你可以看到很多运行的网站，在下载中更多的例子（和矩形）。这也说明不是每一个矩形可放置的情况。
找到一个矩形可以放在最左边/最高细胞和检查邻近细胞等的代码是在Canvas类在下载的映射项目。二维动态数组是实施中的DynamicTwoDimensionalArray类。因为它是大量使用，这个类是高度优化的性能，尤其是当分裂的行和列。{A14}基本算法的改进
在研究测试测试网站下载所产生的案件，进行了以下改进变得清晰。在下载代码，这些改进工作。我没有找到这些文献中，让你阅读，他们在这里第一次:{A16}{A17}{A18}封闭矩​​形宽度减少时，充分增加身高
有以下基本算法的迭代过程中产生的封闭矩形的外观:
{S19}
根据基本的算法，你应该减少1封闭矩形的宽度，然后再次尝试将所有的矩形。然而，如果你只是宽度减少1，你知道，暗绿色的长方形，对坐在右手边境封闭的矩形不能被放置在任何地方，所以未来的尝试，肯定会失败。
此外，算法说增加1发生故障时，封闭的矩形的高度。然而，由于暗绿色的长方形高10个像素，你知道，由1增加是不够的。所以，以下的基本算法，必将创造10个失败的尝试，将所有的矩形，这是昂贵的和不必要的的。
的优化是记录最高的，对坐在右手边的封闭矩形的矩形的高度。如果你成功地把所有矩形和矩形的宽度减少1，然后也增加最高的权利刷新矩形的高度封闭的矩形的高度。这给了该算法的一个机会找到新的专为最高权利刷新在新的封闭矩形的矩形:
{S20}{A19}失败后，将所有矩形，充分增加身高
在看看下面的序列。这里的算法地方4矩形，但失败的地方第五矩形。1234
放置矩形失败
{S21}
{S22}
{S23}
{S24}
{S25}
此故障后，基本算法会增加1个封闭的矩形的高度，并再次尝试放置的矩形。然而，增幅仅为1，第4矩形可能被放置在完全相同的位置，再次导致失败的地方第五矩形。算法将增加1高度又再次尝试，可能造成相同的情况下，等这一切都徒劳无功的尝试，采用了大量的时间。
，而不是增加1高度，它需要由更小的提高:不能放在矩形的高度;需要增加，以确保第4矩形将安排不同的 - 这将使该算法至少有机会的地方第五矩形封闭的矩形的高度。
挑选最小的两个，你更可能是用尽可能小的封闭矩形风。
弄清楚2点中提到的高度上面是不是所有的困难，当你意识到，该算法试图在最左边的列的第一个地方每个矩形，如果失败了，移动到右侧立柱并再次尝试等，每一次失败，放置在一个列矩形，这是因为在该列底部的可用空间低于矩形本身 - 是一个免费的高度赤字。
例如，第二个矩形，在第一列的自由高度赤字是30px:
{S26}
也就是说，如果已封闭的矩形30px较高，第二个矩形可以被放置在最左边的一栏。
同样，在最左边列第三的矩形高度的赤字是25px，并在第二列是15px。因此，如果已封闭的矩形15px较高，第三个矩形可以被置于不同的:
{S27}
在最左边的列第四矩形的高度赤字的是10px。因此，如果已封闭的矩形10px高，有可能被第四矩形放置在第一列:
{S28}
我们要增加的最低要求，以确保可以安排不同的矩形封闭矩形的高度。在这里，所有列的所有矩形的最小自由高度赤字是10px（适用于在最左边的列第四的矩形）。看到第五未能放置的矩形，大于10px高，我们需要增加10px封闭的矩形的高度有任何放置在下次尝试的第五个矩形的希望:12345
{S29}
{S30}
{S31}
{S32}
{S33}
这意味着，为了防止大量失败的封闭矩形，该算法只需要保持的最小自由高度赤字的轨道，当它试图一列放置在一个矩形。然后当它失败的地方一个矩形，它需要封闭的矩形的高度，最小的自由高度赤字增加 - 或如果这较小，不能放在矩形的高度。
这种优化不能保证，导致在下次尝试成功的封闭矩形。例如，在新的高​​度，封闭的矩形可能大于最好的封闭矩形到目前为止，在这种情况下，该算法将开始减少它的宽度。正因为如此，它可能无法在未来尝试，因为减少宽度所有矩形的地方。这种优化做的是防止了很多的尝试没有成功的希望。{A20}贸易关廉政高速封闭矩形的大​​小
如果你决定，你能忍受浪费的空间水平的一种方式，以减少产生封闭的矩形的时间是告诉代码停止试图得到一个更小的封闭矩形，一旦达到这一水平。
以提高速度的另一种方式是告诉停止后，它已经找到了成功的封闭矩形，它可以包含所有矩形的一定数量的算法。你可能会设置一个或两个限制。这将是有吸引力的，如果你发现，这种方式不够好，几乎可以保证速度提升的同时，你通常得到的结果。
为了让您作出这些选择，第二个构造为MapperOptimalEfficiency类提供了额外的参数，设置这两个削减取舍。{A21}软件接口的矩形包装机
本文中所描述的矩形打包机已在下载的映射项目实施。它暴露了一个良好定义的接口向外界。试验现场，使用该接口。下面是一个接口的描述，使其更容易研究的代码，或在自己的项目中使用的代码。
你会发现该代码是指，而不是矩形和封闭矩形图像和精灵。这是因为它被视为书面（还未完）项目的基础上飞的精灵发电机自动化的一部分。接口
为了使代码容易扩展使用C＃接口，软件接口定义。这样的话，你可以提供自己的实现，为一类，同时重用其他类。矩形包装机是指使用IMapper C＃接口。它暴露了一个单一的方法映射。这种方法需要实施IImageInfo对象的集合，并返回一个对象实施ISprite。换句话说，你给它要合并成一个精灵的图像集合，并产生对你的雪碧。IImageInfo只是暴露了图像的宽度和高度 - 这是所有矩形打包机的需求。请注意，它本身并不代表图像的URL，这就是所谓的IImage IImageInfo，而不是一个真正的形象，因为System.Drawing命名空间中已经包含一个Image类。ISprite对象的方法映射返回，只是公开的宽度，高度和面积的精灵，在精灵中的图像的集合。 IImageInfo，它并不由自己定义一个形象，因为代码实现了一个矩形，而不是与物理图像的矩形打包机。因为我们需要存储在X和Y在位于每个IImageInfo的sprite偏移，这个集合使用IMappedImageInfo，公开IImageInfo及其X和Y偏移。
因此，下面的C＃接口描述矩形的封隔器的完整的软件界面:

public interface IMapper<S> where S : class, ISprite, new()

{

    S Mapping(IEnumerable<IImageInfo> images);

}



public interface IImageInfo

{

    int Width { get; }

    int Height { get; }

}



public interface ISprite

{

    // Width of the sprite

    int Width { get; }



    // Height of the sprite

    int Height { get; }



    // Area of the sprite

    int Area { get; }



    // Holds the locations of all the individual images (treated as rectangles)

    // within the sprite (treated as the enclosing rectangle).

    List<IMappedImageInfo> MappedImages { get; }



    // Adds an image to the SpriteInfo, and updates

    // the width and height of the SpriteInfo.

    void AddMappedImage(IMappedImageInfo mappedImage);

}



public interface IMappedImageInfo

{

    int X { get; }

    int Y { get; }

    IImageInfo ImageInfo { get; }

}

	string inputDirectory = @"D:\Test\Icons\32x32";

	string outputSprite = @"D:\Test\Sprites\Icons_32x32.png";

 

	Canvas canvas = new Canvas();

	MapperOptimalEfficiency<Sprite> mapper = new MapperOptimalEfficiency<Sprite>(canvas);

	Dictionary<ImageInfo, Image> images = new Dictionary<ImageInfo, Image>();

 

	foreach (string fileName in Directory.EnumerateFiles(inputDirectory, "*.png", SearchOption.AllDirectories))

	{

		Image image = Image.FromFile(fileName);

		ImageInfo info = new ImageInfo(image.Width, image.Height);

		images.Add(info, image);

	}

 

	Sprite output = mapper.Mapping(images.Keys);

	Bitmap bmp = new Bitmap(output.Width, output.Height, PixelFormat.Format32bppArgb);

	Graphics g = Graphics.FromImage(bmp);

 

	foreach (var item in output.MappedImages)

	{

		ImageInfo info = (ImageInfo)item.ImageInfo;

		Image image = images[info];

		g.DrawImage(image, item.X, item.Y);

	}

 

	bmp.Save(outputSprite, ImageFormat.Png);