Method and apparatus for placing parts in a bounded region
First Claim
1. A process for placing a part in a predetermined region wherein the part is defined by a corresponding part boundary and the predetermined region is defined by a region boundary, the process comprising the steps of:
- (a) placing the part in a first location of the predetermined region;
(b) identifying area elements which extend from the part boundary of the part;
(c) computing the area of each of the area elements;
(d) assigning a weight value to each of the area elements, wherein each weight value is a function of a distance from a point on the part to a predetermined location of the area element;
(e) computing a first weighted sum of the area elements surrounding the part boundary in the first location of the predetermined region;
(f) placing the part in a second different location of the predetermined region;
(g) identifying area elements which extend from the part boundary of the part;
(h) computing the area of each of the area elements;
(i) assigning a weight value to each of the area elements, wherein each weight value is a function of a distance from a point on the part to a predetermined location of the area element;
(j) computing a second weighted sum of the area elements surrounding the part boundary in the second different location of the predetermined region;
(k) comparing the first weighted sum to the second weighted sum; and
(l) placing the part in a first one of the first and second locations of the predetermined boundary having the lowest weighted sum.
1 Assignment
0 Petitions
Accused Products
Abstract
A process for placing a part in a predetermined region is described. The part is defined by a part boundary and the predetermined region is defined by a region boundary. The process includes the steps of identifying corner locations of the bounded region in which parts may be placed and minimizing waste during part placement. Waste minimization may be accomplished by placing the part in a plurality of different locations in the predetermined region and at each location identifying area elements which extend from the part boundary of the part, computing the area of each of the area elements, assigning a weight value to each of the area elements and computing a weighted sum of the area elements surrounding the part boundary in each of the locations of the predetermined region. Waste is minimized at a first one of the plurality of locations of the predetermined boundary having the lowest weighted sum.
72 Citations
44 Claims
-
1. A process for placing a part in a predetermined region wherein the part is defined by a corresponding part boundary and the predetermined region is defined by a region boundary, the process comprising the steps of:
-
(a) placing the part in a first location of the predetermined region; (b) identifying area elements which extend from the part boundary of the part; (c) computing the area of each of the area elements; (d) assigning a weight value to each of the area elements, wherein each weight value is a function of a distance from a point on the part to a predetermined location of the area element; (e) computing a first weighted sum of the area elements surrounding the part boundary in the first location of the predetermined region; (f) placing the part in a second different location of the predetermined region; (g) identifying area elements which extend from the part boundary of the part; (h) computing the area of each of the area elements; (i) assigning a weight value to each of the area elements, wherein each weight value is a function of a distance from a point on the part to a predetermined location of the area element; (j) computing a second weighted sum of the area elements surrounding the part boundary in the second different location of the predetermined region; (k) comparing the first weighted sum to the second weighted sum; and (l) placing the part in a first one of the first and second locations of the predetermined boundary having the lowest weighted sum. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A process for placing a plurality of parts in a predetermined region wherein each of the parts is defined by a corresponding part boundary and the predetermined region is defined by a region boundary, the process comprising the steps of:
-
(a) placing at least a portion of the part boundary of a first one of the plurality of parts proximate a portion of the region boundary; (b) selecting a corner location in the predetermined region; and (c) placing a second one of the plurality of parts in the corner location. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A process for placing a plurality of parts in a predetermined region having at least two predetermined boundaries, the process comprising the steps of:
-
(a) selecting a first corner location in the predetermined region wherein the step of selecting the first corner location includes the steps of;
(1) identifying a part to be placed in the predetermined region;
(2) orienting the part in a particular direction with respect to the boundaries of the predetermined region;
(3) generating a configuration space path; and
(4) identifying one or more break points in the configuration space path wherein each of the one or more breakpoints in the configuration space path corresponds to a corner location for that particular part in the predetermined region; and(b) positioning a first one of the plurality of parts in the first corner location; (c) selecting a second corner location; and (d) positioning a second one of the plurality of parts in the second corner location. - View Dependent Claims (16)
-
-
17. A process for placing parts in a predetermined region having at least two predetermined boundaries, the process comprising the steps of:
-
(a) selecting a first corner location in the predetermined region; (b) positioning a first one of the plurality of parts in the first corner location wherein the first one of the plurality of parts has a first edge and a second edge; (c) selecting a second corner location; and (d) positioning a second one of the plurality of parts in the second corner location and wherein the step of selecting the first corner location includes the steps of; (a1) moving a first one of the first and second edges of the first part to a first one of a boundary defining a first end of the predetermined region and a boundary defining an edge of the predetermined region such that the first one of the first and second edges of the first part is disposed proximate the first one of the boundary defining a first end of the predetermined region and the boundary defining an edge of the predetermined region; and (a2) moving a second one of the first and second edges of the first part to a second one of the boundary defining a first end of the predetermined region and the boundary defining an edge of the predetermined region such that the second one of the first and second edges of the first part is disposed proximate the second one of the boundary defining the first end of the predetermined region and the boundary defining an edge of the predetermined region. - View Dependent Claims (18, 19, 20, 21)
-
-
22. A process for selecting an order in which to place a plurality of parts in a region having a predetermined boundary, the process comprising the steps of:
-
(a) computing a probability value for each of the plurality of parts wherein each probability value is proportional to a characteristic dimension of the respective part; (b) storing each probability value in a database; and (c) computing a first order in which to place the parts, wherein the computing step uses the probability value computed in the step of computing a probability value. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35)
-
-
36. Apparatus for placing a parts in a predetermined region having predetermined boundaries, the apparatus comprising:
-
(a) means for selecting a first corner location in the predetermined region; (b) means for positioning a first one of the plurality of parts in the first corner location; (c) means for selecting a second corner location; and (d) means for positioning a second one of the plurality of parts in the second corner location. - View Dependent Claims (37, 38, 39)
-
-
40. Apparatus for selecting an order in which to place a plurality of parts in a region having a predetermined boundary, the apparatus comprising:
-
(a) means for computing a probability value for each of the plurality of parts wherein each probability value is proportional to a characteristic dimension of the respective part; (b) means for storing each probability value in a database; and (c) means for computing a first order in which to place the parts, wherein the computing step uses the probability value computed in the step of computing a probability value. - View Dependent Claims (41, 42, 43, 44)
-
Specification