Difference between revisions of "2D-Packing Rectangles and Images"

From dftwiki3
Jump to: navigation, search
(Created page with "--~~~~ ---- <center> <font size="+2">Page under construction!</font> <br \>300px </center> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <b...")
 
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 10:26, 8 July 2013 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 10:26, 8 July 2013 (EDT)
 
----
 
----
−
<center> <font size="+2">Page under construction!</font> <br \>[[File:UnderConstruction.jpg|300px]] </center>  
+
<center> <font size="+2">Page under construction!</font> <br \>[[File:UnderConstruction.jpg|200px]] </center>  
  
 
<br />
 
<br />
 +
=2D-Packing Rectangles=
 +
 +
<bluebox>
 +
 +
</bluebox>
 +
 +
==Multithreaded 2D-Packing with pre-placed items==
 +
<br />
 +
{|
 +
|
 +
<videoflash>v=dIjJHexzPSI</videoflash>
 +
|
 +
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''. <br />
 +
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.
 +
<br />
 +
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.
 +
<br />
 +
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.
 +
<br />
 +
This page is aliased to the easier to use URL: [http://tinyurl.com/2DPacking  http://tinyurl.com/2DPacking].
 +
<br />
 +
Algorithm and video generated by
 +
Dominique Thiebaut, Dept. Computer Science, Smith College, Northampton, MA 01060, USA.
 +
|}
 +
 
<br />
 
<br />
 
<br />
 
<br />

Revision as of 10:07, 8 July 2013

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

Page under construction!
UnderConstruction.jpg


2D-Packing Rectangles

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.
This page is aliased to the easier to use URL: http://tinyurl.com/2DPacking.
Algorithm and video generated by Dominique Thiebaut, Dept. Computer Science, Smith College, Northampton, MA 01060, USA.



















Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=2D-Packing_Rectangles_and_Images&oldid=17034"