An efficient algorithm for the regular W 1 packing of polygons in the infinite plane
- PDF / 596,120 Bytes
- 9 Pages / 595 x 842 pts (A4) Page_size
- 68 Downloads / 196 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $15.00 http://www.stockton-press.co.uk/jors
An ef®cient algorithm for the regular W1 packing of polygons in the in®nite plane PD Watson and AM Tobias University of Birmingham This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the W1 packing of identical shapes in the in®nite plane. Restricted to polygons for computational convenience, it is based on the no-®t polygon=con®guration space obstacle approach. The algorithm was tested on a modest set of fourteen polygons (thirteen non-interlocking and one interlocking) and yielded a feasible solution for each. The solutions were optimal for four of the non-interlocking polygons and near optimal for the other nine. As expected though, the solution for the one interlocking polygon was sub-optimal and enhancements to the algorithm would be required for such cases. Keywords: packing; heuristics; optimisation; non-convex polygon
Introduction Mathematical theories for the problem of packing congruent (identical) convex shapes in the plane date back to the seventeenth century and the work of Kepler.1 Much of this early work was concerned with the mathematical properties of convex polygons which cover the plane without gaps (tilings). It is well known2 that all convex polygons with fewer than ®ve vertices (and hence edges) tile the plane but that, with the exception of a small number of pentagons and hexagons, the majority of convex polygons with ®ve or more vertices fail to do so. Given a shape that cannot tile the plane, what is the most ef®cient (tightest packed) arrangement that can be achieved? The only early work which addressed this question was concerned with the packing of congruent circles. Thue3 is one of several mathematicians to have proved that the optimal arrangement of circles has a packing ef®ciency of 90.69%. It is only over the past two or three decades, since the growth of operational research, that much related work has been conducted and this has mainly focused on speci®c practical problems which occur in particular manufacturing industries. Cutting and packing is now a subject with its own typology4 and a vast literature.5,6 Following a discussion of the various existing methods, this paper describes a new algorithm for packing polygons ef®ciently in the plane using W1 arrangements7 (in which only translations are permitted, that is, no rotations or re¯ections). The algorithmÐcalled PLANEPACKÐis comprised of a series of well-established techniques (including decomposition and the use of con®guration *Correspondence: Dr AM Tobias, School of Manufacturing and Mechanical Engineering, University of Birmingham, Birmingham B15 2TT, UK. E-mail: [email protected]
space obstacles8,9 similar to the no-®t polygon approach of Adamowicz and Albano10). It is described using a fairly simple non-convex shape as an example and its performance when applied to this and thirteen other test polygons of varying complexities is discussed.
Cuttin
Data Loading...
