On the Template-Layout Problem.
NEW YORK UNIV N Y DIV OF APPLIED SCIENCE
Pagination or Media Count:
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.
- Operations Research
- Manufacturing and Industrial Engineering and Control of Production Systems