13,700,577 members

#### Stats

194K views
58 bookmarked
Posted 14 Jun 2011
Licenced CPOL

# 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 System.Diagnostics; namespace Mapper { /// /// Implements a two dimensional dynamic array with elements of type T. /// /// public class DynamicTwoDimensionalArray { /// /// Describes a row or column /// private struct Dimension { public short _size; public short _index; // The width of a column or the height of a row public int Size { get { return (int)_size; } set { _size = (short)value; } } // When a row or column is split, the new row is created at the end of the physical array rather than in the middle. // That way, there is no need to copy lots of data. But it does mean you need indirection from the logical index // to the physical index. // This field provides the physical index. public int Index { get { return (int)_index; } set { _index = (short)value; } } } // Describe the rows and columns private Dimension[] _columns; private Dimension[] _rows; private T[,] _data; // Number of logical columns in the 2 dimensional array private int _nbrColumns = 0; // Number of logical rows in the 2 dimensional array private int _nbrRows = 0; /// /// Number of columns /// public int NbrColumns { get { return _nbrColumns; } } /// /// Number of rows /// public int NbrRows { get { return _nbrRows; } } /// /// Constructor /// public DynamicTwoDimensionalArray() { } /// /// After you've constructed the array, you need to initialize it. /// /// This removes any content and creates the first cell - so the array /// will have height is 1 and width is 1. /// /// /// The array will initially have capacity for at least this many columns. /// Must be greater than 0. /// Set to the expected maximum width of the array or greater. /// The array will resize itself if you make this too small, but resizing is expensive. /// /// /// The array will initially have capacity for at least this many rows. /// Must be greater than 0. /// Set to the expected maximum height of the array or greater. /// The array will resize itself if you make this too small, but resizing is expensive. /// /// /// Width of the first column. /// /// /// Width of the first column. /// /// /// Width of the first column. /// public void Initialize(int capacityX, int capacityY, int firstColumnWidth, int firstRowHeight, T firstCellValue) { if (capacityX <= 0) { throw new Exception("capacityX cannot be 0 or smaller"); } if (capacityY == 0) { throw new Exception("capacityY cannot be 0 or smaller"); } if ((_columns == null) || (_columns.GetLength(0) < capacityX)) { _columns = new Dimension[capacityX]; } if ((_rows == null) || (_rows.GetLength(0) < capacityY)) { _rows = new Dimension[capacityY]; } if ((_data == null) || (_data.GetLength(0) < capacityX) || (_data.GetLength(1) < capacityY)) { _data = new T[capacityX, capacityY]; } _nbrColumns = 1; _nbrRows = 1; _columns[0].Index = 0; _columns[0].Size = firstColumnWidth; _rows[0].Index = 0; _rows[0].Size = firstRowHeight; _data[0, 0] = firstCellValue; } /// /// Returns the item at the given location. /// /// /// /// public T Item(int x, int y) { return _data[_columns[x].Index, _rows[y].Index]; } /// /// Sets an item to the given value /// /// /// /// public void SetItem(int x, int y, T value) { _data[_columns[x].Index, _rows[y].Index] = value; } /// /// Inserts a row at location y. /// If y equals 2, than all rows at y=3 and higher will now have y=4 and higher. /// The new row will have y=3. /// The contents of the row at y=2 will be copied to the row at y=3. /// /// If there is not enough capacity in the array for the additional row, /// than the internal data structure will be copied to a structure with twice the size /// (this copying is expensive). /// /// /// Identifies the row to be split. /// /// /// The height of the new row (the one at y=3 in the example). /// Must be smaller than the current height of the existing row. /// /// The old row will have height = (old height of old row) - (height of new row). /// public void InsertRow(int y, int heightNewRow) { if (y >= _nbrRows) { throw new Exception(string.Format("y is {0} but height is only {1}", y, _nbrRows)); } // If there are as many phyiscal rows as there are logical rows, we need to get more physical rows before the number // of logical rows can be increased. if (_data.GetLength(1) == _nbrRows) { IncreaseCapacity(); } // Copy the cells with the given y to a new row after the last used row. The y of the new row equals _nbrRows. int physicalY = _rows[y].Index; for (int x = 0; x < _nbrColumns; x++) { _data[x, _nbrRows] = _data[x, physicalY]; } // Make room in the _rows array by shifting all items that come after the one indexed by y one position to the right. // If y is at the end of the array, there is no need to shift anything. if (y < (_nbrRows - 1)) { Array.Copy(_rows, y + 1, _rows, y + 2, (_nbrRows - y - 1)); } // Let the freed up element point at the newly copied row _rows[y + 1].Index = _nbrRows; // Set the heights of the old and new rows. int oldHeight = _rows[y].Size; int newHeightExistingRow = oldHeight - heightNewRow; Debug.Assert((heightNewRow > 0) && (newHeightExistingRow > 0)); _rows[y + 1].Size = heightNewRow; _rows[y].Size = newHeightExistingRow; // The logical height of the array has increased by 1. _nbrRows++; } /// /// Same as InsertRow, but than for columns. /// /// public void InsertColumn(int x, int widthNewColumn) { if (x >= _nbrColumns) { throw new Exception(string.Format("x is {0} but width is only {1}", x, _nbrColumns)); } // If there are as many phyiscal columns as there are logical columns, we need to get more physical columns before the number // of logical columns can be increased. if (_data.GetLength(0) == _nbrColumns) { IncreaseCapacity(); } // Copy the cells with the given x to a new column after the last used column. The x of the new column equals _nbrColumns. int nbrPhysicalRows = _data.GetLength(1); int physicalX = _columns[x].Index; Array.Copy(_data, physicalX * nbrPhysicalRows, _data, _nbrColumns * nbrPhysicalRows, _nbrRows); // Make room in the _columns array by shifting all items that come after the one indexed by x one position to the right. // If x is at the end of the array, there is no need to shift anything. if (x < (_nbrColumns - 1)) { Array.Copy(_columns, x + 1, _columns, x + 2, (_nbrColumns - x - 1)); } // Let the freed up element point at the newly copied column _columns[x + 1].Index = _nbrColumns; // Set the widths of the old and new columns. int oldWidth = _columns[x].Size; int newWidthExistingColumn = oldWidth - widthNewColumn; Debug.Assert((widthNewColumn > 0) && (newWidthExistingColumn > 0)); _columns[x + 1].Size = widthNewColumn; _columns[x].Size = newWidthExistingColumn; // The logical width of the array has increased by 1. _nbrColumns++; } /// /// Returns the width of the column at the given location /// /// /// public int ColumnWidth(int x) { return _columns[x].Size; } /// /// Returns the height of the row at the given location /// /// /// public int RowHeight(int y) { return _rows[y].Size; } /// /// Doubles the capacity of the internal data structures. /// /// Creates a new array with double the width and height of the old array. /// Copies the element of the old array to the new array. /// Then replaces the old array with the new array. /// private void IncreaseCapacity() { int oldCapacityX = _data.GetLength(0); int oldCapacityY = _data.GetLength(1); int newCapacityX = oldCapacityX * 2; int newCapacityY = oldCapacityY * 2; int nbrItemsToCopy = oldCapacityX * oldCapacityY; T[,] newData = new T[newCapacityX, newCapacityY]; Array.Copy(_data, newData, nbrItemsToCopy); _data = newData; } /// /// Represents the DynamicTowDimensionalArray as a string. /// /// public override string ToString() { StringBuilder sb = new StringBuilder(); sb.AppendLine(); sb.Append(" X "); for (int x = 0; x < _nbrColumns + 1; x++) { sb.AppendFormat(" {0,2:G} ", x); } sb.AppendLine(); sb.Append("Y "); for (int x = 0; x < _nbrColumns + 1; x++) { sb.AppendFormat(" ({0,3:G})", ColumnWidth(x)); } sb.AppendLine(); for (int y = 0; y < _nbrRows + 1; y++) { sb.AppendFormat("{0,2:G} ({1,3:G}) ", y, RowHeight(y)); for (int x = 0; x < _nbrColumns + 1; x++) { sb.AppendFormat(" {0} ", Item(x, y)); } sb.AppendLine(); } return sb.ToString(); } } } ```

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.

## Share

 Architect Australia
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