Method of packing rectangular objects in a rectangular area or space by determination of free subareas or subspaces

A method for optimally placing objects in the shape of a rectangular parallelepiped in a space partially filled with objects in said form, comprising the steps of:

• measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;
• depicting a space essentially having the form of a right parallelepiped and having dimensions X, Y and Z in the form of three-dimensional matrix (x,y,z) having x rows, y columns and z layers, each element of the matrix representing a right parallelepiped in the space and establishing for each element whether the corresponding right parallelepiped in the space is free or occupied,
• assigning the corresponding element of the associated matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subspace in the space if a first equation group (I) is satisfied which states (x.sub.l,y.sub.l,z.sub.l)=B and (x.sub.l-1,y.sub.l,z.sub.l)=A and (x.sub.l,y.sub.l-1,z.sub.1)=A and (x.sub.l+1,y.sub.l,z.sub.l)=A and (x.sub.l,y.sub.l+1,z.sub.l)=A and (x.sub.l,y.sub.l,z.sub.l-1)=A and (x.sub.l,y.sub.l,z.sub.l+1)=A for the corresponding element in the matrix;
• carrying out a matrix reduction after determining the elements (x.sub.l,y.sub.l,z.sub.l) which satisfy said first equation group (I), by reducing by one the number of rows or the number of columns or the number of layers of the matrix in a predetermined sequence in consecutive steps until a (1,1,1) matrix or a null matrix is left, the possible free subspaces, if any, always being determined after a reduction step with the aid of said first equation group (I);
• the number of rows being reduced by determining, for each element (x.sub.l,y.sub.l,z.sub.l) of the matrix, whether a second equation group (II) is satisfied which states (x.sub.l,y.sub.l,z.sub.l)=B and (x.sub.l+1,y.sub.l,z.sub.l)=B, in which case the element (x.sub.l,y.sub.l,z.sub.l)':=B in the reduced matrix (x, y, z)', and if said second equation group (II) is not satisfied, the element (x.sub.l, y.sub.l, z.sub.l)'=A;
• the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x.sub.l, y.sub.l, z.sub.l)=B and (x.sub.l, y.sub.l+1, z.sub.l)=B, in which case the element (x.sub.l, y.sub.l, z.sub.l)':=B in the reduced matrix (x, y, z)', and if said third equation group (III) is not satisfied, then the element (x.sub.l, y.sub.l, z.sub.l)'=A;
• the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x.sub.l, y.sub.l, z.sub.l) =B and (x.sub.l, y.sub.l, z.sub.l+1)=B, in which case the element (x.sub.l, y.sub.l, z.sub.l)':
• =B in the reduced matrix (x, y, z)', and if said fourth equation group (IV) is not satisfied, then the element (x.sub. l, y.sub.l, z.sub.l)'=A;
• finding the dimensions of the free subspaces determined using said first equation group (I) by updating a dimension table for the rows and for the columns and for the layers of the matrix, and by adjusting the dimension table for the rows or the columns or the layers in a corresponding step during the matrix reduction, and
• placing in said free subspaces said objects fitting into said free subspaces.

A method for optimally placing rectangular objects on an area being possibly, but not necessarily, already partially covered with rectangular objects, comprising the steps of:

• measuring the dimensions of the rectangle sides (Xp and Yp) of a plurality of said objects;
• locating on said area a plurality of free rectangular portions of said area having rectangle sides (Xs and Ys);
• establishing a score for each one of said free rectangular portions of said area, for each of said objects, and for each of two possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said area, by assigning score values, in respective substeps, corresponding to the following determinations:
• (1) whether said object in a said orientation is too large for fitting in said portion of said area;
• (2) whether all dimensions of said object (Xp, Yp) are smaller than the corresponding dimensions of said portion (Xs, Ys) of said area;
• (3) whether one dimension of said portion (Xs, or Ys) of said area corresponds to one dimension of said object (Xp or Yp), and
• (4) whether two dimensions of said portion (Xs, and Ys) of said area correspond to two dimensions of the object (Xp and Yp),
• said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3 or 4) of said substeps which produces an affirmative answer, and
• thereafter selecting and placing an object in a free area portion and in an orientation for which a most favorable score was established among respective scores for said plurality of portions and said plurality of objects and said orientations.

A method for optimally placing objects in the shape of a rectangular parallelepiped in a space being possibly, but not necessarily, already partially filled with objects in said form, comprising the steps of:

• measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;
• locating in said space a plurality of portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs);
• and
• establishing a score for each of said portions of free space, for each of said objects, for each of six possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said free space, by assigning score values, in respective substeps, corresponding to the following determinations:
• (1) whether an object (Xp, Yp, Zp) in a said orientation is too large for fitting in said portion (Xs, Ys, Zs) of said space;
• (2) whether all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Zs) of said free space;
• (3) whether one dimension of said portion (Xs, Ys or Zs) of said free space corresponds to one dimension of said object (Xp, Yp or Zp);
• (4) whether two dimensions of said portion (Xs, Ys, Zs) of said free space correspond to two dimensions of said object, and
• (5) whether three dimensions of said portion (Xs, Ys, Zs) of said free space correspond to three dimensions of said object,
• said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3,4 or 5) of said substeps which produces an affirmative answer, and
• thereafter selecting and placing an object in a portion of free space and in an orientation for which a most favorable score was established among respective scores for said plurality of portions and said plurality of objects and said orientations.

A method for optimally placing objects in the shape of a rectangular parallelepiped in a space available for storage or transportation of said objects and being possibly, but not necessarily, already partially occupied with objects of said shape, comprising the steps of:

• (a) measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;
• (b) locating in said space a plurality of portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs);
• (c) establishing a score for each of said portions, for each of said objects, for each of six possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said space, by assigning score values, in respective substeps, corresponding to the following determinations:
• (1) whether an object (Xp, Yp, Zp) in a said orientation is too large for fitting in said portion (Xs, Ys, Zs) of said space;
• (2) whether all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Zs) of said free space;
• (3) whether one dimension of said portion (Xs, Ys or Zs) of said free space corresponds to one dimension of said object (Xp, Yp or Zp);
• (4) whether two dimensions of said portion (Xs, Ys, Zs) of said free space correspond to two dimensions of said object, and
• (5) whether three dimensions of said portion (Xs, Ys, Zs) of said free space correspond to three dimensions of said object,
• said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3,4 or 5) of said substeps which produces an affirmative answer;
• (d) selecting and placing an object in a free portion of free space and in an orientation for which a most favorable score was established among respective scores for said plurality of said portions and said plurality of objects and said possible orientations, thereby leaving unoccupied a free space portion of the originally available space;
• (e) adding to said plurality of said objects a next object, if any, and measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of said next object;
• (f) repeating method steps (b) through (e) with the plurality of space portions defined in step (b) henceforth being a plurality of portions of free space remaining after an immediately previous performance of method steps (b) through (e), until either all objects of said plurality are placed in previously free space or else no more objects of said plurality can fit in space left free by the most recent performance of method steps (b) through (e).