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.Text;
using Mapper;
using System.Drawing;
using System.Web;
using System.Drawing.Imaging;
using System.IO;


/// <summary>
/// This version of Mapper.Canvas writes an image to the web site's root folder
/// after each time a rectangle is added to the canvas.
/// </summary>
public class CanvasWritingStepImages : Canvas
{
    private const string _canvasFolderName = "canvasimages";
    
    // Used to give each canvas image a unique name.
    private static int _sequenceNbr = 0;

    private List<ImagePlacementDetails> _imageDetails = null;

    private int _nbrRectanglesAdded = 0;
    private int _nbrRedimensions = 0;

    private int _canvasWidth = 0;
    private int _canvasHeight = 0;

    private int _imageZoom = 1;
    private bool _showCanvasImages = false;

    /// <summary>
    /// The images that have been generated.
    /// </summary>
    public List<ImagePlacementDetails> ImageDetails { get { return _imageDetails; } }

    public CanvasWritingStepImages(int imageZoom, bool showCanvasImages)
    {
        _imageZoom = imageZoom;
        _showCanvasImages = showCanvasImages;

        ResetCanvasImagesFolder();
    }

    public override void SetCanvasDimensions(int canvasWidth, int canvasHeight)
    {
        // Don't use a canvas size that is too big, otherwise the images get too big

        if (canvasWidth > 500) { canvasWidth = 500; }
        if (canvasHeight > 500) { canvasHeight = 500; }

        _canvasWidth = canvasWidth;
        _canvasHeight = canvasHeight;

        _nbrRedimensions++;
        
        base.SetCanvasDimensions(canvasWidth, canvasHeight);
        _imageDetails = new List<ImagePlacementDetails>();
    }

    /// <summary>
    /// See ICanvas.
    /// </summary>
    public override bool AddRectangle(int width, int height, out int xOffset, out int yOffset, out int lowestFreeHeightDeficit)
    {
        bool rectangleAdded = base.AddRectangle(width, height, out xOffset, out yOffset, out lowestFreeHeightDeficit);

        // ------------

        Rectangle rectAdded = new Rectangle(xOffset, yOffset, width, height);

        if (rectangleAdded)
        {
            _nbrRectanglesAdded++;

            if (_showCanvasImages)
            {
                int bitmapWidth = _canvasWidth * _imageZoom;
                int bitmapHeight = _canvasHeight * _imageZoom;
                using (Bitmap bitmap = new Bitmap(bitmapWidth, bitmapHeight))
                {
                    using (Graphics graphics = Graphics.FromImage(bitmap))
                    {
                        int xImageOffset = 0;

                        for (int x = 0; x < CanvasCells.NbrColumns; x++)
                        {
                            int yImageOffset = 0;
                            for (int y = 0; y < CanvasCells.NbrRows; y++)
                            {
                                int cellWidth = CanvasCells.ColumnWidth(x);
                                int cellHeight = CanvasCells.RowHeight(y);
                                Rectangle rectCell = new Rectangle(xImageOffset, yImageOffset, cellWidth, cellHeight);
                                bool newlyOccupied = rectAdded.Contains(rectCell);

                                DrawRectangle(
                                    graphics,
                                    cellWidth * _imageZoom, cellHeight * _imageZoom,
                                    xImageOffset * _imageZoom, yImageOffset * _imageZoom,
                                    CanvasCells.Item(x, y).occupied,
                                    newlyOccupied);

                                yImageOffset += CanvasCells.RowHeight(y);
                            }

                            xImageOffset += CanvasCells.ColumnWidth(x);
                        }

                        string imageFileName = string.Format(_canvasFolderName + "/canvas_{0}_{1}_{2}.png", _nbrRedimensions, _nbrRectanglesAdded, _sequenceNbr);
                        _sequenceNbr++;
                        string imageServerFileName = HttpContext.Current.Server.MapPath(imageFileName);

                        ImagePlacementDetails singleImageDetails = new ImagePlacementDetails()
                        {
                            Width = width,
                            Height = height,
                            XOffset = xOffset,
                            YOffset = yOffset,
                            ImageUrl = imageFileName
                        };

                        _imageDetails.Add(singleImageDetails);

                        bitmap.Save(imageServerFileName, ImageFormat.Png);
                    }
                }
            }
        }
        else if (_showCanvasImages)
        {
            // Rectangle could not be placed. Show it on its own to make it easier to see how it relates to the canvas.

            int bitmapWidth = width * _imageZoom;
            int bitmapHeight = height * _imageZoom;
            using (Bitmap bitmap = new Bitmap(bitmapWidth, bitmapHeight))
            {
                using (Graphics graphics = Graphics.FromImage(bitmap))
                {
                    DrawRectangle(
                        graphics, bitmapWidth, bitmapHeight, 0, 0, true,
                        true);

                    string imageFileName = string.Format(_canvasFolderName + "/canvas_{0}_{1}_{2}.png", _nbrRedimensions, _nbrRectanglesAdded, _sequenceNbr);
                    _sequenceNbr++;
                    string imageServerFileName = HttpContext.Current.Server.MapPath(imageFileName);

                    ImagePlacementDetails singleImageDetails = new ImagePlacementDetails()
                    {
                        Width = width,
                        Height = height,
                        XOffset = -1,
                        YOffset = -1,
                        ImageUrl = imageFileName
                    };

                    _imageDetails.Add(singleImageDetails);

                    bitmap.Save(imageServerFileName, ImageFormat.Png);
                }
            }
        }

        return rectangleAdded;
    }

