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

Claim 7

The method of claim 3, wherein the most favorable score corresponds with the lowest score value among the respective assigned score values as scores for said plurality of portions, said plurality of objects and said possible orientations, and in substep (2) corresponding to the determination whether all dimensions of said object (Xp, Yp) are smaller than the corresponding dimensions of said portion (Xs, Ys) of said area the assigned score value is: score value=[(Xs-Xp)/Xs] k * [(Ys-Yp)/Ys] l wherein k and 1≧1.

Claim 8

The method of claim 3, wherein the step of locating on said area a plurality of free rectangular portions of said area having rectangle side (Xs and Ys) comprising the following substeps of: depicting said area in the form of a two-dimensional matrix (x, y) having x rows and y columns, each element of the matrix representing a rectangle on the area and it being established for each element whether the corresponding rectangle in the area is free or occupied; assigning to the respective elements of the 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 subarea on the area if a first equation group (I) is satisfied, which states (x l , y l )=B and (x l-1 , y l )=A and (x l , y l-1 )=A and (x l+1 , y l )=A (x l , y l+1 )=A for the corresponding element in the matrix; carrying out a matrix reduction after determining the elements x l , y 1 which satisfy (I), by always reducing by one the number of rows or the number of columns in the matrix in a predetermined sequence in consecutive steps until a (1, 1) matrix is left, the possible free subareas always being determined after a reduction step with the aid of (I); the number of rows being reduced by determining a second equation group (II) which states for each element (x l , y l ) of each row, whether (x l ,y l )=B and (x l+1 , y l )=B, in which case the element (x l ,y l )':=B in the reduced matrix (x y)', and if said equation group (II) is not satisfied, the element (x l ,y l )':=A; the number of columns being reduced by determining, for each element (x,y) of each column, whether a third equation group (III) is satisfied which states (x l ,y l )=B and (x l ,y l+1 )=B, in which case the element (x l ,y l )':=B in the reduced matrix (x,y)', and if said third equation group (III) is not satisfied, the element (x l ,y l )':=A; the dimensions of the free subareas determined using said first equation group (I) being determined by updating a dimension table both for the rows and for the columns of the matrix, and by adjusting the dimension table for the rows or for the columns in a corresponding step during the matrix reduction, each determined free subarea defining a free rectangular portion of said plurality of portions of said area.

Claim 11

The method of claim 6, wherein the most favorable score corresponds with the lowest score value among the respective assigned score values as scores for said plurality of portions, said plurality of objects and said possible orientations, and in the event of an affimative determination in substep (2) signifying that all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Ys) of said area, the assigned score value is: score value=[(Xs-Xp)/Xs] k * [(Ys-Yp)/Ys] l * [(Zs-Zp)/Zs] m wherein k, l and m>1.

Claim 12

The method according to claim 7, wherein, prior to or concurrently with the step of establishing a score, a determination is made whether said object would be sufficiently supported in said portion (Xs, Ys, Zs) of said free space, and wherein in the event said support determination is answered in the negative, said object thereby found insufficiently supported is rejected for placement.

Claim 13

The method according to claim 8, wherein four areas are defined for said object on its bottom face, which areas do not overlap each other and each of which comprise a corner point of said object, and wherein if each of said areas upon placement is supported at at least one point, said object is found sufficiently supported and said support determination is answered in the affirmative.

Claim 14

The method according to claim 9, wherein prior to the method step of defining said four areas on the bottom face of said object, there are performed a method step of locating a center of gravity on the bottom face of said object and thereafter a method step of defining an area around the located center of gravity, which defined area is to be barred from inclusion in said four areas when they are defined.

Claim 15

The method according to claim 10, wherein prior to the method step of determining whether a said object would be sufficiently supported, a method step is performed of determining whether in placing said object in said free space said object would come to rest with a lateral face against an adjacent object, and in the event of an affirmative dtermination in the method step just mentioned, the subsequent step of determining sufficient support is carried out on the basis that any of said four areas which is adjacent to said lateral face adjacent to another object does not need to be supported for an affirmation of sufficient support.

Claim 16

