¹University of Birmingham

Correspondence: Dr A M Tobias, School of Manufacturing and Mechanical Engineering, University of Birmingham, Birmingham B15 2TT, UK. E-mail: a.m.tobias@bham.ac.uk

Received February 1998; Accepted May 1999.

Abstract

This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the W₁ packing of identical shapes in the infinite plane. Restricted to polygons for computational convenience, it is based on the no-fit polygon/configuration 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.