    /// <summary>
    /// Creates an image showing the structure of a sprite (that is, its constituent images).
    /// </summary>
    /// <param name="sprite">
    /// Sprite to be shown
    /// </param>
    /// <returns>
    /// Url of the generated image.
    /// </returns>
    public string SpriteToImage(ISprite sprite)
    {
        string imageFileName = null;

        using (Bitmap bitmap = new Bitmap(sprite.Width * _imageZoom, sprite.Height * _imageZoom))
        {
            using (Graphics graphics = Graphics.FromImage(bitmap))
            {
                // Draw border around the entire image
                DrawRectangle(
                    graphics,
                    sprite.Width * _imageZoom, sprite.Height * _imageZoom,
                    0, 0,
                    false, false);

                foreach (IMappedImageInfo mappedImageInfo in sprite.MappedImages)
                {
                    DrawRectangle(
                        graphics,
                        mappedImageInfo.ImageInfo.Width * _imageZoom, mappedImageInfo.ImageInfo.Height * _imageZoom,
                        mappedImageInfo.X * _imageZoom, mappedImageInfo.Y * _imageZoom,
                        true, false);
                }
            }

            imageFileName = string.Format(_canvasFolderName + "/canvas_finalsprite_{0}.png", _sequenceNbr);
            _sequenceNbr++;
            string imageServerFileName = HttpContext.Current.Server.MapPath(imageFileName);

            bitmap.Save(imageServerFileName, ImageFormat.Png);
        }

        return imageFileName;
    }

    /// <summary>
    /// Draws a rectangle on the canvas. The rectangle denotes a FreeArea.
    /// </summary>
    /// <param name="graphics"></param>
    /// <param name="width"></param>
    /// <param name="height"></param>
    /// <param name="xOffset"></param>
    /// <param name="yOffset"></param>
    /// <param name="occupied"></param>
    private void DrawRectangle(Graphics graphics, int width, int height, int xOffset, int yOffset, bool occupied, bool newlyOccupied)
    {
        // Fill the rectangle
        Color c;
        if (occupied)
        {
            if (newlyOccupied)
            {
                c = Color.DarkGreen;
            }
            else
            {
                c = Color.LightGreen;
            }
        }
        else
        {
            c = Color.White;
        }

        SolidBrush brush = new SolidBrush(c);
        graphics.FillRectangle(brush, xOffset, yOffset, width, height);

        // Draw border 
        Pen pen = new Pen(Color.Black);
        graphics.DrawRectangle(pen, xOffset, yOffset, width - 1, height - 1);
    }

    /// <summary>
    /// Removes any canvas images folder, than creates an empty one.
    /// </summary>
    private void ResetCanvasImagesFolder()
    {
        string tildeSpriteUrlPath = "~/" + _canvasFolderName + "/";
        string resolvedUrlPath = VirtualPathUtility.ToAbsolute(tildeSpriteUrlPath);
        string fileSystemFolder = HttpContext.Current.Server.MapPath(resolvedUrlPath.Replace('\\', '/'));

        // Create the directory in case it doesn't exist. If it does, nothing happens.
        DirectoryInfo di = Directory.CreateDirectory(fileSystemFolder);

        // Delete all files in the directory in case it already existed
        FileInfo[] fiArr = di.GetFiles();
        foreach(FileInfo fi in fiArr)
        {
            fi.Delete();
        }
    }
}

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
Web02 | 2.8.140814.1 | Last Updated 14 Jun 2011
Article Copyright 2011 by Matt Perdeck
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid