Object placement method and apparatus
First Claim
1. A method for placing physical objects of differing placement characteristic types in a physical three-dimensional space of predetermined size, comprising the steps of:
- (a) storing in a computer, a library of object placement patterns, each pattern in the library representing placement of a plurality of objects;
(b) storing in the computer, a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed;
(c) selecting, in the computer, from the stored representation of the physical objects, a given number of first type representation of an object to be placed in the representation of the three-dimensional space;
(d) choosing, in the computer, from the stored library, a pattern set comprising at least one pattern for placement of said first type representation of an object in the representation of the three-dimensional space which minimizes the portion of said representation of the three-dimensional space used, to place the given number of first type representation of objects within a portion of the representation of the three-dimensional space consistent with at least one constraint factor;
(e) repeating steps (c) and (d) in the computer, for the remaining representations of objects to be placed in the representation of the three-dimensional space, to thereby place the representation of the physical objects in the representation of the physical three-dimensional space;
(f) producing an indication of the placed representation of the objects in the representation of three-dimensional space; and
(g) placing the physical objects in the physical three-dimensional space in conformance with the indication of the placed representation of the objects in the representation of three-dimensional space.
2 Assignments
0 Petitions
Accused Products
Abstract
An object placement method and apparatus which obtains efficiency and optimized placement by providing a library of object placement patterns, each pattern in said library representing a plurality of objects filling a pattern line or series of pattern lines of a three-dimensional space. For each pattern line, a first type object (for example, a first size object) to be placed is selected and the pattern which minimizes the portion of the three-dimensional space used to place a number of first type objects, subject to at least one constraint factor, is determined. A representation of the objects in the rows according to the determined pattern may be provided. According to another aspect of the invention, linking restrictions between the objects of differing sizes may be provided. The linking restrictions are patterns from the library which may not be employed with objects of differing types in a line of the three-dimensional space. The linking restrictions may reject patterns that lead to irregular pattern geometries, inefficient use of space, unstable characteristics or any other undesirable configuration of the two object types in a single pattern line. The element placement technique of the present invention determines the patterns which minimize the portions of the three-dimensional space used to place the objects consistent with at least one constraint factor without violating the linking restrictions.
180 Citations
44 Claims
-
1. A method for placing physical objects of differing placement characteristic types in a physical three-dimensional space of predetermined size, comprising the steps of:
-
(a) storing in a computer, a library of object placement patterns, each pattern in the library representing placement of a plurality of objects; (b) storing in the computer, a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed; (c) selecting, in the computer, from the stored representation of the physical objects, a given number of first type representation of an object to be placed in the representation of the three-dimensional space; (d) choosing, in the computer, from the stored library, a pattern set comprising at least one pattern for placement of said first type representation of an object in the representation of the three-dimensional space which minimizes the portion of said representation of the three-dimensional space used, to place the given number of first type representation of objects within a portion of the representation of the three-dimensional space consistent with at least one constraint factor; (e) repeating steps (c) and (d) in the computer, for the remaining representations of objects to be placed in the representation of the three-dimensional space, to thereby place the representation of the physical objects in the representation of the physical three-dimensional space; (f) producing an indication of the placed representation of the objects in the representation of three-dimensional space; and (g) placing the physical objects in the physical three-dimensional space in conformance with the indication of the placed representation of the objects in the representation of three-dimensional space. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method for placing physical objects of differing sizes in a three-dimensional space of a predetermined size, comprising the steps of:
-
(a) storing in a computer, a library of object placement patterns, each pattern in the library representing placement of objects in a row of three-dimensional space, the library of patterns having several different pattern types; (b) storing in the computer, a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed; (c) determining, in the computer, which of the pattern types are feasible for placing the stored representation of the physical objects; (d) selecting, in the computer, a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of the representation of the three-dimensional space used to place a given number of representations of first type objects consistent with at least one constraint factor; (e) choosing, in the computer, which of the selected patterns minimizes the portion of the representation of the three-dimensional space used to place a given number of representations of first type objects consistent with the constraint factor associated therewith; (f) for each pattern set, if a pattern remains unfilled after all representations of objects of the first size are placed, determining which pattern minimizes the portion of the representation of the three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern; (g) repeating steps (d), (e) and (f) in the computer, for the remaining representations of objects to be placed in the representation of the three-dimensional space, to thereby place the representation of the physical objects in the representation of the physical three-dimensional space; (h) producing an indication of the placed representation of the objects in the representation of three-dimensional space; and (i) placing the physical objects in the physical three-dimensional space in conformance with the indication of the placed representation of the objects in the representation of three-dimensional space. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
-
21. A method for placing objects of at least two differing placement characteristic types in a three-dimensional space of a predetermined size, comprising the steps of:
-
(a) storing, in a computer, a library of patterns, each pattern representing placement of objects within said pattern; (b) storing in the computer, a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed; (c) determining linking restrictions between the representations of objects of differing placement characteristic types, the linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; (d) selecting a pattern for each group of objects, which places said differing placement characteristic type groups of objects without violating the linking restrictions; (e) repeating step (d) in the computer, for the remaining representations of objects to be placed in the representation of the three-dimensional space, to thereby place the representation of the physical objects in the representation of the physical three-dimensional space; (f) producing an indication of the placed representation of the objects in the representation of three-dimensional space; and (g) placing the physical objects in the physical three-dimensional space in conformance with the indication of the placed representation of the objects in the representation of three-dimensional space. - View Dependent Claims (22, 23, 24, 25)
-
-
26. Apparatus for placing physical objects of differing placement characteristic types in a physical three-dimensional space, comprising:
-
a library of electronically stored object placement pattern, each pattern in said library representing placement of a plurality of objects; means for electronically storing a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed; and
,an electronic controller, comprising; means for selecting a given number of representations of a first type object to be placed in the representation of said three-dimensional space; means for choosing from said library a pattern set comprising at least one pattern for placement of representation of the first type object in the representation of the three-dimensional space which minimizes the portion of said three-dimensional space used to place said given number of representations of the first type objects within a portion of the representation of said three-dimensional space consistent with at least one constraint factor; means for generating instructions for placing the physical objects in the physical three dimensional space based upon the placement of the representation of the first type object in the representation of the three-dimensional space; and means for placing said objects into said three dimensional space according to the selected patterns. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33)
-
-
34. Apparatus for placing objects of differing sizes in a three-dimensional space of a predetermined size, comprising:
-
a library of electronically stored object placement patterns, each pattern in said library representing placement of objects in a row of said three-dimensional space, which place a number of the objects in that row, said library of patterns having several different pattern types; means for electronically storing a representation of the physical objects to be placed and a representation of the physical three-dimensional space in which the physical objects are to be placed; and
,an electronic controller, comprising; means for determining which of said pattern types are feasible; means for selecting a pattern set comprising at least one pattern from each feasible pattern type which minimizes the portion of said three-dimensional space used to place a given number of first type objects within said three-dimensional space consistent with at least one constraint factor first means for choosing which of the selected patterns minimizes the portion of said representation of said three-dimensional space used to place a given number of representations of first type objects consistent with said constraint factor associated therewith; means for identifying which pattern minimizes the portion of said representation of said three-dimensional space used to place the representation of objects of a succeeding size in the unfilled pattern for each row, if a pattern remains unfilled after all representations of objects of said first size are placed; means for generating instructions for placing the physical objects in the physical three dimensional space based upon the placement of the representation of the first type object in the representation of the three-dimensional space; and means for placing said objects into said three-dimensional space according to the selected patterns. - View Dependent Claims (35, 36, 37, 38, 39, 40)
-
-
41. Apparatus for placing of objects of at least two differing placement characteristic types in a three-dimensional space, comprising:
-
a library of electronically stored patterns, each pattern representing placement of objects within said pattern; means for identifying linking restrictions between said objects of differing placement characteristic types, said linking restrictions comprising selected patterns which may not be employed for placement of differing object types in a pattern within said three-dimensional space; means for selecting a pattern set comprising at least one pattern which places said differing placement characteristic type objects without violating said linking restrictions; means for generating instructions for placing the physical objects in the physical three dimensional space based upon the placement of the representation of the first type object in the representation of the three-dimensional space; and means for placing said objects into said three-dimensional space according to the selected patterns. - View Dependent Claims (42, 43, 44)
-
Specification