2D-Packing Rectangles and Images

--D. Thiebaut (talk) 10:26, 8 July 2013 (EDT)

---

2D-Packing Rectangles

This page is aliased to the easier to use URL: http://tinyurl.com/2DPacking.
It contains information about a 2D-rectangular packing heuristic developed by D. Thiebaut to create collages of large collection of images.
The 2D-Packing Algorithm and the videos were generated by Dominique Thiebaut, (dthiebaut at smith.edu), Dept. Computer Science, Smith College, Northampton, MA 01060, USA.

One-thread 2D-Packing

A demo made of a 2D-Packing heuristic. The algorithm is given 10,000 randomly generated rectangles. The heuristic is multithreaded, with a "manager/worker" scheduling algorithm. In this movie 1 manager distributes rectangles to just 1 worker. So it is a multithreaded scheduling algorithm running but only one thread does the packing. The rectangles are colored by the first worker they are given to, and therefore are all colored the same here. See below for examples of true multithreaded packing. This version of the heuristic stops packing when it has reached a threshold, in this case if more than 99% of the original rectangular surface is covered. This corresponds to 9,848 rectangles of the 10,000 original ones picked. The actual coverage of the surface is 99.64%, corresponding to a packing factor of 1/0.9964 = 1.0036. The demo is written in Java and uses Processing for the display of the progression of the algorithm. The program is run on a MacPro with 2 x 2.8 GHz Quad-Core Intel Xeon processors, and 12 GBytes of RAM, and runs in 30.18 seconds.

Multithreaded 2D-Packing

A demo made of a 2D-Packing heuristic. The algorithm is given 10,000 randomly generated rectangles. The heuristic is multithreaded, with a "manager/worker" scheduling algorithm. In this movie 1 manager distributes rectangles to 6 workers. The rectangles are colored by the first worker they are given to. Workers return rectangles to the manager when they cannot pack them, and the manager distributes them to other workers. This version of the heuristic stops packing when it has reached a threshold, in this case if more than 99% of the original rectangular surface is covered. This corresponds to 9,869 rectangles of the 10,000 original ones picked. The actual coverage of the surface is 99.14%, corresponding to a packing factor of 1/0.9914 = 1.0087. The demo is written in Java and uses Processing for the display of the progression of the algorithm. The program is run on a MacPro with 2 x 2.8 GHz Quad-Core Intel Xeon processors, and 12 GBytes of RAM, and runs in 17.79 seconds.

Multithreaded 2D-Packing with pre-placed items

A demo made of a 2D-Packing heuristic. The algorithm is given 10,000 randomly generated rectangles, 5 of which have been modified to have fixed positions, and specific locations in the final rectangular surface. These are the pre-placed items. The heuristic is multithreaded, with a "manager/worker" scheduling algorithm. In this movie 1 manager distributes rectangles to 6 workers. The rectangles are colored by the first worker they are given to. Workers return rectangles to the manager when they cannot pack them, and the manager distributes them to other workers. This version of the heuristic stops packing when it has reached a threshold, in this case if more than 99% of the original rectangular surface is covered. This corresponds to 9,823 rectangles of the 10,000 original ones picked. The actual coverage of the surface is 99.10%, corresponding to a packing factor of 1/0.991 = 1.0090. The demo is written in Java and uses Processing for the display of the progression of the algorithm. The program is run on a MacPro with 2 x 2.8 GHz Quad-Core Intel Xeon processors, and 12 GBytes of RAM, and runs in 20.8 seconds.

Packing a Million Rectangles

This is a real-time screen capture of the packing of 1 million rectangles implemented in Processing. The heuristic used is described in "2D Packing Images on a Large Scale" authored by D. Thiebaut and to be presented at INFOCOMP 2013. In the video the rectangles are randomly sized and packed in a greedy fashion, the rectangle with the largest height put in the largest and left-most space available. The packing was captured on a 2.8 GHz Mac Pro. The application is serial, and not threaded. The Processing GUI thread works in parallel to the packing and displays (in a choppy way) the rectangles packed so far. The total time is less than 8 real-time seconds.

Packing Photographs

The collage below contains about 200 photographs, some of them duplicated. They have all been resized by a random factor. The dimensions are not all the same as some photographs have been cropped to improve their artistic value. They represent sky shots taken in Northampton, MA, over the course of two years. All photos belong to this wiki owner.

The collage below contains 2,200 photographs. The photographs have been resized by a random factor, and not all photographs have the same aspect ratio. All photographs owned this wiki owner.

Publications

• 2D-Packing on a Large Scale, D. Thiebaut, in Proceedings of INFOCOMP 2013, Lisbon, Portugal, Nov. 2013. (Awarded best paper at INFOCOMP 2013.)

Abstract: We present a new heuristic for 2D-packing of rectangles inside a rectangular area where the aesthetics of the resulting packing is amenable to generating large collages of photographs or images. The heuristic works by maintaining a sorted collection of vertical segments covering the area to be packed. The segments define the leftmost boundaries of rectangular and possibly overlapping areas that are yet to be covered. The use of this data structure allows for easily defining ahead of time arbitrary rectangular areas that the packing must avoid. The 2D-packing heuristic presented does not allow the rectangles to be rotated during the packing, but could easily be modified to implement this feature. The execution time of the present heuristic on various benchmark problems is on par with recently published research in this area, including some that do allow rotation of items while packing. Several examples of image packing are presented.

• 2D Packing on a Large Scale: Packing a Billion Rectangles under 10 Minutes, D. Thiebaut, Int'l Journal in Advances in Systems and Measurements, vol. 7, no. 1&2, pp. 80-90, July 2014.

Abstract: We present a new heuristic for 2D-packing of rectangles inside a rectangular area where the aesthetics of the resulting packing is amenable to generating large collages of photographs or images. The heuristic works by maintaining a sorted collection of vertical segments covering the area to be packed. The segments define the leftmost boundaries of rectangular and possibly overlapping areas that are yet to be covered. The use of this data structure allows for easily defining ahead of time arbitrary rectangular areas that the packing must avoid. The 2D-packing heuristic presented does not allow the rectangles to be rotated during the packing, but could easily be modified to implement this feature. The execution time of the present heuristic on various benchmark problems is on par with recently published research in this area, including some that do allow rotation of items while packing. Several examples of image packing are presented. A multithreaded version of our core packing algorithm running on a 32-core 2.8 GHz processor packs a billion rectangles in under 10 minutes.