Nova Patents
EP0507375B1

Method of determining free subareas and free spaces

Abstract

This record has no abstract on file.

EP0507375B1, drawing sheet 1
Sheet 1 of 53

Term

Term ended

Expired 16 March 2012, 14.5 years ago.

  1. Priority
  2. Filed
  3. Granted
  4. Expired
  5. Today

2 claims: 2 independent, 0 dependent

  1. 1
    Method of determining free subareas on an area partially covered with essentially rectangular objects, wherein an essentially rectangular area to be covered having dimensions X and Y is depicted 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, the corresponding element of the matrix being assigned 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 (xl, yl) = B and (xl-1, yl) = A and (xl, yl-1) = A and (xl+1, yl) = A (xl, yl+1) = A (I) for the corresponding element in the matrix; a matrix reduction being carried out, after determining the elements xl, yl 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 or a null 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 deriving one row from predetermined rows L, L+1 by determining, for each element (xl, yl) of each row, whether (xl,yl) = B and (xl+1, yl) = B (II), in which case the element (xl,yl)':= B in the reduced matrix (x,y)', and if (II) is not satisfied, the element (xl,yl)': = A;the number of columns being reduced by deriving one column from predetermined columns L, L+1 by determining, for each element (x,y) of each column, whether (xl,yl) = B and (xl,yl+1) = B (III), in which case the element (xl,yl)': = B in the reduced matrix (x,y)', and if (III) is not satisfied, the element (xl,yl)': = A;the dimensions of the free subareas determined using (I) being determined by creating 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 to sum the dimensions of the rows or columns l, l+1. Procédé de détermination de surfaces libres sur une aire partiellement couverte d'objets sensiblement rectangulaires, dans lequel une aire sensiblement rectangulaire à couvrir, de dimensions X et Y, est représentée sous la forme d'une matrice bidimensionnelle (x, y) comportant x rangées et y colonnes, chaque élément de la matrice représentant un rectangle sur l'aire et étant précisé qu'il est établi pour chaque élément si le rectangle correspondant de l'aire est libre ou occupé, l'élément correspondant de la matrice prenant une première valeur logique (A) dans le premier cas mentionné et une seconde valeur logique (B) dans le second cas mentionné, étant précisé qu'il y a une surface libre sur l'aire si (xl, yl) = B et (xl-1, yl) = A et (xl, yl-1) = A et (xl+1, yl) = A et (xl, yl+1) = A (I) pour l'élément correspondant de la matrice;une réduction de la matrice étant effectuée après que soient déterminés les éléments xl, yl qui satisfont (I), en réduisant toujours de un le nombre de rangées ou le nombre de colonnes de la matrice selon une séquence prédéterminée, par pas consécutifs jusqu'à ce qu'il ne reste qu'une matrice (1, 1) ou une matrice nulle, les surfaces libres possibles étant toujours déterminées après un pas de réduction à l'aide de (I);le nombre de rangées étant réduit en retirant des rangées prédéterminées l,l+1 une rangée, en déterminant, pour chaque élément (xl, yl) de chaque rangée, si, oui ou non, (xl, yl) = B et (xl+1, yl) = B (II), cas dans lequel l'élément (xl, yl)': = B dans la matrice réduite (x, y)', et si (II) n'est pas satisfait l'élément (xl, yl)': = A;le nombre de colonnes étant réduit en retirant des colonnes prédéterminées l,l+1 une colonne, en déterminant pour chaque élément (x, y) de chaque colonne, oui ou non, (xl, yl) = B et (xl, yl+1) = B (III), cas dans lequel l'élément (xl, yl)': = B dans la matrice réduite (x yl)', et si (III) n'est pas satisfait l'élément (xl, yl)': = A;les dimensions des surfaces libres déterminées à l'aide de (I) étant déterminées en créant une table de dimension à la fois pour les rangées et pour les colonnes de la matrice et en ajustant la table de dimension pour les rangées ou pour les colonnes en un pas correspondant au cours de la réduction de la matrice pour faire la somme des dimensions des rangées ou des colonnes l, l+1. Verfahren zur Bestimmung von freien Teilbereichen von einem teilweise mit Objekten in Gestalt von Rechtecken bedeckten Bereich, bei welchem Verfahren ein im wesentlichen rechteckiger abzudeckender Bereich, der die Dimensionen X und Y aufweist, in Gestalt einer zweidimensionalen Matrix (x, y) dargestellt wird, die x Zeilen und y Spalten umfasst, wobei jedes Element der Matrix ein Rechteck auf dem Bereich darstellt und für jedes Element festgestellt wird, ob das entsprechende Rechteck in dem Bereich frei oder besetzt ist, wobei dem zugehörigen Element der Matrix ein erster logischer Wert (A) im zuerst genannten Fall und ein zweiter logischer Wert (B) im als zweites genannten Fall zugewiesen wird, wobei ein freier Teilbereich auf dem Bereich vorliegt, falls (xl,yl) = B und (xl-1,yl) = A und (xl,yl-1) = A und (xl+1,yl) = A und (x1,yl+1) = A (I) für das zugehörige Element in der Matrix ist;dass eine Matrixreduktion durchgeführt wird, nachdem die Elemente (xl,yl) festgestellt worden sind, die (I) erfüllen, indem jeweils um eins die Anzahl der Zeilen oder die Anzahl der Spalten in der Matrix in einer vorbestimmten Abfolge in aufeinanderfolgenden Schritten reduziert wird, bis eine (1,1)-Matrix oder eine Null-Matrix übrigbleibt, wobei die möglichen freien Teilbereiche immer nach einem Reduktionsschritt mit der Hilfe von (I) bestimmt werden;dass die Anzahl der Zeilen durch Ableiten einer Zeile aus vorbestimmten Zeilen 1, l+1 vermindert wird, indem für jedes Element (xl,yl) jeder Zeile bestimmt wird, ob (xl,yl) = B und (xl+1,yl) = B (II), in welchem Fall das Element (xl,yl)' : = B in der reduzierten Matrix (x, y)' gesetzt wird, und dass, falls (II) nicht erfüllt wird, das Element (xl,yl)' : = A gesetzt wird, dass die Anzahl von Spalten durch Ableiten einer Spalte aus vorbestimmten Spalten 1, l+1 vermindert wird, indem für jedes Element (xl,yl) jeder Spalte bestimmt wird, ob (xl,yl) = B und (xl,yl+1) = B (III), in welchem Fall das Element (xl,yl)': = B in der reduzierten Matrix (x, y)' gesetzt wird, und dass, falls (III) nicht erfüllt wird, das Element (xl,yl)' : = A gesetzt wird, dass die Dimensionen der freien Teilbereiche, die unter Einsatz von (I) bestimmt worden sind, bestimmt werden, indem eine Dimensionstabelle sowohl für die Zeilen als auch für die Spalten der Matrix erzeugt wird und durch Einstellen der Dimensionstabelle für die Zeilen oder für die Spalten in einem zugehörigen Schritt während der Matrixreduktion, um die Dimensionen der Zeilen oder Spalten 1, l+1 aufzusummieren.
  2. 2
    Method of determining free spaces in a space partially filled with objects essentially having the form of a right parallelepiped, wherein a space essentially having the form of a right parallelepiped and having dimensions X, Y and Z is depicted 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 it being established for each element whether the corresponding right parallelepiped in the space is free or occupied, the corresponding element of the associated matrix being assigned 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 space in the space if (xl,yl,zl) = B and (xl-1,yl,zl) = A and (xl,yl-1,zl) = A and (xl+1,yl,zl) = A and (xl,yl+1,zl) = A and (xl,yl,zl-1) = A and (xl,yl,zl+1) = A (IV) for the corresponding element in the matrix; a matrix reduction being carried out, after determining the elements (xl,yl,zl) which satisfy (IV), 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 spaces always being determined after a reduction step with the aid of (IV); the number of rows being reduced by deriving one row from predetermined rows L, l+1 by determining, for each element (xl,yl,zl) of the matrix, whether (xl,yl,zl) = B and (xl+1,yl,zl) = B (V), in which case the element (xl,yl,zl)':= B in the reduced matrix (x, y, z)', and if (V) is not satisfied, the element (xl, yl, zl)' = A;the number of columns being reduced by deriving one column from predetermined columns L, l+1 by determining whether (xl, yl, zl) = B and (xl, yl+1, zl) = B (VI), in which case the element (xl, yl, zl)': = B in the reduced matrix (x, y, z)', and if (VI) is not satisfied, the element (xl, yl, zl)' = A;the number of layers being reduced by deriving one layer from predetermined layers L, L+1 by determining whether (xl, yl, zl) = B and (xl, yl, zl+1) = B (VII), in which case the element (xl, yl, zl)': = B in the reduced matrix (x, y, z)', and if (VII) is not satisfied, the element (xl, yl, zl)' = A;the dimensions of the free spaces determined using (IV) being found by creating 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 to sum the dimensions of the rows, columns or layers l, l+1. Procédé de détermination d'espaces libres dans un volume partiellement rempli d'objets ayant sensiblement la forme d'un parallélépipède rectangle, dans lequel un volume ayant sensiblement la forme d'un parallélépipède rectangle et de dimension X, Y et Z, est représenté sous la forme d'une matrice tridimensionnelle (x, y, z) comportant x rangées, y colonnes et z couches, chaque élément de la matrice représentant un parallélépipède rectangle dans le volume et étant précisé qu'il est établi pour chaque élément si oui ou non, le parallélépipède rectangle correspondant dans le volume est libre ou occupé, l'élément correspondant de la matrice associée prenant une valeur logique (A) dans le premier cas mentionné et une seconde valeur logique (B) dans le second cas mentionné, étant précisé qu'il existe un espace libre dans le volume si (xl, yl, zl) = B et (xl-1, yl, zl) = A et (xl, Yl-1, zl) = A et (xl+1, yl, zl) = A et (xl, yl+1, zl) = A et (xl, yl, zl-1) = A et (xl, yl, zl+1) = A (IV) pour l'élément correspondant de la matrice;une réduction de la matrice s'effectuant après que soient déterminés les éléments (xl, yl, zl), qui satisfont (IV), en réduisant de un le nombre de rangées ou le nombre de colonnes ou le nombre de couches de la matrice, selon une séquence prédéterminée, par pas consécutifs, jusqu'à ce qu'il ne reste qu'une matrice (1, 1, 1) ou une matrice nulle, les espaces libres possibles étant toujours déterminés après un pas de réduction à l'aide de (IV);le nombre de rangées étant réduit en retirant des rangées prédéterminées l,l+1 une rangée, en déterminant, pour chaque élément (xl, yl, zl) de la matrice, si oui ou non, (xl, yl, zl) = B et (xl-1, yl, zl) = B (V), cas dans lequel l'élément (xl, yl, zl)': = B dans la matrice réduite (x, y, z)' et si (V) n'est pas satisfait, l'élément (xl, yl, zl)' = A;le nombre de colonnes étant réduit en retirant des colonnes prédéterminées l,l+1 une colonne, en déterminant si, oui ou non, (xl, yl, zl) = B et (xl, yl+1, zl) = B (VI), cas dans lequel l'élément (xl, yl, zl)': = B dans la matrice réduite (x, y, z)' et si (VI) n'est pas satisfait l'élément (xl, yl, zl)' = A;le nombre de couches étant réduit en retirant des couches prédéterminées l,l+1 une couche, en déterminant si, oui ou non, (xl, yl, zl) = B et (xl, yl, zl+1) = B (VII), cas dans lequel l'élément (xl, yl, zl)': = B dans la matrice réduite (x, y, z)', et si (VII) n'est pas satisfait, l'élément (xl, yl, zl)' = A;les dimensions des espaces libres déterminés à l'aide de (IV) étant trouvées en créant une table de dimension pour les rangées et pour les colonnes et pour les couches de la matrice et en ajustant la table de dimension pour les rangées, pour les colonnes ou pour les couches dans un pas correspondant au cours de la réduction de la matrice pour faire la somme des dimensions des rangées, des colonnes ou des couches l,l+1. Verfahren zur Bestimmung von freien Räumen in einem teilweise mit Objekten, die im wesentlichen die Gestalt eines Parallelepipeds mit rechten Winkeln aufweisen, gefüllten Raum, bei welchem Verfahren der zu füllende Raum, der im wesentlichen die Gestalt eines Parallelepipeds mit rechten Winkeln aufweist und der die Dimensionen X, Y und Z aufweist, die in Gestalt einer dreidimensionalen Matrix (x, y, z) dargestellt wird, die x Zeilen, y Spalten und z Schichten umfasst, wobei jedes Element der Matrix ein Parallelepiped mit rechten Winkeln in dem Raum darstellt und für jedes Element festgestellt wird, ob das zugehörige Parallelepiped mit rechten Winkeln in dem Raum frei oder besetzt ist, wobei dem zugehörigen Element der zugeordneten Matrix ein erster logischer Wert (A) in dem zuerst genannten Fall und ein zweiter logischer Wert (B) in dem als zweites genannten Fall zugewiesen wird, wobei ein freier Raum in dem Raum vorliegt, falls (xl, yl, zl) = B und (xl-1, yl, zl) = A und (xl, yl-1, zl) = A und (xl+1,yl,zl) = A und (xl,yl+1,zl) = A und (xl,yl,zl-1) = A und (xl,yl,zl+1) = A (IV) für das zugehörige Element in der Matrix ist, dass eine Matrixreduktion durchgeführt wird, nachdem die Elemente (xl,yl,zl) festgestellt worden sind, die (IV) erfüllen, indem um eins die Anzahl von Zeilen oder die Anzahl von Spalten oder die Anzahl von Schichten in der Matrix in einer vorbestimmten Abfolge in aufeinanderfolgenden Schritten reduziert wird, bis eine (1,1,1)-Matrix oder eine Null-Matrix übrigbleibt, wobei die möglichen freien Räume immer nach einem Reduktionsschritt jeweils mit der Hilfe von (IV) bestimmt werden;dass die Anzahl von Zeilen durch Ableiten einer Zeile aus den vorbestimmten Zeilen 1, l+1 vermindert wird, indem für jedes Element (xl,yl,zl) der Matrix festgestellt wird, ob (xl,yl,zl) = B und (xl+1,yl,zl) = B (V), in welchem Falle das Element (xl,yl,zl)' : = B in der reduzierten Matrix (x, y, z)' gesetzt wird, und dass, falls (V) nicht erfüllt wird, das Element (xl,yl,zl)' = A gesetzt wird;dass die Anzahl von Spalten durch Ableiten einer Spalte aus den vorbestimmten Spalten l, l+1 vermindert wird, indem festgestellt wird, ob (xl,yl,zl) = B und (xl,yl+1,zl) = B (VI), in welchem Falle das Element (xl,yl,zl)' : = B in der reduzierten Matrix (x, y, z)' gesetzt wird;und dass, falls (VI) nicht erfüllt ist, das Element (xl,yl,zl)' = A gesetzt wird;dass die Anzahl von Schichten durch Ableiten einer Schicht aus den vorbestimmten Schichten l, l+1 vermindert wird, indem festgestellt wird, ob (xl,yl,zl) = B und (xl,yl,zl+1) = B (VII), in welchem Falle das Element (xl,yl,zl)' : = B in der reduzierten Matrix (x, y, z)' gesetzt wird;und dass, falls (VII) nicht erfüllt ist, das Element (xl,yl,zl)' = A gesetzt wird;dass die Dimensionen der freien Räume, die unter Einsatz von (IV) festgestellt worden sind, festgestellt werden, indem eine Dimensionstabelle für die Zeilen und für die Spalten und für die Schichten der Matrix erzeugt wird und durch Einstellen der Dimensionstabelle für die Zeilen oder die Spalten oder die Schichten in einem entsprechenden Schritt während der Matrixreduktion, um die Dimensionen der Zeilen, Spalten oder Schichten l, l+1 aufzusummieren.
Independent claims2