Patent ID: 7275210

Claim:
A method for creating a layout comprising: (a) inputting a smallest rectangular shape; (b) inputting a total area for the layout as integer multiples of the width and height of the smallest rectangular shape; (c) inputting a largest acceptable rectangular shape as integer multiples of the width and height of the smallest rectangular shape; (d) inputting a plurality of rectangular shapes, wherein each of the plurality of rectangular shapes is characterized by a size relative to the smallest rectangular shape and no larger than the input largest acceptable rectangular shape; (e) determining if a selection of said plurality of rectangular shapes exists such that the selection has the cardinality of the input plurality of rectangular shapes and the plurality of rectangular shapes covers the inputted total area without overlapping or leaving any part of the total area uncovered, wherein: (1) if at least one such plurality of rectangular shapes exists, producing a layout of the plurality of inputted shapes by changing the sizes of some of the inputted rectangular shapes sizes relative to a smallest rectangular shape and no larger than the input largest acceptable rectangular shape such that the plurality of rectangular shapes covers the input total area without overlapping; and (2) if no such plurality of rectangular shapes exists, find a total area similar to the inputted total area for which such a combination exists and apply the layout method to that total area.