The method according to claim 8, wherein, prior to or concurrently with the step of establishing a score, a determination is made whether said object would be sufficiently supported in said portion (Xs, Ys, Zs) of said free space, and wherein in the event said support determination is answered in the negative, said object thereby found insufficiently supported is rejected for placement.

Claim 17

The method according to claim 12, wherein four areas are defined for said object on its bottom face, which areas do not overlap each other and each of which comprise a corner point of said object, and wherein if each of said areas upon placement is supported at at least one point, said object is found sufficiently supported and said support determination is answered in the affirmative.

Claim 18

The method according to claim 13, wherein prior to the method step of defining said four areas on the bottom face of said object, there are performed a method step of locating a center of gravity on the bottom face of said object and thereafter a method step of defining an area around the located center of gravity, which defined area is to be barred from inclusion in said four areas when they are defined.

Claim 19

The method according to claim 14, wherein prior to the method step of determining whether a said object would be sufficiently supported, a method step is performed of determining whether in placing said object in said free space said object would come to rest with a lateral face against an adjacent object, and in the event of an affirmative dtermination in the method step just mentioned, the subsequent step of determining sufficient support is carried out on the basis that any of said four areas which is adjacent to said lateral face adjacent to another object does not need to be supported for an affirmation of sufficient support.

Claim 20

The method of claim 6, wherein the step of locating in said space a plurality of free portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs) comprises the following substeps of: 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 l ,y l ,z l )=B and (x l-1 ,y l ,z l )=A and (x l ,y l-1 ,z l )=A and (x l+1 ,y l ,z l )=A and (x l ,y l+1 ,z l )=A and (x l ,y l ,z l-1 )=A and (x l ,y l ,z l+1 )=A for the corresponding element in the matrix; carrying out a matrix reduction after determining the elements (x l ,y l ,z 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 l ,y l ,z l ) of the matrix, whether a second equation group (II) is satisfied which states (x l ,y l ,z l )=B and (x l+1 ,y l ,z l )=B, in which case the element (x l ,y l ,z l )':=B in the reduced matrix (x, y, z)', and if said second equation group (II) is not satisfied, the element (x l , y l , z l )'=A; the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x l , y l , z l )=B and (x l , y l+1 , z l )=B, in which case the element (x l , y l , z l )':=B in the reduced matrix (x, y, z)', and if said third equation group (III) is not satisfied, then the element (x l , y l , z l )'=A; the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x l , y l , z l )=B and (x l , y l , z l+1 )=B, in which case the element (x l , y l , z l )':=B in the reduced matrix (x, y, z)', and if said fourth equation group (IV) is not satisfied, then the element (x l , y l , z 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, each determined free subspace defining a free rectangular parallelepiped portion of said plurality of portions of free space in said space.

Claim 23

The method of claim 17, wherein the step (b) of locating in said space a plurality of free portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs) comprises the following substeps of: 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 l ,y l ,z l )=B and (x l-1 ,y l ,z l )=A and (x l ,y l-1 ,z 1 )=A and (x l+1 ,y l ,z l )=A and (x l ,y l+1 ,z l )=A and (x l ,y l ,z l-1 )=A and (x l ,y l ,z l+1 )=A for the corresponding element in the matrix; carrying out a matrix reduction after determining the elements (x l ,y l ,z 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 l ,y l ,z l ) of the matrix, whether a second equation group (II) is satisfied which states (x l ,y l ,z l )=B and (x l+1 ,y l ,z l )=B, in which case the element (x l ,y l ,z l )':=B in the reduced matrix (x, y, z)', and if said second equation group (II) is not satisfied, the element (x l , y l , z l )'=A; the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x.sub. l, y l , z l )=B and (x l , y l+1 , z ;l )=B, in which case the element (x l , y l , z l )':=B in the reduced matrix (x, y, z)', and if said third equation group (III) is not satisfied, then the element (x l , y l , z l )'=A; the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x l , y l , z l )=B and (x l , y l , z l+1 )=B, in which case the element (x l , y l , z l )':=B in the reduced matrix (x, y, z)', and if said fourth equation group (IV) is not satisfied, then the element (x l , y l , z 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, each determined free subspace defining a free rectangular parallelepiped portion of said plurality of portions of free space in said space.