On the Template-Layout Problem.
Abstract:
A challenging problem in geometric pattern fitting and graphic-data manipulation is that of packing as many copies of a given irregularly-shaped planar template into a large stock sheet of finite dimensions. The problem has many industrial applications, e.g., in sheet metal stamping and cloth cutting. This report describes a heuristic approach in which edge profiles are computed from the chain-code representations of the given templates. The edge profiles then facilitate the pairwise fitting of templates into modules which can be placed iteratively over the entire sheet, except near the boundaries where there may be insufficient space. Separate boundary modules are then utilized at the sheet boundaries. Three criteria for evaluating a pairwise template fit are described and related to the overall objective of achieving a maximum ratio of utilized to available space.