rectpack

Optimal rectangle packing

This code implements Huang and Korf's (2008, 2009, 2010, 2011) optimal rectangle packer. It also implements Korf's (2003, 2004) and Korf et al.'s (2009) optimal rectangle packer.

The software handles rectangles rotated to be aligned to the x and y axes, handles both oriented and unoriented rectangles, rectangles of high-precision dimensions, and finds the bounding box of smallest area that can contain the input rectangles without overlap.

Dependencies

• Boost program options, boost graph library, boost spirit v2, boost thread
• GNU Multi-Precision library (gmp), and C++ wrapper (gmpxx)

Reference

• 2003: Optimal Rectangle Packing: Initial Results
• 2004: Optimal Rectangle Packing: New Results
• 2009: New Improvements in Optimal Rectangle Packing
• 2010: Optimal Rectangle Packing on Non-Square Benchmarks
• 2011: Optimal Packing of High-Precision Rectangles
• 2012: Optimal Rectangle Packing: An Absolute Placement Approach
• Richard E. Korf homepage
• Eric Huang homepage

static memory allocation

When using this code for static memory allocation, first create a problem file (such as problem.csv) in the following format:

buffer_id,start,end,offset,size,alignment
1,0,20,0,4,1
2,9,20,0,4,1
3,0,8,0,4,1
4,3,8,0,4,1
5,0,2,0,4,1

To invoke the CSP solver, execute this command:

release/rectpack -2 d -b 0 -o 1 -w 5 -i problem.csv -B 0x12

To invoke the meta-CSP solver, execute this command:

release/rectpack -2 d -b 0 -o 1 -w 6 -i problem.csv -B 0x12

(the program will automatically calculate grid width, hence the '0' in the above box dimensions)