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 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;

namespace Mapper
{
    /// <summary>
    /// A canvas is a rectangle of a given size that lets you add smaller rectangle.
    /// The canvas will place each rectangle so that it doesn't overlap with any other rectangle that is already 
    /// on the canvas.
    /// </summary>
    public interface ICanvas
    {
        /// <summary>
        /// Value denoting an unlimited width or height. You would pass this in to SetCanvasDimensions.
        /// </summary>
        int UnlimitedSize { get; }

        /// <summary>
        /// Sets the dimensions of the canvas.
        /// If there were already rectangles on the canvas when this is called, those rectangles will be removed.
        /// 
        /// Be sure to call this method before you call AddRectangle for the first time.
        /// </summary>
        /// <param name="canvasWidth">New width of the canvas</param>
        /// <param name="canvasHeight">New height of the canvas</param>
        void SetCanvasDimensions(int canvasWidth, int canvasHeight);

        /// <summary>
        /// Adds a rectangle
        /// </summary>
        /// <param name="rectangleWidth">Width of the rectangle</param>
        /// <param name="rectangleHeight">Height of the rectangle</param>
        /// <param name="rectangleXOffset">X position where rectangle has been placed</param>
        /// <param name="rectangleYOffset">Y position where rectangle has been placed</param>
        /// <param name="lowestFreeHeightDeficit">
        /// Lowest free height deficit for all the rectangles placed since the last call to SetCanvasDimensions.
        /// 
        /// This will be set to Int32.MaxValue if there was never any free height deficit.
        /// </param>
        /// <returns>
        /// true: rectangle placed
        /// false: rectangle not placed because there was no room
        /// </returns>
        bool AddRectangle(
            int rectangleWidth, int rectangleHeight, out int rectangleXOffset, out int rectangleYOffset,
            out int lowestFreeHeightDeficit);

        /// <summary>
        /// The canvas keeps statistics, on for example the number of times a FreeAreas is generated.
        /// Use this method to fill an object that implements ICanvasStats with these statistics.
        /// 
        /// Note that calling SetCanvasDimensions resets all counters.
        /// </summary>
        /// <param name="canvasStats">
        /// Reference to object to be filled.
        /// 
        /// If this is null, nothing happens (so there is no exception).
        /// </param>
        void GetStatistics(ICanvasStats canvasStats);


    }
}

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