Brevet FR2524176A1 — publié le 19830930

Procédé et dispositif électronique pour l'arrangement de fi- gures au moins bidimensionnelles. La présente invention se rapporte à un procédé et à un dispositif électronique pour l'arrangement ou rangement de figures au moins bidimensionnelles La réalisation d'un arran- gement optimal de diverses figures suivant un ou plusieurs points de vue quelconques est une tâche fréquente dans le domai- ne technique Ce problème se présente de façon classique lors de l'arrangement de figures planes, notamment lors de la recher- cher de l'utilisation maximale d'une surface de base donnée. La détermination de l'arrangement optimale des fi- gures bidimensionnelles devant être logéessur une surface donnée, en vue de l'obtention de vides(chutes) minimaux, ne représente qu'un des problèmes des plus simples parmi des problèmes sem- blables En effet, dans de nombreux cas, la simple détermination des quantités maximales à loger est insuffisante car il faut également tenir compte d'autres facteurs, par exemple de direc- tions, dessinsetc préférentiels du point de vue technologi- que. Dans la technique actuelle, les problèmes sont sou- vent plus compliqués qu'antérieurement, d'une part en raison du nombre accru des conditions à observer et d'autre part en raison du caractère souvent tridimentionnel du problème Des problèmes semblables d'arrangement se présentent souvent dans la découpe de panneaux, de textiles ou de cuir, ainsi que dans la détermination du remplissage optimal de l'espace dans le cas de moyens de transport Toutefois, des problèmes semblables doivent être résolus également lors de l'agencement d'espaces spéciaux très peu volumineux, par e Aemple le compartiment mo- teur de véhicules automobiles, le compartiment de machines de centrales, le compartimexft de machines de navirel etc. Pour résoudre de tels problèmes, on utilise généra- lement avantageusement un calculateur ou un système de concep- tion graphique. A l'aide de ces systèmes, les problèmes sont générale- ment résolus par un procédé interactif, mais on connaît égale- ment déjà un procédé automatique utilisable dans des conditions déterminées. Les méthodes usuelles à l'heure actuelle se carac- térisent généralement par la longue durée de calcul du calcu- lateur, ainsi que par le fait que l'optimisation est en générale s effectuée dans l'intérêt d'un objectif (par exemple en vue de l'obtention d'une utilisation maximale de la matière), sans tenir compte des conditions technologiques. Le problème à résoudre par la présente invention est la réalisation d'un procédé et d'un dispositif permettant d'optimiser de tels agencements en tenant compte de certaines conditions Il s'agit là de résoudre un problème extrêmement important, permettant de résoudre de façon plus efficace des problèmes semblables dans de nombreuses branches de l'industrie. L'objet de la présente invention est de mettre au point,en vue de résoudre ce problème, un procédé et un disposi- tif permettant d'effectuer de façon rapide des problèmes d'opti- misation en respectant simultanément diverses conditions. L'objet de la présenteinvention est de réaliser un procédé suivant lequel on mémorise par voie vectorielle les données des figures à arranger, on détermine les vides entre les figures déjà arrangées et on essaye d'insérer les figures à arranger dans les vides entres les figures déjà arrangées, en analysant en décomposition rangées-colonnes les nouveaux arrangements obtenus par cette insertion et les éventuels chevau- chements ou recouvrements et en déterminant l'arrangement optimal. Suivant un mode de réalisation avantageux du procédé conforme à l'invention, on ne contrôle le chevauchement ou re- couvrement de la figure à arranger par rapport aux figures déjà arrangées, mémorisées par voie vectorielle, qu'en relation avec celles qui se trouvent aux alentours du vide choisi en vue de l'arrangement de la nouvelle figure à arranger. Le dispositif convenant à la mise en oeuvre du pro- cédé ci-dessus comprend; suivant l'invention, une mémoire de vecteurs, un convertisseur vecteurs-trame, un générateur de fenêtre, un générateur d'arrangement, un analyseur d'occupation, une unité de commande, un appareil indicateur, une source exté- rieure et des organes d'intervention, la mémoire de vecteurs étant reliée à l'unité de commande, au générateur d'arrange- ment et au convertisseur vecteurs-trame, la source extérieure étant reliée au générateur d'arrangement et à l'unité de com- mande, l'unité de commande étant reliée au générateur d'arran- gement, au générateur de fenêtre, à l'analyseur d'occupation et aux organes d'intervention, l'analyseur d'occupation étant relié au convertisseur vecteurs-trame, le convertisseur verteuit- trame étant relié à l'appareil indicateur, le générateur de fenêtre étant relié au générateur d'arrangement et àlamémoire de vecteuiz ou au convertisseur vecteurs -trame. Suivant un mode de réalisation avantageux du dis- positif conforme à l'invention, la mémoire de vecteur comprend un mémoire, un transformateur de forme double-normale, une mé- moire de passage ou mémoire-file, une unité de comparateur ainsi qu'une mémoire-pile, le transformateur de forme double-noimale étant relié à la mémoire-file, la mémoire-file étant reliée à l'unité de comparateur et à la mémoire, l'unité de comparateur étant reliée à la mémoire et à la mémoire-pile et la mémoire- pile étant reliée à la mémoire. Suivant un autre mode de réalisation avantageux du dispositif conforme à l'invention, le générateur d'arrange- ment comprend une unité de commande interne, une mémoire de fi- gures, un multiplexeur, un transformateur de position, une unité de chevauchement ou recouvrement, un générateur de valeur scalaire,une mémoire d'environnement, une mémoire-pile de valeur scalaire etune unité de commande de mémoire-pile, l'unité de commande interne étant reliée à la mémoire de figures, à l'uni- té de commande de mémoire-pile et au multiplexeur, le multi- plexeur étant relié à l'unité de commande de mémoire-pile et au transformateur de position, le transformateur de position étant relié à l'unité de chevauchement ou recouvrement et à la mémoire-pile de valeur scalaire, l'unité de chevauchement ou recouvrement étant reliée au générateur de valeur scalaire et à la mémoire d'environnement, le générateur de valeur scalaire étant relié à la mémoire-pile de valeur scalaire, la mémoire-pile de valeur scalaire étant reliée à l'unité de commande de mémoi- re-pile et la mémoire de figuresétant reliée au transformateur de position Suivant un autre mode de r;alisat on avantageux lu dispositif conforme à l'invention, l Vanalyseur d'occupation comprend une unité de séparation, une unité de discriminateur, un sommateur de vides, un compteur de coordonnées, un registre de coordonnées, un compteur de vides, un générateur de centre de gravité, un générateur d'espace, une logique d'inscription, une mémoire de paramètres une unité d'équivalence de limiteur minimum, un registre limiteur de minimum, une logique de magi - tude, un registre de longueurs, une unité d'équivalence de lon- gueur, un registre d'intervalles une unité d'équivalence d'in- tervalle, un registre d'adresse, un registre d'ordres de grandeur, une unité d'équivalence d'ordre de grandeur et une mémoire-pile d'ordre de grandeur, l'unité de séparation étant reliée au som- mateur de vides, au compteur de coordonnées et à l'unité de dis- criminateur, l'unité de discriminateur étant reliée au sommateur de vides, au registre de coordonnées, au compteur de vides, à la logique de magnitude, à l'unité d'équivalence de longueur, à la logique d'inscription et à l'unité d'équivalence d'inter- valle, le registre de coordonnées étant relié à la logique d'inscription et à l'unité d'équivalence d'intervalle, le comp- teur de videsétant relié au générateur de centre de gravité, au générateur d'espace, à la logique d'inscription, à l'unité d'équivalence de longueur et à l'unité d'équivalence de limiteur de minimum, l'unité d'équivalence de limiteur de minimum étant reliée à la logique de magnitude et au registre de limiteur de minimum, la logique de magnitude étant reliée à la logique d'ins- cription, l'unité d'équivalence de longueur étant reliée à la logique d'inscription et au registre de longueurs, le registre de longueur étant relié à la mémoire de Daramètres, le registre d'adressesétant relié à la mémoire de paramètreset à l'unité d'équivalence d'intervalle, l'unité d'équivalence d'intervalle étant reliée à la logique d'inscription et au registre l'inter- valles, le registre d'intervallesétant relié à la mémoire de para- mètreset à l'unité d'équivalence d'ordre de grandeur, l'unité d'équivalence d'ordre de grandeur étant reliée à la mémoire de paramètre% à la mémoire-pile d'ordre de grandeur et au registre d'ordresde grandeur, la mémoire-pile d'ordre de grandeur étant reliée à la mémoire de paramètrez le compteur de coordonnées étant relié au registre de coordonnées, le générateur de centre de gravité et le générateur d'espace étant reliésà la logique d'ins- cription et la logique d'inscription étant reliée à la mémoire de paramètres. s Pour la description plus détaillée du procédé et du dispositif conformes à l'invention, on va se référer aux dessins annexés sur lesquels la figure 1 représente le schéma synoptique d'un mode de réalisation avantageux du dispositif conforme à l'inven- tion; la figure 2 représente un schéma synoptique d'un autre mode de réalisation avantageux du dispositif conforme à l'invention; la figure 3 représente le schéma synoptique d'un is mode de réalisation avantageux de la mémoire de vecteursutilisée dans le dispositif conforme à l'invention; la figure 4 représente le schéma synoptique d'un mode de réalisation avantageux du générateur d'arrangement utilisé dans le dispositif conforme à l'invention; La figure 5 représente le schéma synoptique d'un mode de réalisation de l'analyseur d'occupation utilisé dans le dispositif conforme à l'invention. Le dispositif conforme à l'invention tel qu'illus- tré par les figures let 2 comprend une mémoire de vecteurs 1, un convertisseur vecteurs-trame 2, un générateur de fenêtre 3, un générateur d'arrangement 4, un analyseur d'occupation 5, une unité de commande 6, un appareil indicateur 7, une source exté- rieure 8 et des organes d'intervention 9. La mémoire de vecteurs 1 est reliée à l'unité de commande 6 et au générateur d'arrangenfent 4 ainsi qu'au conver- tisseur vecteur-trame 2 La source extérieure 8 est reliée au générateur d'arrangement 4 et l'unité de commande 6 L'unité de commande 6 est reliée au générateur d'arrangement 4, au géné- rateur de fenêtre 3, à l'analyseur d'occupation 5 et aux organes d'intervention 9 L'analyseur d'occupation 5 est relié au con- vertisseur vecteuxg-trame 2 et le convertisseur vecteuz-trame 2 est relié à l'appareil indicateur 7 Le générateur de fenêtre 3 est relié au générateur d' arrangement 4 ainsi qu'à la mémoire de vecteurs I (figure 1) ou au convertisseur vecteuis-trame 2 (fi- gure 2). On va décrire ci-après le mode de fonctionnement des variantes de réalisation du dispositif suivant les figures 1 et 2, en distinguant entre le mode de fonctionnement interactif et le mode de fonctionnement automatique. Dans le mode de fonctionnement interactif, les figures déjà mémorisées dans la mémoire de vecteursl sontaffiché par l'intermédiaire du convertisseur vecteum-trame 2, sur l'appa- reil indicateur 7 Sous l'action des organes d'intervention 9, l'unité de commande 6 procède au décalage virtuel par rotation ou translation des figures dans la mémoire de vecteurs 1 Ainsi, la nouvelle figure apparaît dans sa position virtuelle sur l'appa- reil indicateur 7, c'est-à-dire que le résultat de l'intervention est visualisé sur l'appareil indicateur 7. Ce mode de fonctionnement dit interactif n'est cepen- dant que d'une importance secondaire à côté du mode de fonction- nement automatique Pendant le mode de fonctionnement automatique, l'unité de commande 6 reçoit de l'analyseur d'occupation 5 des informations concernant les vides entre les figures déjà arran- gées L'unité de commande 6 examine les données des figures à arran- ger susceptibles d'être appelées dans la source extérieure 8 et compte tenu de ces données, elle détermine les paramètres du générateur de fenêtre 3, donc la zone qui, virtuellement découpée dans l'ensemble de la surface disponible, doit être utilisée pour l'arrangement des figures Ensuite, la description vectorielle des figures à arranger, provenant de la source extérieure 8, ainsi que les données de la partie de l'espace sélectionnéapar le gé- nérateur de fenêtre 3, parviennent au générateur d'arrangement 4 dans lequel est réalisé un arrangement virtuel concret sur la base de la commande de l'unité de commande 6, et compte tenu d'autres conditions'liées à l'arrangement, cela par l'examen de la valeur limite d'essais d'arrangement répétés Après sélection de l'arrangement, la nouvelle figure arrangée est inscrite, sur l'ordre de l'unité de commande 6, à l'endroit correspondant de la mémoire de vecteurs 1. Il se produit ensuite un nouvel essai d'arrangement avec une nouvelle figure provenant de la source extérieure 8, et le processus se répète de façon cyclique Ce processus se termine lorsque l'unité de commande 6, sur la base de l'in- formation de l'analyseur d'occupation 5, ne peut pas appeler dans la source extérieure une figure pour l'arrangement de laquelle est disponible un vide suffisant. La figure 3 représente le schéma synoptique d'une variante de rélisation concrète de la mémoire de vecteurs 1 utilisé dans le dispositif 1 Selon cette figure, la mémoire de vecteur 1 comprend une mémoire 10, un transformateur de forme double-normale 11, une mémoire-file 12, une unité de comparateur 13 et une mémoire-pile 14 (stack memory) Le transformateur de forme double-normale 11 est relié à la mémoire-file 12 et la mémoirefile 12 est relié à l'unité de comparateur 13 et à la mémoire 10 L'unité de comparateur 13 est reliée à la-mémoire 10 et à la mémoire-pile 14, la mémoi- re 10 et la mémoire-pile 14 étant également reliée entre elles L'unité de commande 6 est reliée à l'unité de compa- rateur 13 et à la mémoire 10, le générateur d'arrangement 4 est relié au transformateur de forme double-normale 11, le convertisseur vecteur-trame 12 est relié à l'unité de comparateur 13 et, le cas échéant, le générateur de fenêtre 3 est relié à l'unité de comparateur 13. On va décrire ci-après le mode de fonctionnement de la mémoire de vecteurs 1 représenté sur la figure 3. Lorsqu'il n'est pas nécessaire de prendre une nou- velle figure dans la mémoire de vecteur 61 et par conséquent dans la mémoire 10, l'unité de commande 6 commande l'unité de comparateur 13 de manière que le contenu de la mémoire parvienne par l'unité de comparateur 13 directement au con- vertisseur vecteur-trame 2. Si une nouvelle figure déjà positionnée de façon correspondante par le générateur d'arrangement 4 doit être arrangée, cette nouvelle figure parvient par le transforma- teur de forme double-normale 11 dans la mémoire-file 12 Le transformateur de forme double-normale 11 assure une décompo- sition telle des vecteurs que le caractère univoque du déve- loppement trame (décomposition en rangées 4-Ofl"Oflnf) puisse être assuré La lecture dans la mémoire 10 a lieu dans ce cas également de façon usuelle jusqu'à ce que l'unité de compara- teur 13 reconnaît que la figure mémorisée dans la mémoire- S 12 jouit d'une priorité, du point de vue de l'apparition sur l'image, car le générateur d'arrangement 4 a arrangé cette figure sur la surface qui vient d'être indiquée Dans ce cas, l'unité de comparateur 13 admet, sous l'effet du signal d'au- torisation de l'unité de commande 6, la description vectoriel- le de la nouvelle figure sur le convertisseur vecteuis-trame 2 et en même temps elle envoie dans la mémoire-pile 14 la figure qui se trouvait dans l'image précédente et introduit dans la mémoire 10, à l'emplacement correspondant à sa place dans la nouvelle image, la nouvelle figure provenant de la mémoire-file 12. Ensuite, l'ancienne figure mémorisée pour le moment dans la mémoire-pile 14 est affichée et inscrite par échange permanente de figures dans la mémoire 10 cela de telle manière que la figure chaque fois transcrite soit mémorisée dans la mémoire-pile 14 De cette manière, le processus d'insertion se poursuit pendant une cadence d'image complète. Si l'effacement et le transfert de positiond'une figure quelconque se trouvant dans la mémoire 10 était néces- saire, cela a lieu de la façon suivante: la partie constitu- tive à effacer, lue dans la mémoire 10 ne parvient, en raison de l'interdiction de l'unité de commande 6, pas à travers l'unité de comparateur 13 et la partie constitutive suivante qui n'est plus à effacer s'inscrit par la mémoire-pile 14 à l'endroit libérée de la mémoire 10. La figure 4 représente un exemple de réalisation avantageux du générateur d'arrangement 4 utilisé dans le dis- positif conforme à l'invention Cette variante d'exécution du générateur 44 comprend une mémoire d'environnement 15, une mémoire de figures 16, une unité de chevauchement ou re- couvrement 27, une unité de commande interne 18, un transfor- mateur de position 19, un générateur de valeur scalaire 20, une unité de commande de mémoire-pile 21,une mémoire-pile de valeursscalaires 22 et un multiplexeur 23 La mémoire d'envi- ronnement 15 est reliée à l'unité de chevauchement 17, l'unité de chevauchement 17 est reliée au générateur de valeur scalaire 20 et au transformateur de position 19, le transfor- mateur de position 19 est relié au multiplexeur 23, à la mé- moire de figures 16 et à la mémoire-pile de valeurs scalaires 22, la mémoire-pile de valeurs scalaires 22 est reliée au générateur de valeur scalaire 20 et à l'unité de commande de mémoire-pile 21. L'unité de commande de mémoire-pile 21 est reliée au multiplexeur 23 et à l'unité de commande interne 18, laquelle est reliée au multiplexeur 23 et à la mémoire de figures 16 L'unité de commande 6 est reliée à l'unité de com- mande interne 18, la source extérieure 8 est reliée à l'unité de commande interne 18 et à la mémoire de figures 16, la mé- moire de vecteuis 1 est reliée au transformateur de position 19 et le générateur de fenêtre 3 est relié à la mémoire d'en- vironnement 15. On va décrire ci-après le fonctionnement du mode de réalisation ci-dessus du générateur d'arrangement 4. La description vectorielle de la partie constitu- tive à arranger parvient de la source extérieure 8 dans la mémoire de figures 16 De la source extérieure 8 parviennent également à l'unité de commande interne 18 les paramètres qui déterminent le nombre des essais d'arrangement à effectuer et les exigences technologiques intervenant dans l'arragne- ment (direction des fibres, texture, dessins, anisotropie, etc) Le générateur de fenêtre 3 commandé par la fonction de l'analyseur d'occupation 5 fait simultanément parvenir dans la mémoire d'environnement 1 E la description vectorielle des parties constitutives disposées jusqu' à présent dans la mémoire de vecteurs 1 La description vectorielle de la partie constitutive à arranger parvient de la mémoire de figures 16 au transformateur de position 19 et de là de façon transfor- mante (rotation ou translation) dans l'unité de chevauchement 17 Il en est de même pour le contenu de la mémoire d'environne- ment 15 L'lunité'de commande interne 18 génère par le multiplexeur 23 et le transformateur de position 19 des nouveaux arrange- ments jusqu'à ce que l'unité de chevauchement 17 reconnaît, en combinaison avec les parties constitutives arrangées jusqu'à présent dans cette unité et devant être arrangées de façon actuelle, un arrangement exempt de chevauchement ou que le nombre d'essais mémorisé dans l'unité de commande interne 18 est épuisé. Si un arrangement sans recouvrement a été réalisé dans l'unité de chevauchement 17, l'unité de commande interne 18 autorise pour l'unité de commande de mémoire-pile 21 P'ins- cription des paramètres actuels du transformateur de position 18 ainsi que de la valeur actuelle du générateur de valeur sclaire dans la mémoire-pile de valeurs scalaire 20 Le géné- rateur de valeur scalaire délivre, selon l'algorythme non dé- taillé ici, une valeur de mesure scalaire pour la position de la partie constitutive déjà arrangée et à arranger. L'unité de commande de mémoire-pile 21 tient en évi- dence la valeur scalaire maximale atteinte Cette opération se répète avec différentes quantités partielles environnantes et lorsque la fréquence prédéterminée pour les essais est atteinte, l'unité de commande de mémoire-pile 21 sélectionne, sur instruc- tion de l'unité de commande interne 18, l'une des valeurs scalaire mémorisées dans la mémoire-pile de valeurs scalaires 22, avec contrôle de valeur limite, et laisse ensuite arriver les paramètres de translation et de rotation correspondant à travers le multiplexeur 23 dans le transformateur de position 19 La description vectorielle de la partie constitutive à arranger, mémorisée dans la mémoire de figures 16, parvient par le transfor- mateur de position 19 avec transformation appropriée dans la mémoire de vecteurs 1 Donc,le générateur d' arrangement 4 sélection- ne essentiellement les paramètres de la meilleure adaptation de la figure à arranger, désigne la meilleure adaptation avec une valeur de mesure scalaire et introduit la figure dans cette position virtuelle dans la mémoire de vecteurs 1. Le schéma synoptique d'une variante de réalisation avantageuse de l'analyseur d'occupation S utilisé dans le dis- positif suivant l'invention est illustré par le figure 5. L'analyseur d'occupation 5 a pour fonction de dé- terminer, sur la surface d'arrangement, les vides o des nou- velles figures peuvent encore être arrangées potentiellement. L'arrangement concret est ensuite effectué, de la manière décrite précédemment, par le générateur d'arrangement 4, dans le champ déterminé par le générateur de fenêtre 3. La variante d'exécution représentée de l'analyseur d'occupation 5 comprend une unité de séparation 24, une unité de discriminateur 25, un compteur de coordonnées 26, un regis- tre de coordonnées 27, un compteur de vides 28, une mémoire de paramètres 29, une logique d'inscription 30, un sommateur de vides 31, un registre limiteur de minimum 32, une unité d'équivalence de limiteur minimum, une logique de magnitude 34, un registre d'intervalles 35, une unité d'équivalence d'inter- valle 36, un registre d'adresses 37, un générateur de centre de gravité 38, un générateur d'espace 39, un registre de lon- 1 S gueurs 40, une unité d'équivalence de longueur 41, un registre d'ordresde grandeur 42, une unité d'équivalence d'ordre de grandeur 43 et une mémoire-pile d'ordresde grandeur 44. L'unité de séparation 24 est reliée au sommateur de vides 31, au compteur de coordonnées 26 et à l'unité de discriminateur 25, l'unité de discriminateur 25 est reliée au sommateur de vides 31, au registre de coordonnées 27, au compteur de vides 28, à l'unité d'équivalence d'intervalle 36, à la logique d'inscription 30, à l'unité d'équivalence de longueur 41 et à la logique de magnitude 44 Le compteur de coordonnées 26 est relié au registre de coordonnées 27, le registre de coordonnées 27 est relié à l'unité d'équivalence d'intervalle 36 et à la logique d'inscription 30, le compteur de vides 28 est relié au générateur de centre de gravité 38, au générateur d'espace 39, à la logique d'inscription 30, à l'unité d'équivalence de longueur 41 et à l'unité d'équiva- lence de limiteur minimum 33 L'unité d'équivalence de limiteur minimum 33 est reliée à la logique de magnitude 34 et au re- gistre de limiteur minimum 32 et la logique de magnitude 34 est reliée à la logique d'inscription 30. L'unité d'équivalence de longueur 41 est reliée à la logique d'inscription 30 et au registre de longueurs 40 et le registre de longueur 40 est relié avec la logique d'ins- cription 30 ainsi qu'avec le registre d'adresse 37 à la mémoire de paramètres 29 L'unité d'équivalence d'intervalle 36 est reliée au registre d'adresse 537 et au registre d'intervalle 35. Le registre d'intervalles 35 est relié à la mémoire de paramètres 29 et l'unité d'équivalence d'ordre de grandeur 43 est reliée à la mémoire de paramètres 29, à la mémoire-pile d'ordrebde grandeur 44 et au registre d'ordresde grandeur 42, le registre- pile d'ordresde grandeur 44 étant en outre relié à la mémoire de paramètres 29. Le convertisseur vecteur-trame 2 est relié à l'uni- té de séparation 24, l'unité de commande 6 au sommateur de vides 33, au registre d'ordresde grandeur 42 et au registre de limi- teur minimum 32. On va décrire ci-après plus en détail le mode de fonctionnement de l'analyseur d'occupation 5 illustré par le *figure 5. Au cours du travail, l'analyseur d'occupation 5 détermine essentiellement par rangées la longueur (déterminée en points de trame) des parties non encore occupées par des figures, et les coordonnées de ces parties L'analyseur d'occu- pation 5 forme simultanément à partir de ces rangées vides également une surface cohérente avec détermination simultanée des données de centre de gravité et de superficie de cette sur- face Lors de la détermination de la surface, l'analyseur d'occupation 5 examine si les vides se trouvant dans les rangées successives sont suffisamment longs ou se recouvrent les uns les autres sur une longueur suffisante et si l'ordre de grandeur de la surface ainsi obtenue atteint la valeur dans laquelle tombent les figures devant être arrangées. En effet, si les conditions ci-dessus ne devaient pas être remplies, l'analyseur d'occupation 5 constaterait un vide séparé, ou n'indiquerait pas pour le générateur de fonc- tion 3 l'espace en question comme vide en cas de non atteinte de l'ordre de grandeur prescrit. Au cours du fonctionnement de l'analyseur d'occupa- tion 5, les figures jusqu'à présent arrangées parviennent comme point d'image avec les signaux de synchronisation, de changement d'image et de couleur nécessaires pour l'apparition, du conver- tisseur vecteurs-trame à travers l'unité de séparation 24 dans l'unité de discriminateur 25 L'unité de séparation 24 efface à chaque changement d'image le sommateur de vides 31 ainsi que par rangéesle compteur de coordonnées 26 L'unité de discriminateur 25 reconnaît à partir du contenu de signal (par exemple 1 0) des différents points d'image si le point qui a été laissé appa- raître actuellement représente une figure ou un vide Dans le cas d'un vide, l'unité de discriminateur 25 décale le sommateur de vides 31 ainsi que le compteur de vides 28. Les signaux de l'unité de séparation 24 décale le compteur de coordonnées 26. Lorsque l'unité de discriminateur 25 reconnaît la fin d'une, figure quelconque dans la rangée venant d'être examinée, elle introduit le contenu du compteur de coordonnées 26 dans le registre de coordonnées 27, c'est-à-dire qu'elle conduit le point de départ du vide dans cette rangée L'unité de commande 6 amène le registre limiteur de minimum 32 à la valeur qui dé- termine la longueur du vide, qui correspond encore de façon minimale à l'arrangement des figures à arranger La logique de magnitude 34 n'autorise la prise en compte du vide dans la rangée venant d'être examinée, en tant que vide que si la longueur du vide se trouvant dans la rangée donnée dépasse le contenu du registre de limiteur minimum 32. L'unité de discriminateur 25 efface la logique de magnitude 34 à chaque passage figure-vide Les coordonnées de début et fin du vide actuel de même que la valeur générée jusqu'à présent concernant le centre de gravité et la superfi- cie, sont lues par rangée à partir de la mémoire de paramètres 29 Les coordonnées' de départ et fin parviennent dans le re- gistre d'intervalles 35 et les autres'données dans l'unité d'équi- valence d'ordre de grandeur 43. L'unité de commande 6 remplit également le registre d'ordresde grandeur 42; les données de tous les vides parvien- nent par suite de la commande de l'unité d'équivalence d'ordre de grandeur 43, dans la mémoire-pile d'ordresde grandeur 44 pour atteindre la valeur d'ordre de grandeur mémorisée dans le registre d'ordreade grandeur 42, donc conviennent à l'arrangement vrais- semblable des figures à introduire Pour dévoiler ou dé&'elop- per les vides-cohérents, il faut évidemment comparer la position relative des vides se trouvant par rangées et des vides se trouvant chaque fois dans la rangée précédente Cette comparaison est effectuée dans l'unité d'équivalence d'inter- valle 36, avec la comparaison des données du registre d'inter- valleb 35 qui mémorise les données de la rangée précédente, et celle du registre de coordonnées 27 qui mémorise les données de la rangée actuelle S'il existe entre les vides se trouvant dans les deux rangées un chevauchement d'une certaine gran- deur, le dispositif considère ces vides comme étant cohérents du point de vue de la formation de vide S'il n'existe cepen- dant pas de chevauchement préalable de grandeur déterminée, l'unité d'équivalence d'intervalle 36 augmente le contenu du registre d'adresseb 37 et cela détermine dans la mémoire de paramètres 29 une nouvelle adresse en vue de l'arrangement du nouveau vide Dans la détermination du vide, l'unité d'équi- valence de longueur 41 a également un rôle puisqu'elle compare la longueur du vide se trouvant dans la rangée actuel- le avec la longueur du vide se trouvant dans la rangée précé- dente Le compteur de vide 28 commande le générateur decentre de gravité 38 et également le générateur d'espace 39; en effet, si l'analyse devait démontrer que les vides dévoilés dans la rangée examinée constituent le prolongement des vides reconnus dans la rangée précédente et constituent donc un vide cohérent, la valeur de centre de gravité et de superficie calculée pré- cédemment doit être actualisée Si, par contre, le vide dévoi- lé dans la rangée examinée devait représenter le début d'un nouveau vide, le vide précédent s'achève et la génération d'un nouveau vide commence. Le sommateur de vides 31 inscrit son contenu actuel à chaque changement dtimage dans l'unité de commande 6 laquelle est donc toujours informée au sujet du rapport d'occu- pation de la surface destinée pour l'arrangement. Un avantage du procédé et dispositif suivant la pré- sente invention réside dans le fait que la modélisation de l'arrangement de figures bi-et tridimensionnelles peut être effectuée par utilisation du procédé conforme à l'invention de façon rapide et en tenant compte de plusieurs conditions. REVENDICATIONS 1 Procédé d'arrangement optimal de figures au moins bidimensionnelles, caractérisé par le fait qu'on mémo- rise de façon vectorielle tes figures à arranger, qu'on dé- L iiïua I vi'es ïd figur-es dujà arranges et quon essaye d'insérer les figures à arranger dans lesdits vides, les éventuels chevauchements ou recouvrementsdes nouveaux arran- gements obtenus au cours de l'insertion étant analysés en décomposition rangée-colonnes (décomposition en trame) et l'optimum de l'arrangement étant déterminé suivant un point de vue quelconque. 2 Procédé suivant la revendication 1, caractérisé par le fait que parmi les figures mémorisées de façon vec- torielle, on examine le chevauchement ou recouvrement éven- tuel de la figure à arranger uniquement en relation avec les figures qui sont situées aux alentours du vide sélectionné pour l'arrangement de la nouvelle figure à arranger. 3 Dispositif électronique pour l'arrangement opti- mal de figures au moins bidimensionnelles, en vue de la mise en oeuvre du procédé suivant la revendication 1 ou 2, caracté- risé par le fait qu'il comprend une mémoire de vecteurs( 1),un. convertisseur vecteurs-trame( 2), un générateur de fenêtre ( 3), un générateur d'arrangement ( 4), un analyseur d'occupation ( 5), une unité de commande ( 6), un appareil d'indication ( 7), une source extérieure ( 8), ainsi que des organes d'intervention ( 9), la mémoire de vecteur S ( 1) étant reliée à l'unité de commande ( 6), un générateur d'arrangement ( 4) et un convertis- seur vecteur-trame ( 2), la source extérieure ( 8) étant réliée au générateur d'arrangement ( 4) et à l'unité de commande ( 6), l'unité de commande ( 6) étant reliée au générateur d'arran- gement ( 4), au générateur de fenêtre ( 3), à l'analyseur d'oc- cupation ( 5) et aux organes d'intervention ( 9), l'analyseur d'occupation ( 5) étant relié au convertisseur vecteurstrame ( 2), le convertisseur vecteuirtrame ( 2) étant relié à l'appa- reil d'indication ( 7), le générateur de fenêtre ( 3) étant relié au générateur d'arrangement ( 4) et à la mémoire de vec- teus ( 1) ou au convertisseur vecteu V,-trame ( 2). 4 Dispositif suivant la revendication 3, caracté- risé par le fait que la mémoire de vecteur 551 comprend unemé- moire, un transformateur de forme double-normale ( 11), une mémoire-file ( 12),une unité de comparateur ( 13) ainsi qu'une mémoire-pile ( 14), le transformateur de forme double-normale ( 11) étant relié à la mémoirefile( 12), la mémoire-file( 12) étant reliée à l'unité de comparateur ( 13) et à la mémoire ( 10), l'unité de comparateur ( 13) étant reliée à la mémoire ( 10) et la mémoire-pile ( 14) étant reliée à la mémoire ( 10). 5 Dispositif suivant la revendication 3 ou 4, caractérisé par le fait que le générateur d'arrangement ( 4) comprend une unité de commande interne ( 18), une mémoire de figures( 16),un multiplexeur ( 23), un transformateur de posi- tion ( 19), une unité de chevauchement ou de recouvrement ( 17), un générateur de valeur scalaire ( 20), une mémoire d'environ- nement ( 15), une mémoire-pile de valeursscalaires( 22) et une unité de commande de mémoire-pile ( 21), l'unité de commande interne ( 18) étant reliée à la mémoire de figures ( 16), à l'unité de commande de mémoirepile ( 21) et au multiplexeur ( 23), le multiplexeur ( 23) étant relié à l'unité de commande de mémoire-pile( 21) et au transformateur de position( 19), le transformateur de position ( 19) étant relié à la mémoire de figure 6 ( 16), à l'unité de chevauchement ( 17) et à la mémoire- pile de valeurs scalaires ( 22), l'unité de chevauchement ( 17) étant reliée au générateur de valeur scalaire ( 20) et à la mémoire d'environnement ( 15), le générateur de valeur scalaire ( 20) étant relié à la mémoire-pile de valeurs scalaires( 22) et la mémoire-pile de valeursscalaires( 22) étant reliée à l'unité de commande de mémoire-pile ( 21). 6 Dispositif suivant l'une quelconque des revendi- cations 3 à S, caractérisé par le fait que l'analyseur d'occu- pation (S) comprend une unité de séparation ( 24), une unité de discriminateur ( 25), un sommateur de vides ( 31), un compteur de coordonnées ( 26), un registre de coordonnées ( 27),un comp- teur de vides ( 28), un générateur de centre de gravité ( 38), un générateur d'espace ( 39)> une logique d'inscription ( 30), une mémoire de paramètres( 29), une unité d'équivalence de limiteur minimum ( 33),un registre de limiteur minimum ( 32), une logique de magnitude ( 34), un registre de longueur 5 s( 40), une unité d'équivalence de longueur ( 41), un registre d'adres- ses( 37), un registre d'intervalle ( 35), une unité d'équivalence d'intervalle ( 36), un registre d'ordresde grandeur ( 42), une unité d'équivalence d'ordre de grandeur( 43) et une mémoire- pile d'ordresde grandeur ( 44), l'unité de séparation ( 24) étant reliée au sommateur de vides ( 31), au registre de coor- données ( 26) et à l'unité de discriminateur ( 25), l'unité de discriminateur ( 25) étant relié au sommateur de vides ( 31), au registre de coordonnées ( 27), au compteur de vides( 28), à la logique de magnitude ( 34), à l'unité d'équivalence de lon- gueur ( 41), à la logique d'inscription ( 30) et à l'unité d'équivalence d'intervalle ( 36), le registre de coordonnées ( 27) étant relié à la logique d'inscription ( 30) et à l'uni- té d'équivalence d'intervalle ( 36), le compteur de vides ( 28) étant relié au générateur de centre de gravité ( 38) et au générateur de vides ( 39) ainsi qu'à la logique d'inscription ( 30),à l'unité d'équivalence de longueur ( 41)et à l'unité d'équi- valence de limiteur minimum, l'unité d'équivalence de limi- teur minimum ( 33) étant reliée à la logique de magnitude ( 34) et au registre de limiteur minimum ( 32), la logique de magni- tude ( 34) étant reliée à la logique d'inscription ( 30),1 'uni- té d'équivalence de longueur ( 41) étant reliée à la logique d'inscription ( 30) et au registre de longueurs( 40), le regis- tre de longueurs ( 40) étant relié à la mémoire de paramètres ( 29), l'unité d'équivalence d'ordre de grandeur ( 43) étant reliée au registre d'ordresde grandeur ( 42), la mémoire-pile d'ordresde grandeur ( 44) étant reliée à la mémoire de para- mètres( 29) et au registre d'intervalles( 35), le registre d'intervalles( 35) étant relié à la mémoire de paramètres( 29) et à l'unité d'équivalence d'intervalle ( 36), au registre d'adresse B( 37) et à la logique d'inscription ( 30), le regis- tre d'adresses( 37) étant relié à la mémoire de paramètre 5 ( 29), la mémoire de paramètre ( 29) étant reliée à la mémoire-pile d'ordresde grandeur ( 44), la logique d'inscription 00) étant reliée à la mémoire de paramètres ( 29)et le compteur de coordonnées ( 26) étant relié au registre de coordonnées ( 27). 7 Dispositif indicateur, caractérisé par le fait qu'il comprend une mémoire de vecteurs ( 1), un convertisseur vecteurs-trame ( 2) et un appareil indicateur à trame ( 7), la mémoire de vecteurs ( 1) étant reliée à un convertisseur vec- teurs-trame ( 2) et le convertisseur vecteurs-trame ( 2) étant relié à l'appareil indicateur ( 7).