Click here to Skip to main content
11,408,835 members (63,609 online)
Click here to Skip to main content
Add your own
alternative version

Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites

, 14 Jun 2011 CPOL
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 Mapper;
using System.Drawing;

/// <summary>
/// Version of MapperOptimalEfficiency that produces additional stats
/// </summary>
public class MapperOptimalEfficiency_AdditionalStats<S> : MapperOptimalEfficiency<S> where S : class, ISprite, new()
{
    ICanvas _canvas = null;
    List<IterationStats> _currentMappingIterationStats = null; 

	public MapperOptimalEfficiency_AdditionalStats(ICanvas canvas)
            : base(canvas)
    {
        _canvas = canvas;
    }

    /// <summary>
    /// See MapperIterative_Base
    /// </summary>
    /// <param name="canvas"></param>
    /// <param name="cutoffEfficiency"></param>
    /// <param name="maxNbrCandidateSprites"></param>
    public MapperOptimalEfficiency_AdditionalStats(ICanvas canvas, float cutoffEfficiency, int maxNbrCandidateSprites)
        : base(canvas, cutoffEfficiency, maxNbrCandidateSprites)
    {
        _canvas = canvas;
    }

    /// <summary>
    /// Does a mapping with the given images and returns the resulting stats.
    /// </summary>
    /// <param name="images"></param>
    /// <returns></returns>
    public DetailedSingleTestStats GetMappingStats(IEnumerable<IImageInfo> images)
    {
        // Mapping will call MappingRestrictedBox, which will add records to this collection.
        _currentMappingIterationStats = new List<IterationStats>();

        DetailedSingleTestStats stats = new DetailedSingleTestStats();
        TestUtils.RunTest<S>(this, images, stats);

        stats.Iterations = _currentMappingIterationStats;

        return stats;
    }

    /// <summary>
    /// This method is called by MapperOptimalEfficiency_AdditionalStats for each iteration
    /// </summary>
    /// <param name="images"></param>
    /// <param name="maxWidth"></param>
    /// <param name="maxHeight"></param>
    /// <returns></returns>
    protected override S MappingRestrictedBox(
        IOrderedEnumerable<IImageInfo> images, int maxWidth, int maxHeight, ICanvasStats canvasStats,
        out int lowestFreeHeightDeficitTallestRightFlushedImage)
    {
        S intermediateSpriteInfo = 
            base.MappingRestrictedBox(images, maxWidth, maxHeight, canvasStats, out lowestFreeHeightDeficitTallestRightFlushedImage);

        IterationStats stats = null;
        CanvasWritingStepImages canvasBLFStats = _canvas as CanvasWritingStepImages;

        List<ImagePlacementDetails> imageDetails = null;
        if (canvasBLFStats != null) { imageDetails = new List<ImagePlacementDetails>(canvasBLFStats.ImageDetails); }

        if (intermediateSpriteInfo != null)
        {
            stats =
                new IterationStats
                {
                    Result = IterationResult.Success,
                    MaxCanvasWidth = maxWidth,
                    MaxCanvasHeight = maxHeight,
                    IntermediateSpriteWidth = intermediateSpriteInfo.Width,
                    IntermediateSpriteHeight = intermediateSpriteInfo.Height,
                    ImageDetails = imageDetails
                };
        }
        else
        {
            stats =
                new IterationStats
                {
                    Result = IterationResult.Failure,
                    MaxCanvasWidth = maxWidth,
                    MaxCanvasHeight = maxHeight,
                    ImageDetails = imageDetails
                };
        }

        _currentMappingIterationStats.Add(stats);

        // Clear out the current image details as kept by the canvas, otherwise we get the same details again next time.
        if (canvasBLFStats != null) { canvasBLFStats.ImageDetails.Clear(); }

        return intermediateSpriteInfo;
    }

    /// <summary>
    /// </summary>
    /// <param name="images"></param>
    /// <param name="maxWidth"></param>
    /// <param name="maxHeight"></param>
    /// <returns></returns>
    protected override bool CandidateCanvasFeasable(
        int canvasMaxWidth, int canvasMaxHeight, int bestSpriteArea, int totalAreaAllImages,
        out bool candidateBiggerThanBestSprite, out bool candidateSmallerThanCombinedImages)
    {
        bool isFeasable =
            base.CandidateCanvasFeasable(
                canvasMaxWidth, canvasMaxHeight, bestSpriteArea, totalAreaAllImages,
                out candidateBiggerThanBestSprite, out candidateSmallerThanCombinedImages);

        IterationStats stats = null;

        if (candidateBiggerThanBestSprite)
        {
            stats = new IterationStats
            {
                Result = IterationResult.BiggerThanBestSprite,
                MaxCanvasWidth = canvasMaxWidth,
                MaxCanvasHeight = canvasMaxHeight
            };
        }
        else if (candidateSmallerThanCombinedImages)
        {
            stats = new IterationStats
            {
                Result = IterationResult.SmallerThanCombinedImages,
                MaxCanvasWidth = canvasMaxWidth,
                MaxCanvasHeight = canvasMaxHeight
            };
        }

        if (stats != null)
        {
            _currentMappingIterationStats.Add(stats);
        }

        return isFeasable;
    }
}


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 | Terms of Use | Mobile
Web03 | 2.8.150414.5 | Last Updated 14 Jun 2011
Article Copyright 2011 by Matt Perdeck
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid