An efficient algorithm for the regular w\ packing of polygons in the infinite plane

P. D. Watson, A. M. Tobias*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the Wj 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.

Original languageEnglish
Pages (from-to)1054-1062
Number of pages9
JournalOperational Research Society. Journal
Volume50
Issue number10
DOIs
Publication statusPublished - 1999

Keywords

  • Heuristics
  • Non-convex polygon
  • Optimisation
  • Packing

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Fingerprint

Dive into the research topics of 'An efficient algorithm for the regular w\ packing of polygons in the infinite plane'. Together they form a unique fingerprint.

Cite this