Method for packing rectangular strips
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsNeal B. Lesh, Michael D. Mitzenmacher, Joseph W. Marks
Life of this patent
Estimating the term…
Abstract
A method packs input rectangles into a target rectangle. The rectangles are permuted into one or more an ordered list according to dimensions of the rectangles, e.g., width, height, perimeter, and area. The rectangles are then marked as unaccepted. A next unaccepted rectangle is selected from the ordered list beginning with a first rectangle in the list. Accepting the next rectangle if it is the last unaccepted rectangles, and otherwise, accepting the next rectangle with a probability p, and marking the next rectangle as accepted, and repeating the steps until all rectangles have been accepted.
Claims23
A method for packing a plurality of input rectangles into a target rectangle, comprising:
- permuting a plurality of input rectangles into an ordered list;
- marking the plurality of rectangles in the ordered list as unaccepted;
- selecting a next unaccepted rectangle from the ordered list beginning with a first rectangle in the list;
- determining whether the next rectangle is a last unaccepted rectangle;
- accepting the next rectangle, if true, otherwise;
- accepting the next rectangle with a probability p;
- marking the next rectangle as accepted;
- and
- repeating from the selecting step.
A method for packing a plurality of input rectangles into a target rectangle, comprising:
- sorting the plurality of input rectangles into an ordered list according to a decreasing dimension of the plurality of rectangles;
- and
- selecting, in order, the plurality of rectangles from the ordered list for packing into the target rectangle in a bottom-left-decreasing order while permuting randomly the ordered list.
Dependencies are inferred from the claim text.