Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites

, 14 Jun 2011
Describes a fast algorithm to pack a series of rectangles of varying widths and heights into an enclosing rectangle of minimum size
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Diagnostics;
using System.Drawing;
using Mapper;

/// <summary>
/// Summary description for TestUtils
/// </summary>
public class TestUtils
{
    private static readonly int _nbrStatisticTypes = Enum.GetNames(typeof(SingleTestStats.StatisticType)).Length;

    /// <summary>
    /// Runs a performance test by generating a sprite with a number of images using a given IMapper object.
    /// </summary>
    /// <typeparam name="S"></typeparam>
    /// <param name="mapper"></param>
    /// <param name="images"></param>
    /// <param name="testStats">
    /// Results of the test. Pass in a reference to an ISingleTestStats object. That object will be updated with the stats.
    /// </param>
    public static void RunTest<S>(
        IMapper<S> mapper, IEnumerable<IImageInfo> images, ISingleTestStats testStats) where S : class, ISprite, new()
    {
        S spriteInfo = null;
        MapperStats mapperStats = new MapperStats();

        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();

        if (mapper is IMapperReturningStats<S>)
        {
            spriteInfo = ((IMapperReturningStats<S>)mapper).Mapping(images, mapperStats);
        }
        else
        {
            spriteInfo = mapper.Mapping(images);
        }

        stopWatch.Stop();
        long elapsedTickes = stopWatch.ElapsedTicks;

        int totalAreaAllImages =
            (from a in images select a.Width * a.Height).Sum();

        testStats.MapperType = mapper.GetType();
        testStats.TotalAreaAllImages = totalAreaAllImages;
        testStats.FinalSprite = spriteInfo;

        testStats.CandidateSpriteFails = mapperStats.CandidateSpriteFails;
        testStats.CandidateSpritesGenerated = mapperStats.CandidateSpritesGenerated;
        testStats.CanvasRectangleAddAttempts = mapperStats.CanvasRectangleAddAttempts;
        testStats.CanvasNbrCellsGenerated = mapperStats.CanvasNbrCellsGenerated;

        testStats.Efficiency = Efficiency(spriteInfo.Width, spriteInfo.Height, totalAreaAllImages);
        testStats.ElapsedTicks = elapsedTickes;

        // Statistics related to the input images

        testStats.ImageStats = new double[_nbrStatisticTypes];

        testStats.ImageStats[(int)SingleTestStats.StatisticType.Nbr_Images] = 
            images.Count();

        testStats.ImageStats[(int)SingleTestStats.StatisticType.Width_Standard_Deviation] = 
            StandardDeviation(from i in images select (double)i.Width);

        testStats.ImageStats[(int)SingleTestStats.StatisticType.Heigth_Standard_Deviation] = 
            StandardDeviation(from i in images select (double)i.Height);

        testStats.ImageStats[(int)SingleTestStats.StatisticType.Area_Standard_Deviation] = 
            StandardDeviation(from i in images select (double)Area(i.Width, i.Height));

        testStats.ImageStats[(int)SingleTestStats.StatisticType.Aspect_Ratio_Standard_Deviation] = 
            StandardDeviation(from i in images select (double)AspectRatio(i.Width, i.Height));

    }

    /// <summary>
    /// Returns the efficiency of a sprite, based on its widht, height and the total area of the images contained in it.
    /// </summary>
    /// <param name="spriteWidth"></param>
    /// <param name="spriteHeight"></param>
    /// <param name="totalImagesArea"></param>
    /// <returns></returns>
    public static float Efficiency(int spriteWidth, int spriteHeight, int totalImagesArea)
    {
        float spriteArea = spriteWidth * spriteHeight;
        float efficiency = totalImagesArea / spriteArea;

        return efficiency;
    }

    /// <summary>
    /// Returns the area, given a width and a height
    /// </summary>
    /// <param name="width"></param>
    /// <param name="height"></param>
    /// <returns></returns>
    public static int Area(int width, int height)
    {
        return width * height;
    }

    /// <summary>
    /// Returns the aspect ratio given a width and height.
    /// </summary>
    /// <param name="width"></param>
    /// <param name="height"></param>
    /// <returns></returns>
    public static double AspectRatio(int width, int height)
    {
        return ((double)width) / height;
    }


    /// <summary>
    /// Computes the standard deviation of a series of numbers.
    /// </summary>
    /// <param name="numbers"></param>
    /// <returns></returns>
    public static double StandardDeviation(IEnumerable<double> numbers)
    {
        int nbrNumbers = numbers.Count();

        if (nbrNumbers <= 1) { return 0; }
        
        double mean = numbers.Average();

        double sumDeviations = numbers.Sum(d => Math.Pow(d - mean, 2));

        double result = Math.Sqrt(sumDeviations / (nbrNumbers - 1));

        return result;
    }

    /// <summary>
    /// Takes an absolute file path starting with the drive letter (such as created by Server.Mappath)
    /// and returns the corresponding url (of the form file:///.....)
    /// </summary>
    /// <param name="filePath"></param>
    /// <returns></returns>
    public static string FilePathToUrl(string filePath)
    {
        return "file:///" + filePath.Replace('\\', '/').Replace(" ", "%20");
    }

}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Matt Perdeck
Web Developer
Australia Australia
Twitter: @MattPerdeck
Blog: mattperdeck.com
Current project: JSNLog JavaScript Logging Package
 
Matt has over 6 years .NET and SQL Server development experience. Before getting into .Net, he worked on a number of systems, ranging from the largest ATM network in The Netherlands to embedded software in advanced Wide Area Networks and the largest ticketing web site in Australia. He has lived and worked in Australia, The Netherlands, Slovakia and Thailand.
 
He recently wrote a book, ASP.NET Performance Secrets (www.packtpub.com/asp-net-site-performance-secrets/book) in which he shows in clear and practical terms how to quickly find the biggest bottlenecks holding back the performance of your web site, and how to then remove those bottlenecks. The book deals with all environments affecting a web site - the web server, the database server and the browser.
 
Matt currently lives in Sydney, Australia. After 2 years at Readify, he now works at the global professional services company PwC. His current contract ends at 29 June 2014.
Follow on   Twitter   Google+

| Advertise | Privacy | Mobile
Web04 | 2.8.140821.2 | Last Updated 14 Jun 2011
Article Copyright 2011 by Matt Perdeck
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid