Click here to Skip to main content
12,621,432 members (30,936 online)
Click here to Skip to main content

Stats

134.9K views
5.1K downloads
50 bookmarked
Posted

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.Text;
using System.Diagnostics;

namespace Mapper
{
    /// <summary>
    /// This type of canvas places rectangles as far to the left as possible (lowest X).
    /// If there is a choice between locations with the same X, it will pick the one with the 
    /// lowest Y.
    /// </summary>
    public class Canvas : ICanvas
    {
        public struct CanvasCell
        {
            public bool occupied;

            public CanvasCell(bool occupied) { this.occupied = occupied; }

            public override string ToString() { return occupied ? "x" : "."; }
        }

        private DynamicTwoDimensionalArray<CanvasCell> _canvasCells =
            new DynamicTwoDimensionalArray<CanvasCell>();

        // Make _canvasCells available to canvas classes derived from this class.
        protected DynamicTwoDimensionalArray<CanvasCell> CanvasCells { get { return _canvasCells; } }

        private int _nbrRectangleAddAttempts = 0;
        public int NbrRectangleAddAttempts { get { return _nbrRectangleAddAttempts; } }

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

        // Lowest free height deficit found since the last call to SetCanvasDimension
        private int _lowestFreeHeightDeficitSinceLastRedim = Int32.MaxValue;

        private int _nbrCellsGenerated = 0;

        public Canvas()
        {
        }

        /// <summary>
        /// See ICanvas
        /// </summary>
        public int UnlimitedSize { get { return short.MaxValue; } }

        /// <summary>
        /// See ICanvas
        /// </summary>
        public virtual void SetCanvasDimensions(int canvasWidth, int canvasHeight)
        {
            // Right now, it is unknown how many rectangles need to be placed.
            // So guess that a 100 by 100 capacity will be enough.
            const int initialCapacityX = 100;
            const int initialCapacityY = 100;

            // Initially, there is one free cell, which covers the entire canvas.
            _canvasCells.Initialize(initialCapacityX, initialCapacityY, canvasWidth, canvasHeight, new CanvasCell(false));

            _nbrCellsGenerated = 0;
            _nbrRectangleAddAttempts = 0;
            _lowestFreeHeightDeficitSinceLastRedim = Int32.MaxValue;

            _canvasWidth = canvasWidth;
            _canvasHeight = canvasHeight;
        }

        /// <summary>
        /// See ICanvas.
        /// </summary>
        public virtual bool AddRectangle(
            int rectangleWidth, int rectangleHeight, out int rectangleXOffset, out int rectangleYOffset,
            out int lowestFreeHeightDeficit)
        {
            rectangleXOffset = 0;
            rectangleYOffset = 0;
            lowestFreeHeightDeficit = Int32.MaxValue;

            int requiredWidth = rectangleWidth;
            int requiredHeight = rectangleHeight;

            _nbrRectangleAddAttempts++;

            int x = 0;
            int y = 0;
            int offsetX = 0;
            int offsetY = 0;
            bool rectangleWasPlaced = false;
            int nbrRows = _canvasCells.NbrRows;

            do
            {
                int nbrRequiredCellsHorizontally;
                int nbrRequiredCellsVertically;
                int leftOverWidth;
                int leftOverHeight;

                // First move upwards until we find an unoccupied cell. 
                // If we're already at an unoccupied cell, no need to do anything.
                // Important to clear all occupied cells to get 
                // the lowest free height deficit. This must be taken from the top of the highest 
                // occupied cell.

                while ((y < nbrRows) && (_canvasCells.Item(x, y).occupied))
                {
                    offsetY += _canvasCells.RowHeight(y);
                    y += 1;
                }

                // If we found an unoccupied cell, than see if we can place a rectangle there.
                // If not, than y popped out of the top of the canvas.

                if ((y < nbrRows) && (FreeHeightDeficit(_canvasHeight, offsetY, requiredHeight) <= 0))
                {
                    if (IsAvailable(
                        x, y, requiredWidth, requiredHeight,
                        out nbrRequiredCellsHorizontally, out nbrRequiredCellsVertically,
                        out leftOverWidth, out leftOverHeight))
                    {
                        PlaceRectangle(
                            x, y, requiredWidth, requiredHeight,
                            nbrRequiredCellsHorizontally, nbrRequiredCellsVertically,
                            leftOverWidth, leftOverHeight);

                        rectangleXOffset = offsetX;
                        rectangleYOffset = offsetY;

                        rectangleWasPlaced = true;
                        break;
                    }

                    // Go to the next cell
                    offsetY += _canvasCells.RowHeight(y);
                    y += 1;
                }

                // If we've come so close to the top of the canvas that there is no space for the
                // rectangle, go to the next column. This automatically also checks whether we've popped out of the top
                // of the canvas (in that case, _canvasHeight == offsetY).

                int freeHeightDeficit = FreeHeightDeficit(_canvasHeight, offsetY, requiredHeight);
                if (freeHeightDeficit > 0)
                {
                    offsetY = 0;
                    y = 0;

                    offsetX += _canvasCells.ColumnWidth(x);
                    x += 1;

                    // This update is far from perfect, because if the rectangle could not be placed at this column
                    // because of insufficient horizontal space, than this update should not be made (because it may lower
                    // _lowestFreeHeightDeficitSinceLastRedim while in raising the height of the canvas by this lowered amount
                    // may not result in the rectangle being placed here after all.
                    //
                    // However, checking for sufficient horizontal width takes a lot of CPU ticks. Tests have shown that this
                    // far outstrips the gains through having fewer failed sprite generations.
                    if (_lowestFreeHeightDeficitSinceLastRedim > freeHeightDeficit) { _lowestFreeHeightDeficitSinceLastRedim = freeHeightDeficit;  }
                }

                // If we've come so close to the right edge of the canvas that there is no space for
                // the rectangle, return false now.
                if ((_canvasWidth - offsetX) < requiredWidth)
                {
                    rectangleWasPlaced = false;
                    break;
                }
            } while (true);

            lowestFreeHeightDeficit = _lowestFreeHeightDeficitSinceLastRedim;
            return rectangleWasPlaced;
        }

        /// <summary>
        /// Works out the free height deficit when placing a rectangle with a required height at a given offset.
        /// 
        /// If the free height deficit is 0 or negative, there may be room to place the rectangle (still need to check for blocking
        /// occupied cells).
        /// 
        /// If the free height deficit is greater than 0, you're too close to the top edge of the canvas to place the rectangle.
        /// </summary>
        /// <param name="canvasHeight"></param>
        /// <param name="offsetY"></param>
        /// <param name="requiredHeight"></param>
        /// <returns></returns>
        private int FreeHeightDeficit(int canvasHeight, int offsetY, int requiredHeight)
        {
            int spaceLeftVertically = canvasHeight - offsetY;
            int freeHeightDeficit = requiredHeight - spaceLeftVertically;

            return freeHeightDeficit;
        }


        /// <summary>
        /// Sets the cell at x,y to occupied, and also its top and right neighbours, as needed
        /// to place a rectangle with the given width and height.
        /// 
        /// If the rectangle takes only part of a row or column, they are split.
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <param name="requiredWidth"></param>
        /// <param name="requiredHeight"></param>
        /// <param name="nbrRequiredCellsHorizontally">
        /// Number of cells that the rectangle requires horizontally
        /// </param>
        /// <param name="nbrRequiredCellsVertically">
        /// Number of cells that the rectangle requires vertically
        /// </param>
        /// <param name="leftOverWidth">
        /// The amount of horizontal space left in the right most cells that could be used for the rectangle
        /// </param>
        /// <param name="leftOverHeight">
        /// The amount of vertical space left in the bottom most cells that could be used for the rectangle
        /// </param>
        private void PlaceRectangle(
            int x, int y, 
            int requiredWidth, int requiredHeight,
            int nbrRequiredCellsHorizontally, int nbrRequiredCellsVertically,
            int leftOverWidth,
            int leftOverHeight)
        {
            // Split the far most row and column if needed.

            if (leftOverWidth > 0)
            {
                _nbrCellsGenerated += _canvasCells.NbrRows;

                int xFarRightColumn = x + nbrRequiredCellsHorizontally - 1;
                _canvasCells.InsertColumn(xFarRightColumn, leftOverWidth);
            }

            if (leftOverHeight > 0)
            {
                _nbrCellsGenerated += _canvasCells.NbrColumns;

                int yFarBottomColumn = y + nbrRequiredCellsVertically - 1;
                _canvasCells.InsertRow(yFarBottomColumn, leftOverHeight);
            }

            for (int i = x + nbrRequiredCellsHorizontally - 1; i >= x; i--)
            {
                for (int j = y + nbrRequiredCellsVertically - 1; j >= y; j--)
                {
                    _canvasCells.SetItem(i, j, new CanvasCell(true));
                }
            }
        }

