An algorithm for polygon placement using a bottom-left strategy

An algorithm for polygon placement using a bottom-left strategy

0.00 Avg rating0 Votes
Article ID: iaor20031913
Country: Netherlands
Volume: 141
Issue: 2
Start Page Number: 371
End Page Number: 381
Publication Date: Sep 2002
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper describes a fast and efficient implementation of a bottom-left (BL) placement algorithm for polygon packing. The algorithm allows pieces to be nested within the partial layout produced by previously placed pieces, and produces an optimal BL layout in the sense that the positions considered are guaranteed to contain the bottom-left position of the infinite set of possibilities. Full details of the way in which these positions are calculated are given. Computational experiments comparing the results of different orderings on a variety of datasets from the literature are reported, and these illustrate that problems having in excess of 100 pieces of several piece types can be solved within one minute on a modern desktop PC. The procedure can easily be incorporated into algorithms that apply more sophisticated piece selection procedures.

Reviews

Required fields are marked *. Your email address will not be published.