Home > ASP.NET, C#, Graphics, Optimization, Programming, Tips & Tricks > C# Rectangle Packing

C# Rectangle Packing

Sometimes, you’re faced with the problem to cramp as many smaller textures as possible onto a larger texture. Typical cases are lightmaps, which are very small textures with dimensions that usually are not powers of two, or bitmap fonts where you want to try and fit the entire ascii character set onto a texture without wasting much space.

What you need then, is a rectangle packer, an algorithm that arranges as many smaller rectangles on a larger rectangle as can possibly fit.

The Nuclex.Support assembly contains several rectangle packing algorithms in the Nuclex.Support.Packing namespace offering various levels of compromises between space efficiency and runtime performance. All of these algorithms have been implemented as classes with a common interface, so, once implemented, you can easily switch forth and back between different algorithms to find the one best suites for your purpose.

Currently, there are three different packing algorithms for you to choose:

The Simple Packer The Simple Packer
This packer is optimized for runtime performance. It does sacrifice a bit of space, but the time needed to find a position for a new rectangle is O(1). In english, that means it doesn’t take longer to search for a suitable position, no matter how many rectangles have been added to the packing area.
The Cygon Packer The Cygon Packer
Named after your humble webmaster, this algorithm is highly efficient in its space usage and offers reasonable performance. It will never exceed O(n) time but generally achieves almost O(1) on average. English translation: Search time is usually constant and guaranteed to never exceed a linear increase (so when you’ve got 99 rectangles already packed and add the 100th one, it guarantees that search time will at most be 1% longer than the time taken for the previous rectangle).
The Arevalo Packer The Arevalo Packer
Named after Javier Arevalo, who posted his implementation of this packer on flipcode back in the golden times. This algorithm offers very good space efficiency and runs in slightly less then O(n) time. Just to be consistent, in english, that means, the time needed to find a suitable place for a new rectangle will only increase linearly.

You can download the C# version of the algorithms from here.

The usage is very simple :

	Point PP;
	var ARP = new ArevaloRectanglePacker(200, 200);

	if(!ARP.TryPack(Width, Height, out PP)) {
		// Do something
	}
	else {
		// Do something else
	}
VN:F [1.9.22_1171]
Rating: 4.3/5 (6 votes cast)
C# Rectangle Packing, 4.3 out of 5 based on 6 ratings
  1. leonardo
    July 13th, 2009 at 00:13 | #1

    Nice. I have translated & improved the Arevalo packer to Python and D:
    http://www.fantascienza.net/leonardo/so/index.html#rectpack

    VA:F [1.9.22_1171]
    Rating: 5.0/5 (1 vote cast)
  2. MisterQ
    November 4th, 2009 at 23:02 | #2

    Very nice!
    I use your code to create spritesheets. Do you know if soritng the images by height/width or something like this improves the packrate ?

    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
  3. Kosta
    March 19th, 2010 at 15:56 | #3

    Hi!
    I’m beginer developer and I need some help!
    I would like to use this code, but I don’t know to implement it.
    Can somebody provide simple code/solution of using this engine(one form, button, list of input rectangles, and panel, so when button is clicked, I would be able to see sort rectangles in panel)? This would really help me!!

    Thanks anyway!!!

    VA:F [1.9.22_1171]
    Rating: 5.0/5 (1 vote cast)
  4. Kosta
    March 20th, 2010 at 10:50 | #4

    Hi! Very nice!

    I’m beginer developer, and I need some help :)

    I would like to use this engine in my code, but I don’t know how to implement it. So, if somebody can provide simple solution(one form, one button, one list with 10 rectangles, and one panel, so when i click on the button i get packed/sorted my rectangles in panel) I would be grateful!!!

    p.s. Can this code be used in win applications, not just for game developing?

    Thanks anyway!!!

    VA:F [1.9.22_1171]
    Rating: 5.0/5 (1 vote cast)
  5. Matt
    June 16th, 2011 at 13:59 | #5

    I came up with a fast algorithm that does the same thing – packing rectangles of varying sizes into an enclosing rectangle of minimum size. I wrote it in C#. Also did a web site that graphically shows step by step how the algorithm works out the best enclosing algorithm. It’s at
    http://www.codeproject.com/KB/aspnet/rectanglepacker.aspx

    VA:F [1.9.22_1171]
    Rating: 0.0/5 (0 votes cast)
  1. March 29th, 2010 at 02:23 | #1

Subscribe without commenting

SEO Powered by Platinum SEO from Techblissonline
watch free movies