        /// <summary>
        /// Returns true if a rectangle with the given width and height can be placed
        /// in the cell with the given x and y, and its right and top neighbours.
        /// 
        /// This method assumes that x,y is far away enough from the edges of the canvas
        /// that the rectangle could actually fit. So this method only looks at whether cells
        /// are occupied or not.
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <param name="requiredWidth"></param>
        /// <param name="requiredHeight"></param>
        /// <param name="nbrRequiredCellsHorizontally">
        /// Number of cells that the rectangle requires horizontally
        /// </param>
        /// <param name="nbrRequiredCellsVertically">
        /// Number of cells that the rectangle requires vertically
        /// </param>
        /// <param name="leftOverWidth">
        /// The amount of horizontal space left in the right most cells that could be used for the rectangle
        /// </param>
        /// <param name="leftOverHeight">
        /// The amount of vertical space left in the bottom most cells that could be used for the rectangle
        /// </param>
        /// <returns></returns>
        private bool IsAvailable(
            int x, int y, int requiredWidth, int requiredHeight, 
            out int nbrRequiredCellsHorizontally,
            out int nbrRequiredCellsVertically,
            out int leftOverWidth,
            out int leftOverHeight)
        {
            nbrRequiredCellsHorizontally = 0;
            nbrRequiredCellsVertically = 0;
            leftOverWidth = 0;
            leftOverHeight = 0;

            int foundWidth = 0;
            int foundHeight = 0;
            int trialX = x;
            int trialY = y;

            // Check all cells that need to be unoccupied for there to be room for the rectangle.

            while (foundHeight < requiredHeight)
            {
                trialX = x;
                foundWidth = 0;

                while (foundWidth < requiredWidth)
                {
                    if (_canvasCells.Item(trialX, trialY).occupied)
                    {
                        return false;
                    }

                    foundWidth += _canvasCells.ColumnWidth(trialX);
                    trialX++;
                }

                foundHeight += _canvasCells.RowHeight(trialY);
                trialY++;
            }

            // Visited all cells that we'll need to place the rectangle,
            // and none were occupied. So the space is available here.

            nbrRequiredCellsHorizontally = trialX - x;
            nbrRequiredCellsVertically = trialY - y;

            leftOverWidth = (foundWidth - requiredWidth);
            leftOverHeight = (foundHeight - requiredHeight);

            return true;
        }

        /// <summary>
        /// See ICanvas
        /// </summary>
        /// <param name="canvasStats"></param>
        public void GetStatistics(ICanvasStats canvasStats)
        {
            canvasStats.NbrCellsGenerated = _nbrCellsGenerated;
            canvasStats.RectangleAddAttempts = _nbrRectangleAddAttempts;
            canvasStats.LowestFreeHeightDeficit = _lowestFreeHeightDeficitSinceLastRedim;
        }
    }
}

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
Architect
Australia Australia
Twitter: @MattPerdeck
LinkedIn: au.linkedin.com/in/mattperdeck
Current project: JSNLog JavaScript Logging Package

Matt has over 9 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 is the author of the book ASP.NET Performance Secrets (www.amazon.com/ASP-NET-Site-Performance-Secrets-Perdeck/dp/1849690685) 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. He recently worked at Readify and the global professional services company PwC. He now works at SP Health, a global provider of weight loss web sites such at CSIRO's TotalWellBeingDiet.com and BiggestLoserClub.com.

You may also be interested in...

Pro
Pro
| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.161128.1 | Last Updated 14 Jun 2011
Article Copyright 2011 by Matt Perdeck
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid