Rectangle Packing Problem

[Guest_imported]

problem description:

name: rectangle packing problem (2d bin packing, without rotation) see [1]

implementation: java, c or c++

application: merging many rectangular images to one big image containing all source images at rectangular regions

api overview:
needed is a analyser class that does the following
given is a collection of dimension-pairs (width;height)
after the analyse the result must give the "best" optimized for space (bounding box)
and a collection of rectangular regions with the same sizes given from the dimension collection.

example test code (not compileable):

list = new Vector();

list.add(new Dimension(100, 200));
list.add(new Dimension(130, 100));
list.add(new Dimension(134, 120));
list.add(new Dimension(330, 50));


Vector
 rectangles = new Vector();


Dimension
 boundingBox = [b]RectanglePacker[/b].analyse(list, rectangles);

System.out.println("bounding box size:"+boundingBox);

Enumeration
 e= rectangles.elements();

while (e.hasMoreElements())
{
 Rectangle
  rc = (Rectangle)e.nextElement();

 System.out.println(rc);
}

references:
1.

http://www-cad.eecs.berkeley.edu/~fmang/cs270/report.pdf