FR 2027371 A1 19700925 FR 6945410 A 19691230 69 45410 i 2027371 La présente invention concerne un calculateur de mise en position. Le découpage de modèles ou calibres de forme prédéterminée, en partant d'une matière première continue, plate, de largeur fixe, 5 est une tâche qui se présente fréquemment dans certaines industries. Par exemple, dans l'industrie du vêtement, des pièces de patron de vêtement sont découpées à partir d'une étoffe plate ou tubulaire ; dans l'industrie automobile, des revêtements de siège et des garnitures de tête sont découpés sur une étoffe d'ameuble-10 ment ; dans l'industrie des récipients, des ébauches en carton sont découpées à partir d'une matière première ondulée ou de carton ondulé ; dans 1'industrie du travail des métaux, des pièces sont découpées à partir d'une tôle métallique à l'aide de calibres principaux. Dans ces cas ainsi que dans d'autres cas, une atten-15 tion considérable est donnée à la disposition des pièces nécessaires dans un arrangement d'ensemble calculé pour réduire au minimum la perte de matière entre les calibres mis en place. Le plan de découpage qui en résulte est parfois désigné sous le nom de "marqueur" ou "pochoir". 20 Les lignes générales de ce problème peuvent être exposées de la manière suivante : pour uri jeu prédéterminé de modèles à découper à partir d'une matière première ayant une largeur fixe, trouver la disposition de ces modèles qui réduira la longueur totale de matière première nécessaire pour produire les modèles don-25 nés. Pratiquement cette solution est rarement atteinte, pour ne pas dire jamais, en raison du nombre considérable de combinaisons de pièces qu'il est possible d'envisager pour vin jeu donné de modèles. Une disposition optimale acceptable pourrait être définie comme étant constituée par un arrangement de pièces nécessitant 30 moins de matière en moyenne qu'un pourcentage élevé, par exemple quatre-vingt-dix pour cent des arrangements obtenus manuellement. Le pourcentage peut être fixé par le fabricant pour compenser les économies attendues sur le prix de la matière première, comparées aux dépenses que nécessitent des essais répétés. 35 En conséquence l'un des buts de la présente invention est de fournir un système permettant de réduire automatiquement la longueur de la matière première nécessaire pour cette solution optimale. 69 45410 2 2027371 Un autre but de l'invention est de fournir vm système pour tracer un placement préféré d'entités géométriques. Un autre but enfin de l'invention est de fournir un système qui produise automatiquement des pièces de matière en partant 5 d'une matière première plate de manière à réduire la grandeur de la perte de matière et de la rendre inférieure à celle qui serait obtenue si l'opération était exécutée par des opérateurs humains expérimentés. Le système décrit dans ce qui va suivre, destiné à rendre op-10 timale l'utilisation de la matière première, comprend un moyen pour présenter une représentation, exprimée par des chiffres, d'une succession de fornes géométriques, un ensemble de traitement des données numériques pour régler les données ainsi présentées de manière à simuler un déplacement physique de la pièce au-15 tour de la surface d'une matière sur laquelle les pièces doivent être placées et un moyen de sortie pour produire les modèles,par exemple une fraise de découpage ou tin dispositif de traçage pour tracer le placement résultant destiné â servir de référence dans' le futur. L'ensemble de traitement des données numériques fonc-20 tionne sur les données numériques qui arrivent, conformément à une série de règles prescrites pour placer les pièces à des endroits qui d1une manière générale produisent une perte de matière inférieure à celle qui serait produitê si les pièces étaient placées par un opérateur humain expérimenté. Grâce à un ajustement continu 25 des données numériques des pièces de manière qu'il corresponde à un déplacement physique de la pièce autour d'une limite de marqueur qui est le résultat de placements antérieurs de pièces, chaque pièce nouvelle peut être mise en position à un endroit tel que se trouve réduite la longueur de matière supplémentaire nécessaire. 30 L'ajustement des données correspondant à un déplacement de la pièce par rapport à la limite est analogue à un glissement de la pièce par rapport à la limite de marqueur de telle manière qu'à aucun moment, la pièce ne recouvre la limite de marqueur déjà établie (ou ne soit en interférence avec elle). Du fait que les dë-35 placements sont sans recouvrement, chaque déplacement nouveau de pièce a besoin seulement d'être mis à l'épreuve afin que soit vérifié si oui ou non, le placement résultant augmenterait la longueur de la limite de marquage afin que soit déterminé si oui ou non la position nouvelle est supérieure à un emplacement antérieur. 69 45410 3 2027371 D'autres caractéristiques et avantages ressortiront de la description qui va suivre, faite en regard des dessins annexés et donnant à titre explicatif mais nullement limitatif plusieurs formes de réalisation conformes à l'invention. 5 Sur ces dessins, """" la figure 1 montre la relation entre les éléments actifs de 1'invention ; la figure 2 montre une situation typique pouvant se présenter dans le cas d'une pièce ayant un segment limite concave ; 10 la figure 3a illustre une pièce typique ; la figure 3b est Un tableau correspondant de données pour la pièce représentée sur la figure 3a ; la figure 4a montre la relation entre la limite initiale dégénérée et la matière non coupée ; 15 la figure 4b est un tableau correspondant de données pour la limite dégénérée ; la figure 5 est une succession de blocs diagrammes représentant le développement du système de placement ; la figure 6 montre la position d'une pièce typique à l'empla-20 cernent standard de démarrage ; la figure 7 montre un marqueur typique ayant trois pièces placées antérieurement et une pièce à l'endroit standard de départ et prête à être placée dans le marqueur ; la figure 8a montre la relation existant dans le cas où le 25 prochain segment de pièce, dans le sens inverse du sens des aiguilles d'une montre, a une pente plus grande que celle du prochain segment de limite dans le sens inverse du sens des aiguilles d'une montre ; la figure 8b montre la relation qui existe dans le cas où le 30 prochain segment de pièce, dans le sens inverse du sens des aiguilles d'une montre a une pente plus petite que celle du prochain segment de limite dans le sens des aiguilles d'une montre ; la figure 9 montre une succession typique de mouvements pour déplacer une pièce autour d'une limite de marqueur ; 35 la figure 10 montre la situation qui permet qu'un double mou vement soit exécuté ; la figure 11 montre une situation d'interférence qui peut se produire dans les cas où il existe des sommets concaves ; 69 45410 4 2027371 la figure 12 montre une situation présentant plusieurs interférences ; la figure 13 illustre la manière dont chaque sommet de la pièce mobile est essayé, cet essai ayant pour but de déterminer si 5 oui ou non le sommet essayé croisera un segment de la limite fixe ; la figure 14 illustre la manière dont chaque sommet de la limite fixe est essayé, cet essai ayant pour but de déterminer si oui ou non le sommet essayé croisera vin segment de la pièce mobile; la figure 15 illustre le calcul du déplacement partiel utili-10 sant le calcul imaginaire ; la figure 16 illustre vin premier essai pour éliminer certains sommets déterminés pour être non interférents ; la figure 17 illustre un second essai éliminant des sommets supplémentaires déterminés pour être non interférents. 15 On a présenté ci-après une solution au problème concernant l'arrangement automatique d'une succession prédéterminée de modèles formés arbitrairement d'une manière organisée et contrôlée, de manière à diminuer la grandeur de l'espace nécessaire de telle sorte que cet espace soit plus petit que celui qui est utilisé 20 pour l'exécution de la même tâche dans un temps raisonnable par des opérateurs humains compétents, travaillant à la main. Comme c'est le cas dans de nombreuses techniques automatiques, la supériorité du procédé dépend de la complexité de la décision rendant le procédé compliqué. Dans la description de la présente invention 25 on a employé deux règles fondamentales de base pour simplifier grandement vin problème extrêmement complexe. Tout d'abord, on suppose que l'ordre dans lequel les pièces doivent être choisies pour leur placement a déjà été établi par un procédé indépendant." En second lieu l'orientation de chaque pièce par rapport aux limites 30 de la matière a été aussi déterminée antérieurement sous la réserve toutefois que les pièces elles-mêmes peuvent être retournées bout pour bout autour de 1'axe longitudinal de la pièce pour présenter une vue retournée, inversées côté pour côté autour de l'axe transversal de la pièce pour présenter une vue inversée, ou bien 35 pour présenter une vue combinée retournée/inversée, cela dépendant de ce qui est exigé par les commandes extérieures. En tant que fait préliminaire, on admet que la matière elle-même a une largeur supérieure à la dimension transversale d'une pièce quelconque. La longueur de la matière est normalement égale 69 45410 5 2027371 à plusieurs fois la dimension de largeur et suivant la présente invention, on suppose qu'il y a une pièce d'étoffe ayant une dimension étendue dans le sens de la longueur, le problême général se trouvant ainsi réduit au problème particulier qui consiste 5 dans la mise en position, automatiquement d'une succession prédéterminée de pièces prêorientées à l'intérieur d'un espace ayant une largeur W de manière à faire une économie sur la longueur totale L de matière nécessaire. La figure 1 illustre la relation existant dans un.groupe d'ë-10 -léments actifs qui seraient employés typiquement pour la mise à exécution du procédé automatique de marquage. Au début la forme et les dimensions des pièces individuelles sont décidées par un opérateur humain et les modèles sont préparés comme il est indiqué sur le dessin (figure 1). Les pièces individuelles sont en-15 suite chiffrées (les limites déterminant chaque pièce sont transformées en tableaux d'information de position par coordonnées numériques) par un procédé 4 de chiffrage qui peut être un procédé manuel ou un procédé automatique et l'information résultante est fournie directement à un ensemble de calcul 2. Selon une variante, 20 les données transformées en chiffres peuvent être tout d'abord traitées extérieurement (45) pour l'identification des sommets conformément aux prescriptions, pour l'identification des sommets (les emplacements ayant un degré de courbure élevé) et facultativement pour l'identification d'autres points de contrôle ayant 25 de l'intérêt (voir brevet des Etats-Unis d'Amérique N° 3.391.392 et demande de brevet des Etats Unis d'Amérique N° 716.918, du 28 Mars 1968, déposée par Harold W. DOYLE) qui peuvent avoir de l'importance dans des opérations apparentées telles que la reconnaissance des coins et la régularisation du modèle. L'ensemble 2 30 de calcul est en communication avec un ensemble 3 de contrôle pour assembler et convertir les représentations chiffrées des pièces conformément aux règles fournies extérieurement qui déterminent à la fois l'orientation des pièces individuelles et la succession suivant laquelle ces pièces doivent être présentées en vue de leur 35 placement. Les règles de choix qui commandent cette phase du procédé peuvent être des conclusions logiques d'un opérateur humain ou bien, selon une variante, les critères de sélection et d'orientation peuvent être fournis par une autre décision automatique de routine dont les détails n'ont pas été représentés parce qu'ils 69 45410 6 2027371 ne font pas partie de la présente invention. Une seconde fonction qui est remplie par l'ensemble de calcul 2 consiste dans l'essai de chaque sommet des pièces individuelles au point de vue de la concavité ou de la convexité de la limite 5 de pièce. Cette information est essentielle pour la mise à exécution du procédé de placement suivant la présente invention décrit ci-après. Bien que cette fonction soit remplie normalement sur des données de pièce individuelle après que ces données ont été présentées pour le placement (voir fig. 5), la mécanique du procédé 10 sera décrite à cet endroit (de manière à faciliter une description ininterrompue du procédé de placement) étant donné qu'il s'agit en réalité d'un calcul demandant une décision séparée, qui est indépendant du procédé de placement. Ainsi qu'on l'expliquera plus loin, il est en outre nécessaire de déterminer la concavité ou la 15 convexité du contour de la limite aux sommets représentant la limite de développement du marqueur et la description qui va suivre est également applicable à cette détermination. Le contour de la limite à chaque sommet est déterminé par un examen point par point des données numériques représentant une li-20 mite ou un périmètre. La convention employée pour les fins de la présente description consiste à assigner un "0" binaire aux tours à gauche et un "1" binaire aux tours à droite lorsque la limite déterminant la pièce est circonscrite dans le sens inverse du sens des aiguilles d'une montre. Par conséquent, si un sommet particu-25 lier est convexe (comme ce serait le cas pour chacun des points d'angle d'un polygone régulier, par exemple) le sommet est marqué avec un "0" binaire tandis que si le sommet est concave (comme ce serait le cas pour à peu près la moitié des points déterminant la forme d'un croissant) le sommet est marqué avec un "1" binaire. 30 Pour des raisons qui seront indiquées plus loin, la convention adoptée ici pour le marquage des sommets individuels comme sommet concave ou comme sommet convexe est telle qu'elle nécessite que les points d'un groupe entier de points soient marqués comme concaves quand ces points, considérés dans leur ensemble décrivent un 35 contour limite concave et cela bien que des fluctuations locales de la limite puissent apparaître comme étant convexes. Ainsi, sur la figure 2, la pièce 10 est représentée comme ayant des sommets en 211, 212, 213, 214, 215, 216, 217 et 218. S'il n'y avait pas la partie en saillie hachurée en saillie 220, le sommet 213 serait 69 45410 7 2027371 marque avec un zéro binaire, indiquant une courbure convexe puis- qu'en avançant de 212 à 213 puis à 214, on fait un tour vers la gauche. Toutefois pour des raisons qui apparaîtront plus loin la définition du terme concave doit être étendue suivant la présente 5 invention pour s'appliquer à tout point déterminant la limite pour lequel un autre point déterminant la limite se trouve à droite du segment de ligne droite réunissant le point considéré au point suivant immédiatement sur la limite. On voit que le sommet 217 se trouve à droite du prolongement du segment de droite réunissant 10 le point 213 au point 214 ; en conséquence le point 21J doit être déclaré concave. En considérant les choses d'une autre manière, le segment de droite 221 reliant les sommets 213 et 214 et le segment de droite 223 reliant les sommets 214 et 217 forment me limite incurvée et le sommet 214 est marqué en-conséquence. 15 Quand une pièce particulière a été choisie pour sa mise en place (par exemple le modèle représenté sur la figure 3a) les données représentant cette pièce peuvent être rassemblées suivant un groupement analogue à celui qui est représenté sur la figure 3b. Les entrées X et Y du groupement représentent les coordonnées 20 cartésiennes de chaque sommet de la pièce tandis que la troisième colonne (intitulée Z) est réservée pour l'indication des contours (suivant qu'ils sont convexes ou concaves, conformément aux conventions décrites ci-dessus). Pour la pièce représentée sur la figure 3a (qui est constituée seulement par des segments de ligne 25 droite) le tableau (fig. 3b) comporte 9 entrées seulement mais il est bien entendu qu'un tel tableau peut comprendre un nombre de données numériques correspondant à des points aussi nombreux qu'il peut être nécessaire pour représenter fidèlement une limite fortement incurvée. 30 Lorsque les tableaux ont été formés, 1'emplacement de chaque pièce peut être déterminé conformément au procédé suivant la présente invention. Cette opération est accomplie à l'aide du système 5 de traitement des données qui communique par l'intermédiaire des lignes 31 à 36 avec l'ensemble 3 d'information de commande et avec 35 l'ensemble 2 de calcul des données et il est bien entendu qu'un outillage réel des trois ensembles fonctionnels pourrait être typiquement incorporé à une machine unique. Au début, la largeur W de la matière est transmise au système 5 de traitement des données pour la mise en place des pièces, en 40 compagnie des données représentant'le bord de gauche. Ainsi que OFUG'NAl7 69 45410 8 2027371 le montre la figure 4a, le bord de gauche de la matière 11 est typiquement une ligne droite, les données de définition étant constituées par trois points-seulement qui décrivent une limite dégénérée s'étendant du point 101 au point 102 puis en retour du point 5 102 au point 101. Une fois que l'information concernant le bord a été reçue, les marques de contour peuvent être calculées et l'information peut être disposée sous là forme d'un tableau ainsi que le montre la figure 4b. A ce moment, un tableau de données représentant la première pièce à placer est traité et la routine du 10 placement est ainsi amorcée. La figure 5 est un diagramme de développement qui montre la succession pas à pas des opérations du processus de placement. Le tableau associé de données de chaque pièce présenté pour le placement est tout d'abord ajusté(opération 507) de telle sorte que 15 les axes de coordonnées auxquels se rapportent les données concernant la pièce soient transportés dans le système de coordonnées de la matière 11 d'une manière telle que la pièce soit mise effectivement en position à un emplacement de départ standard, en contact avec la limite du marqueur. Ainsi que le montre la figure 6, l'em-20 placement de départ standard pour la première pièce est déterminé par analyse du tableau de données représentant la pièce pour la valeur Y la plus grande. Le sommet repère représenté par cette entrée particulière du tableau est alors amené en coïncidence avec le point 101 de bordure de marque inférieur de la matière 11, 25 avec référence, naturellement, à l'information présentée dans l'opération 505 spécifiant quelle est la vue de la pièce (normale, retournée, renversée ou retournée/renversée) qui doit être utilisée. Le même ajustement est exécuté pour chaque point du tableau de sorte qu'en fait, la pièce entière est déplacée vers l'emplacement 3 0 standard de départ. En tout ceci, c'est-à-dire dans l'emplacement initial à l'endroit du départ ainsi que dans les déplacements pas à pas qui suivent, pour amener la pièce jusqu'à une position finale, il est essentiel que l'orientation prédéterminée (opération 504) de la pièce soit maintenue suivant l'exposé antérieur afin que les 35 axes de coordonnées X et Y de la pièce demeurent parallèles aux P P axes de coordonnées X et Y de la matière 11 de sorte que soit mm entraînée seulement une translation (et non une rotation) de la pièce. 69 45410 9 2027371 Ainsi que le montre la figure 7, le déplacement réel d'une pièce 16 vers un emplacement préféré à l'intérieur d'une largeur disponible est obtenu par ajustement du tableau de données, ce qui correspond à une translation physique de la pièce 16 soit le long d'une 5 pièce soit le long de segments limites""(c'est-à-dire des segments de ligne droite reliant des sommets voisins). Afin d'illustrer le cas général, la figure 7 montre trois pièces (13, 14 et 15) qui ont été mises en position antérieurement par le procédé suivant la présente invention, et une quatrième pièce 16 se trouvant à l'empla-10 cernent de départ. Il est bien entendu toutefois que le procédé est également applicable à "la mise en position de la première pièce 12 (ainsi que le montre la figure 6) contre la bordure d'extrémité de gauche de la matière 11 (c'est-à-dire la limite disponible dégénérée) . Une fois que les pièces 13, 14 et 15 ont été mises en posi-15 tion, la nouvelle bordure disponible se compose des segments réunissant les points 101-106, 106-107, 107-108, 108-109, 109-110, 110-111, 111-112, 112-113, 113-114, 114-115, 115-116, 116-117, 117-118, 118-102 et 102-101. Le sommet 106 peut être en contact avec le bord inférieur 20, et le sommet 115 peut être en contact 20 avec le bord supérieur 20 de la matière. Cela dépend du coin disponible que la première pièce doit occuper suivant la liste et il n'y a pas de différence évidente au point de vue des économies de matière entre les marges dont on ne se sert pas. Toutefois, pour faciliter la présente explication, on suppose que les pièces sont 25 placées pour occuper la zone inférieure tout d'abord de sorte que le sommet 106 est en contact avec le bord inférieur 20. Le premier mouvement de la pièce 16 à partir de son emplacement de départ est obtenu par modification de son tableau de données d'une manière correspondant à une translation physique dans la di-30 rection X qui amène le sommet de la pièce ayant la valeur Y la plus grande (201) en coïncidence avec le sommet (106) ayant la valeur X la plus grande du bord inférieur disponible, c'est-à-dire du bord inférieur 20 de la matière 11. Le déplacement de la pièce vers un certain emplacement préféré à l'intérieur des bords 35 de la matière est ensuite exécuté conformément aux enseignements de la présente invention, décrits ci-dessous,par un procédé de déplacement pas à pas qui implique une modification de l'information (tableau de données) concernant les coordonnées du sommet de pièce mobile, d'une manière qui est analogue à une nouvelle 69 45410 10 2027371 localisation physique de la pièce qui serait accomplie si la pièce subissait un glissement le long de ses propres segments, en contact avec un sommet fixe de la limite de marque ou, selon une variante, subissait . un glissement, l'un de ses sommets étant 5 en contact le long d'un segment fixe 3e la limite disponible. Dans l'explication qui va suivre de l'opération de translation, le trajet suivi dans le déplacement d'une pièce autour de la limite disponible fixe a été établi comme étant un trajet qui se réfère aux segments voisins de "gauche" de la pièce et de la limite, le 10 résultat étant un déplacement dans le sens inverse du sens des aiguilles d'une montre de la pièce mobile et de la limite fixe l'une par rapport à l'autre. Toutefois, le choix (étape 509 de la figure 5) devl'opération à exécuter c'est-à-dire la question de savoir si l'on fait glisser un sommet de la pièce mobile le long 15 d'un segment d'une limite fixe ou si l'on fait exécuter à la pièce mobile une translation le long d'un de ses propres segments en contact avec un sommet limite fixe implique la prise d'une décision, la détermination finale dépendant du signe algébrique du sinus de . l'angle formé par les deux segments en cause. Sur la figure 8a, on 20 peut voir qu'il est possible de faire exécuter une translation au sommet 201 de la pièce 16 par rapport aù segment de droite 50 de la limite fixe tandis que la pièce 16 ne peut pas exécuter une translation le long de son propre segment 51 en contact avec le sommet fixe 106 sans recouvrir la limite fixe. Toutefois, c'est 25 l'opposé qui se produit dans la situation représentée sur la figure 8b. Dans ce cas, le vecteur 51 réunissant les sommets 202 et 201 de la pièce est représenté comme ayant une pente plus petite que celle du vecteur 50 qui relie les sommets 106 et 107 de la limite fixe. Dans ce cas, une translation sans recouvrement ne 30 peut être faite que le long du segment 51 de la pièce. La figure 9 illustre la succession des mouvements qui se produiraient lors du déplacement d'une pièce typique 60 autour de la limite fixe 61 disponible, En (a) la pièce est placée à l'emplacement standard de départ (fig. 5, étape 507). En (b) la pièce a 35 été déplacée par translation jusqu'à une position dans laquelle son point le plus élevé coïncide avec le sommet le plus à droite de la limite fixe 61 qui est en contact avec le bord inférieur 62 de la matière. En (c), la pièce 60 a été déplacée par translation depuis la position représentée en (b), le long du segment S^ de 69 45410 ii 2027371 la limite fixe 61, jusqu'au sommet 64 ; dans le déplacement de (c) à (d) , la translation est effectuée le long du côté V]L ; dans le déplacement de (d) à (e) , la translation est effectuée le long du segment limite S2 ; dans le déplacement de (e) à (f), la transla-5 tion est effectuée le long du segment V2 de la pièce, et ainsi de suite, la pièce se déplaçant vers la gauche (sens inverse du sens des aiguilles d'une montre) autour du périmètre de la limite fixe d'une manière ne donnant pas de recouvrement (de S1 à S2 puis à Sg, etc.) et la limite fixe s'avançant en fait vers la gauche (sens 10 inverse du sens des aiguilles d'une montre) autour de la pièce d'une manière ne donnant pas de recouvrement (par exemple de à V2 puis à Vg, etc.) ainsi qu'on l'a expliqué précédemment. Ainsi qu'on l'a indiqué ci-dessus, un recouvrement non désiré de la pièce avec la limite disponible déjà établie est évité par un glissement 15 de translation par rapport à tin segment de pièce ou à un segment de limite fixe, cela dépendant des pentes relatives (c'estrà-dire de la somme algébrique des sinus des angles formés par les segments en cause). Sur la figure 9, on voit que toutes les fois que la pente du segment limite vers la gauche (prochain segment dans le 20 sens inverse du sens des aiguilles d'une montre) des sommets qui sont en contact est inférieure à la pente du segment de pièce vers la gauche (dans le sens inverse du sens des aiguilles d'une montre) des sommets qui sont en contact, le déplacement de la pièce s'effectue le long du segment limite, tandis que si la pente du 25 segment limite est plus grande, le déplacement s'effectue le long du segment de pièce. Par exemple quand la pièce est dans la position (b) la pente du prochain segment limite S^ dans le sens inverse du sens des aiguilles d'une montre est inférieure à la pente du prochain segment de pièce rencontré par un déplacement le 30 long du-périmètre de la pièce. En conséquence, la pièce 60 est déplacée avec son sommet 67 en contact avec le segment jusqu'à ce que les sommets 64 et 67 soient amenés en coïncidence comme il est indiqué en (c). En (c), la pente S2 du prochain segment limite est plus grande que la pente de sorte que le déplacement 35 de la pièce vers l'emplacement représenté en (d) s'effectue le long du segment de la pièce. Afin de faciliter un choix en ce qui concerne le segment de déplacement approprié, les segments ayant de 1'intérêt peuvent être considérés comme des vecteurs, le but qu'on se propose étant 69 45410 12 2027371 de former leur produit vectoriel, le sinus de l'angle et par conséquent le mode de déplacement étant déterminés par le signe du produit vectoriel. Par exemple, si la pente d'un vecteur S représentant un segment limite est plus petite que la pente d'un vec-5 teur V représentant un segment de pièclï, le produit vectoriel (S x V) est positif. D'une manière analogue, le produit vectoriel (S x V) est négatif dans les|cas où la pente de V est inférieure à celle de S. Etant donné que par définition le produit vectoriel (S x V) est un vecteur ayant sa direction déterminée par une rota-10 tion à droite amenant S sur V, le produit vectoriel est nul dans les cas où les vecteurs S et V sont parallèles et dans un tel cas, un double mouvement peut être exécuté. Cette situation est illustrée sur la figure 10 sur laquelle le segment vecteur de pièce V est parallèle au segment vecteur limite S de manière à permettre 15 une translation de la pièce 80 de (y) à (z). Le procédé de déplacement pas à pas (étapes b à h) sur la figure 9, décrit ci-dessus ne comprend pas la situation dans laquelle il existe des sommets concaves. Dans le procédé réel d'application de l'invention, il est naturellement nécessaire d'examiner (figure 20 5, étape 510) les marques de contour antérieurement déterminées des sommets de contact prévus de telle manière que des conflits en puissance puissent être évalués avant qu'il soit procédé au déplacement de la pièce. Par conséquent, ainsi qu'on peut le voir sur la figure 11, bien que le produit vectoriel (Q x P) du vecteur 25 limite Q par le vecteur de pièce P soit positif, la pièce 70 ne peut pas être déplacée le long de Q depuis le sommet limite 71 jusqu'au sommet limite 72 sans qu'il y ait vin conflit, c'est-à-dire une interférence, avant que le sommet 72 soit atteint, ainsi qu'il est indiqué par la position 73 en traits interrompus. En 30 conséquence, ce qui est désiré est vin mouvement partiel dont le mécanisme est décrit plus loin afin que la présente description de la succession normale des déplacements de la pièce puisse être poursuivie. On suppose par conséquent qu'un examen des marques de contour a été fait par le diagramme de développement de la figure 35 5 (étape 510) et que le contour est convexe ou qu'il n'y a pas d'interférence, si le contour est concave. Si cet état existe, un mouvement de déplacement peut être fait suivant toute la longueur d'un segment comme pour l'étape 513A. A chaque position nouvelle de la pièce, l'information à jour concernant l'emplacement est 69 45410 13 2027371 examinée afin que soit déterminé si la pièce est à l'intérieur des bords (62 et 63 de la figure 9) de la matière (étapes 514 et 515) et une nouvelle longueur d'essai de la limite, comprenant la pièce dans la position nouvelle, est calculée (étape 516). Si la pièce 5 se trouve à l'intérieur des bords 62 "St 63, et si la nouvelle longueur d'essai disponible (dimension X totale) est inférieure à la longueur d'essai antérieure la plus courte qui ait été calculée (étape 517) la nouvelle longueur et les données d'emplacement sont mises en mémoire pour qu'on s'y réfère ultérieurement (étape 512). 10 Si la pièce est encore à l'extérieur de la bordure inférieure ou si la pièce est à l'intérieur des bordures mais que la nouvelle longueur d'essai soit plus longue qu'une longueur d'essai calculée antérieurement, un autre mouvement est amorcé par le procédé de l'étape 519. Si la nouvelle position de la pièce dépasse le 15 bord supérieur 63, ce qui est détecté par l'étape 515, la pièce est placée (étape 519) à l'endroit qui produit la longueur disponible empirique la plus petite, c'est-à-dire à l'endroit qui a été antérieurement déterminé par l'étape 518. Maintenant, le placement de la pièce mobile à la position correspondant à la valeur 20 la plus petite de la longueur calculée disponible ne peut pas augmenter en fait la longueur totale disponible en raison de la possibilité que des pièces placées antérieurement puissent avoir laissé un espace non marqué suffisant pour loger la nouvelle pièce sans augmentation dans la longueur de marqueur accumulée à ce mo-25 ment dans le procédé. En conséquence, un essai supplémentaire (étape 520) est fait, qui compare la longueur d'essai du marqueur à la longueur totale du marqueur. Si la longueur d'essai dépasse la longueur totale, la longueur d'essai devient alors la nouvelle longueur totale (étape 521) ; autrement, la longueur disponible 30 totale précédente est conservée pour me comparaison qui suivra le prochain placement de pièce. Un contrôle est ensuite exécuté (étape 522) pour déterminer si oui ou non la dernière pièce a été placée et s'il en est ainsi, l'application du procédé est terminée (opération 525) . Autrement, la limite disponible est augmentée de 35 manière qu'elle comprenne la nouvelle pièce (étape 523) et les marques de contour appropriées de la nouvelle limite disponible sont établies (étape 524) de la manière précédemment décrite. Un retour est alors exécuté vers l'étape 504 où la prochaine pièce est choisie et la série d'opérations décrites ci-dessus est répë-40 tée jusqu'à ce que toutes les pièces aient été placées. 69 45410 14 2027371 Ainsi qu'on l'a indiqué précédemment, on a réservé l'explication du mécanisme du mouvement partiel (étapes,511 à 513 B) afin que soit achevé sans interruption l'exposé de la succession fondamentale d'opération de placement. On va donc expliquer mainte-5 nant les détails d'un mouvement partîei. La figure 12 montre une situation dans laquelle la pièce mobile 300 et la limite fixe 301 ont l'une et l'autre des sommets concaves de sorte que le déplacement proposé de la pièce le long du segment 302 aurait pour résultat une interférence. On supposera par exemple que la pièce soit 10 être déplacée le long de 302 de façon que si le point 303 soit amené en contact avec le point fixe 313, le point 307 recouvre en partie (interférence) la zone entourée par la limite fixe 301 et que le point 309 recouvre en partie la zone de la pièce 300. Cette situation de recouvrement en puissance est naturellement si-15 gnalêe par la présence du sommet 304 sur la limite de pièce et du sommet 312 sur la limite fixe (ces deux sommets seraient désignés comme sommets concaves conformément aux conventions précédemment adoptées). On détermine s'il y aura un recouvrement réel en cal- • culant si le déplacement proposé de chaque sommet de la pièce 20 coupe (croisement) les segments de droite reliant les sommets de la limite fixe et si un déplacement, dirigé dans le sens opposé, des sommets de la limite fixe coupe (croisement) les segments reliant les sommets de la limite -de pièce. Ainsi qu'on peut le voir sur la figure 13, le déplacement vectoriel de chaque sommet 25 303, 304, 305, 307, 310, 311 le long du segment 302 a pour effet que le sommet 307 coupe le segment de droite qui relie les sommets 306 et 308 de la limite fixe. Par suite, en ce qui concerne cette partie de l'essai, le déplacement le plus grand qui puisse être fait le long du segment 302 est celui qui produit tout juste 30 l'entrée en contact du sommet 307 avec le segment 315 au point 316. Sur la figure 14, l'essai d'interférence est exécuté pour déterminer si oui ou non la concavité sur la limite fixe (points 306, 308 et 312) entraîne pour résultat un recouvrement partiel quand la pièce mobile 300 se déplace. L'essai est exécuté comme précédem-35 ment, à cette différence près que la pièce mobile 300 est considérée comme fixe et que la limite fixe 301 est considérée comme étant déplacée dans la direction opposée, le but poursuivi étant de déterminer les points où les sommets de la limite fixe 301 croiseraient (couperaient) les segments de droite formant la limite 69 45410 15 2027371 de la pièce mobile 300. Ainsi qu'on peut le voir sur la figure 14, le sommet 309 de la limite fixe croise le segment de droite 317 (qui relie les sommets 307 et 310 de pièce mobile) au point 318. Le déplacement maximum pour cette partie de l'essai est par con-5 séquent déterminé par la longueur du sëgment reliant les points 309 et 318. Le déplacement maximum admissible peut par conséquent être déterminé par la plus petite des distances entre 309 et 318 et entre les points 316 et 307. Dans l'exemple ci-dessus, représenté sur la figure 12, il y a 10 deux points seulement, désignés par les repères 307 et 309, qui produisent une intersection. Toutefois, dans certaines situations il peut y avoir plusieurs points produisant une intersection, compris dans chaque partie. Quand cela se produit, on détermine le déplacement maximum admissible de la même manière que ci-dessus, 15 en se limitant au plus petit des déplacements, c'est-à-dire au déplacement partiel amenant la limite de la pièce mobile en contact avec la limite fixe, sans qu'il y ait recouvrement. Sur la figure 15, la grandeur réelle du déplacement partiel résultant du contact d'un sommet avec un segment peut être dëter-20 minée à l'aide d'équations vectorielles de la manière suivante. Si le déplacement d'un sommet donné A jusqu'au point B est représenté par le vecteur B - A et si le segment de droite réunissant deux sommets adjacents C et D sur la limite fixe est représenté par le vecteur D - C, un point P se trouvant sur un prolongement 25 du vecteur B - Â dans une direction ou dans l'autre peut être représenté par P = Â + (B - Â)Y (1) dans laquelle P est la représentation vectorielle du point P par rapport à une origine. D'une manière analogue, en ce qui concerne 30 un point Q se trouvant, sur le vecteur qui réunit deux sommets, on a Q = C + (D - C) dans laquelle Q est ,1a représentation vectorielle du point Q par rapport à une origine. Les équations vectorielles ci-dessus repré-35 sentent la position sur les vecteurs B - Â et D - C d'un point P et d'un point Q, respectivement. Par conséquent si, dans l'équation (1) la valeur de t' est zéro, le point P coïncide avec le point A sur la figure 15. D'une manière analogue, si "X' égale un, P coïncide avec le point B. Pour O K. ( 1 , le point P se trouve 69 45410 16 2027371 entre les points A et B et pour r> 1 , le point P se trouve au delà du point B, ce qui correspondrait à la situation dans laquelle il n'y a aucune interférence. Les mêmes conclusions sont valables pour le point Q avec référence du vecteur D - C. Par 5 conséquent pour er> , le point Q se trouverait au delà du point D et par suite, il n'y aurait aucune interférence et cela même bien qu'un déplacement complet du sommet (de A à B) soit effectué. Pour déterminer s'il existe une interférence, on peut résoudre les équations (1) et (2) simultanément pour déterminer le Â + (B - Â) = C + (D - C) CT (3) et par conséquent (B - Â)T - (D - C)CT = C - A (4) 15 Etant donné que les équations (1) à (4) sont des équations vectorielles, les projections sur l'axe des X et l'axe des Y doivent satisfaire aussi à ces équations, de sorte que (Bx - V* - 20 (By - V* - (dy - cy,cr - cy - ay (6) Il en résulte deux équations (5) et (6) qui peuvent être résolues simultanément pour la détermination des inconnues G~~ et ^ . Afin de faciliter l'essai des déplacements proposés pour déterminer quels sont les recouvrements qui peuvent se produire, 25 différents essais, décrits ci-dessous, peuvent être faits pour l'élimination de différents points et de différents segments de droite en tant qu'éléments possibles d'interférence (étape 511 sur la figure 5). Du fait que chaque sommet sur la pièce mobile, constituant un élément d'interférence en puissance doit être 30 essayé en combinaison avec chaque segment interfèrent en puissance, de la limite fixe et vice versa, l'élimination d'éléments d'interférence en puissance devient importante en réduisant le temps imparti au calcul. Une fois qu'ont été éliminés les sommets pour lesquels il n'est pas possible qu'il se produise une interférence 35 dans le mouvement considéré, l'essai d'interférence peut être exécuté et c et peuvent être calculés pour chacune des combinaisons possibles (étape 512). S'il se trouve que 69 45410 17 2027371 interférence) un déplacement complet peut être exécuté (étape 513A). Si toutefois et se trouvent tous deux entre "0" et "1" pour certaines des combinaisons, un mouvement partiel est indiqué (étape 513B). La grandeur réelle de ce mouvement partiel est éga-5 le, ainsi que précédemment indiqué, aiT produit du déplacement de l'étape complète désirée par la valeur la plus petite de "f' dans les combinaisons dans lesquelles On a représenté sur la figure 16 une manière commode d'élimi-10 ner les sommets .qui ne sont pas des sommets interférants en puissance. Dans l'exemple représenté, on suppose que le vecteur de déplacement se trouve suivant le segment 413 de la pièce mobile 401 (le vecteur de déplacement étant déterminé par les sommets 403 et 404). L'essai comprend les étapes de construction d'un 15 rectangle fictif 409 (représenté en traits mixtes) qui enveloppe exactement les limites de la pièce mobile 401. Ensuite la limite fixe 400 est entourée d'une manière analogue par le rectangle 410 représenté en traits interrompus. La zone de recouvrement 411 qui est commune aux deux rectangles 409 et 410 est agrandie conformé-20 ment au vecteur de déplacement complet 413 pour produire la zone 412 qui comprend à l'intérieur de ses limites l'un quelconque des sommets (par exemple les sommets 415 à 417 et 419) déterminant la limite fixe 400 qui pourraient peut-être produire une interférence avec des segments de la pièce mobile 401. La grandeur de 25 l'agrandissement est déterminée par la zone du rectangle 412 qui serait nécessaire pour circonscrire la zone entourée par élargissement du rectangle de recouvrement 411 conformément au vecteur de déplacement 413. Le même procédé naturellement pourrait être appliqué pour éliminer les sommets n'interférant pas, sur la 30 pièce mobile par rapport aux segments de droite fixe, la seule différence résidant en ce que la zone commune s'étend vers l'arrière (opposée à la direction du vecteur de déplacement 413) dans la pièce mobile. Sur la figure 17, on a représenté une autre élimination de 35 points n'interférant pas. Si ion déplacement doit être fait le long du vecteur 113, les points sur la. limite de pièce, qui se trouvent à l'extérieur du couloir 450 déterminé par le déplacement latéral maximum de points de la limite 400 par rapport au vecteur 413 ne sont pas des points d'interférence en puissance. D'une 69 45410 18 2027371 manière analogue, les points sur la limite disponible qui se trouvent en dehors du couloir 450 ne sont pas des pçints d'interférence en puissance. Par suite, des sommets tels que 406 sur la pièce mobile et 417 sur la limite fixe n'ont pas besoin d'être 5 considérés dans la détermination de la"valeur limite de On suppose par exemple que chacun des essais ci-dessus ont été exécutés (étape 511) et que les sommets non interférants aient été éliminés. On suppose en outre que les sommets restants d'interférence en puissance et des segments aient été combinés pour 10 déterminer le *( le plus petit correspondant à un mouvement partiel le long du vecteur de déplacement désiré amenant tout juste la pièce mobile en contact avec la limite fixe. Dans cette situation, le tableau de données définissant la pièce est ajusté pour correspondre au mouvement partiel "f (étape 513B). Il est bien en-15 tendu que le prochain vecteur de déplacement à considérer sera hors de la succession parce que la pièce mobile a été amenée en contact avec la limite fixe à un certain point nouveau. Par suite le prochain déplacement de la pièce est relatif au nouveau point de contact. Il est par conséquent nécessaire de repérer les ta-20 bleaux de données pour prévoir le fait que le prochain déplacement de la pièce consiste en une translation du nouveau sommet de contact le long du segment nouvellement contacté d'une manière analogue à celle qui a été précédemment décrite en liaison avec l'étape 513A. Il s'ensuit que les prochains sommets ayant de l'intë-25 rêt (pour l'étape 509) sont ceux se trouvant à la gauche des sommets du nouveau contact et ainsi de suite, l'ajustement approprié étant indiqué dans l'étape 513B. L'enseignement de base de l'invention peut être employé dans toutes sortes d'applications variées nécessitant une analyse à 30 plusieurs dimensions et des placements géométriques. Il va de soi que la présente invention a été décrite ci-dessus à titre d'exemple préférentiel explicatif mais nullement limitatif et que l'on pourra introduire toute équivalence dans ses éléments constitutifs sans sortir de son cadre défini par les reven-35 dications annexées. 69 45410 19 2027371 LEGENDE DES DESSINS Figure Repère 1 A Procédé extérieur alternatif par exemple recon naissance des coins, classement des dimensions du modèle, etc. — B Moyen de chiffrage. C Planche de mise en place. D Entrée dans le cas où l'opérateur est un être humain. E Ensemble de commande pour la succession et l'orientation des pièces. F Système de traitement des données pour le placement et l'évaluation des pièces. G Ensemble de calcul pour le traitement de la sélection de la succession des pièces et l'exécution des analyses des sommets et des contours. H Information concernant les pièces. I Information concernant la largeur. J Sortie. K Moyen de -tracé pour le dessin du placement des pièces. L Dispositif facultatif de coupe pour produire automatiquement les pièces conformément à la disposition rendue optimale. M Alimentation en matière. yo D Données 4Ï> D Données 10 1 Limite fixe D Déplacements combinés dans les cas où S et V sont parallèles. . 69 45410 20 2027371 FIGURE 5 Figure Repères 5 501 Départ. 502 503 504 505 506 507 508 509 510 Réglage de la largeur. Régler la lirai te initiale, les marques de contour et la largeur du marqueur. Déterminer la prochaine pièce à placer et son orientation. Présenter les données concernant la prochaine pièce et modifier le tableau de données pour l'orientation désirée. Calculer les marques du contour des pièces. Ajuster les données de manière à placer effectivement la pièce en contact avec la limite à un emplacement de départ standard. Manipuler les données pour effectuer une translation vers le sommet dont la coordonnée à X est le plus grand qui est en contact avec lé bord inférieur de la matière. Choisir un vecteur de déplacement d'essai. Essayer les marques de contour des sommets de contact s'il n'y a pas de sommet concave si un ou plusieurs sommets sont concaves. ^ 511 Eliminer les sommets et les segments qui ne sont pas des sommets et des segments interférants en puissance. 512 Faire l'essai du déplacement d'essai pour l'interférence s'il n'y a pas d'interférence ajuster le tableau de données et les indices pour les faire correspondre au déplacement total vers le prochain sommet 513A s 'il y a interférence ajusternies données pour les faire correspondre au déplacement partiel vers le prochain sommet et ajuster les indices. 513B 2027371 69 45410 22 2027371 REVENDICATIONS 1. Système pour la mise en position de plusieurs modèles dans une limite disponible, caractérisé en ce qu'il comprend : un moyen de chiffrage pour transformer les sommets de chaque modèle en un 5 tableau de coordonnées cartésiennes ; un moyen pour déterminer le contour de chaque sommet ; un moyen de traitement des données pour modifier chaque tableau de données pour simuler une translation sans interférence de la pièce en contact tangentiel avec la limite disponible ; un moyen pour calculer et mettre en mémoire la dimen-10 sion de longueur disponible après chaque mouvement de telle manière que l'emplacement de longueur minimale puisse être déterminé; un moyen pour l'enregistrement de l'emplacement final de chaque pièce pour former une nouvelle limite disponible. 2. Système de marquage caractérisé en ce qu'il comprend : un 15 moyen de chiffrage pour déterminer les coordonnées de points de données représentant le périmètre d'une pièce ; un moyen de mise en mémoire pour conserver les coordonnées des sommets d'une pièce et d'une limite de marqueur ; des moyens pour engendrer des représentations vectorielles de segments qui réunissent chaque som-20 met d'une pièce au prochain sommet voisin de la pièce ; des moyens pour engendrer des représentations vectorielles de segments qui relient chaque sommet de la limite disponible au prochain sommet voisin de la limite disponible ; des moyens pour déterminer le contour de chaque sommet j des moyens sensibles à l'information de 25 contour et aux représentations vectorielles, pour augmenter les données de coordonnées des sommets afin de simuler une succession de translations, sans recouvrement, de chaque pièce, autour de la limite disponible précédemment établie ; des moyens pour calculer la longueur disponible après chaque mouvement ; des moyens pour 30 mettre en mémoire la longueur calculée ; des moyens pour comparer chaque nouvelle longueur calculée avec des longueurs précédentes de pièce, de sorte que puisse être déterminé l'emplacement de pièce qui entraîne l'augmentation de longueur utilisée la plus petite. 35 3. Système pour la mise en position de modèles qui sont re présentés sous une forme chiffrée autour d'une zone à deux dimensions, caractérisé en ce qu'il comprend : une machine à calculer à chiffres pour transformer les données chiffrées représentant chaque pièce pour qu'elles correspondent à une translation physique 69 45410 23 2027371 sans recouvrement de la pièce autour d'une limite préétablie et en contact avec cette limite, déterminée par des pièces mises en position antérieurement ; des moyens détecteurs pour déterminer le bord de la zone ; des moyens pour déterminer les dimensions 5 nouvelles de la limite après chaque translation simulée de la pièce ; des moyens pour mettre sélectivement en mémoire'11 emplacement de chaque position nouvelle de la pièce, qui a pour résultat une dimension de limite plus petite que les emplacements précédents de la pièce, de sorte que la pièce puisse être ajustée 10 dans l'emplacement qui produit l'augmentation la plus petite dans la zone occupée. 4. Combinaison caractérisée en ce qu'elle comprend : des moyens pour chiffrer les limites d'un modèle ; des moyens pour mettre sous forme de tableau les données représentant chaque mo- 15 dèle pour former un rangement ; des moyens pour disposer les rangements représentant chaque pièce en une succession pour placement à l'intérieur d'une zone ; des moyens pour augmenter chaque rangement de données en succession pour qu'elles correspondent à une translation physique de chaque pièce vers des emplacements diffë-20 rents à l'intérieur de la zone qui n'est pas occupée par des pièces mises en position antérieurement ; des moyens pour délimiter les dimensions extérieures de la bordure formée par les données augmentées représentant les pièces mises en position antérieurement et les données représentant les différents emplacements de 25 la pièce présentement soumise à une translation, de sorte que peut être déterminé l'emplacement de la pièce qui produit l'augmentation la plus petite des dimensions du bord. 5. Combinaison décrite dans la revendication 4, caractérisée en ce que les moyens pour augmenter chaque rangement de données 30 comprennent une machine à calculer pour déterminer arithmétique-ment l'emplacement nouveau de chaque point de données qui correspond à une translation physique de la pièce en contact glissant avec une limite déjà établie, déterminée par des pièces mises en position antérieurement. 35 6. Arrangement pour disposer automatiquement des gabarits afin de réduire la quantité de matière utilisée dans un marquage, caractérisé en ce qu'il comprend : des moyens pour présenter en succession une représentation chiffrée de chaque gabarit ; des 69 45410 24 2027371 moyens pour manipuler les données représentant chaque pièce pour qu'elles correspondent à une mise en position physique de chaque pièce successivement, à l'intérieur des bords de la matière ; des moyens pour manipuler les données de chaque pièce pour qu'elles 5 correspondent à une mise en position de chaque pièce en contact tangentiel avec la limite formée par les pièces mises en position à 1'emplacement qui fournit l'augmentation la plus petite des dimensions non disponibles ; des moyens pour augmenter l'ancienne limite pour comprendre l'addition de chaque pièce à l'emplacement 10 qui produit l'augmentation la plus petite des dimensions utilisées. 7. Procédé pour la mise en place de modèles afin de réduire la perte de matière, caractérisé en ce qu'il comprend les étapes suivantes : chiffrer les limites de chaque pièce ; assembler les données représentant chaque pièce en vin groupe d'entrées, chaque 15 entrée du groupe représentant les coordonnées X-Y des sommets de pièce ; disposer le groupe de données en une succession ; mettre en mémoire la succession des groupes de données ; augmenter chaq• groupe de données pour produire une vue particulière et une orientation par rapport à l'axe de coordonnées de la matière ; calculer 20 les marques de contour à chaque sommet de pièce ; analyser le groupe de données représentant chaque pièce pour déterminer le sommet ayant la valeur Y la plus grande ; augmenter chaque groupe de données pour le faire correspondre avec la mise en position de chaque pièce pour que le sommet ayant la valeur Y la plus grande 25 coïncide avec la limite inférieure de la matière ; modifier chaque groupe de données pour le faire correspondre à la translation de chaque pièce pour amener le sommet de la pièce ayant la valeur la plus grande à être en coïncidence avec le sommet le plus éloigné de la limite formée par les pièces placées antérieu-30 rement, qui est tangent au bord inférieur de la matière ; opérer sur les groupes de données pour engendrer les équations vectorielles représentant les segments de droite qui relient entre eux les sommets de la pièce ; opérer sur les données représentant la limite formée par les pièces mises en place antérieurement pour 35 engendrer à partir de ces données les équations vectorielles représentant les segments de droite qui relient entre eux les sommets de la limite ; calculer les marques de contour à chaque sommet de la limite préétablie ; multiplier le vecteur de la pièce se trouvant à la gauche des sommets en contact par le vecteur de 69 45410 25 2027371 la limite se trouvant à la gauche des sommets en contact, de manière à fermer le produit vectoriel afin de déterminer un vecteur de déplacement le long duquel peut s'effectuer une translation sans recouvrement ; augmenter les données de la pièce pour les 5 faire correspondre à une série de déplacements qui peuvent être ou bien une translation complète, sans recouvrement, de la pièce en contact glissant avec la limite vers un nouveau sommet ou bien une translation partielle, sans recouvrement, de la pièce, en contact glissant avec la limite jusqu'à un point de contact avec 10 la limité, déterminé par l'information concernant le contour ; faire l'essai de la position nouvelle de la pièce après chaque déplacement pour déterminer si la pièce est oui ou non entre les bords de la matière ; comparer la longueur de la limite après chaque déplacement pour déterminer si le nouvel emplacement de la 15 pièce a pour résultat un marqueur dont la longueur est inférieure à celle fournie par les emplacements précédents de la pièce ; mettre en mémoire l'information d'emplacement de la pièce à l'endroit où la pièce se trouve à l'intérieur des limites de la matière et où le nouvel emplacement de la pièce a pour résultat 20 un marqueur plus court que celui fourni par les positions précédentes de la pièce, de sorte que le groupe de données représentant chaque pièce peut être augmenté pour placer la pièce à un emplacement qui fournira l'augmentation la plus petite de la longueur du marqueur. 25 8. Procédé pour disposer les pièces sur une-matière, carac térisé en ce qu'il comprend les étapes suivantes : chiffrer les périmètres de pièce ; transformer les données chiffrées représentant chaque pièce pour qu'elles correspondent à un emplacement physique de la pièce à 1'intérieur des bords de la matière ; 30 manipuler les données chiffrées pour simuler une mise en position de chaque pièce successivement à l'intérieur des bords de la matière vers un emplacement qui produit l'augmentation la plus petite dans la longueur utilisée. 9. Procédé décrit dans la revendication 8, caractérisé en ce 35 que la manipulation des données chiffrées pour simuler une mise en position de chaque pièce successivement à l'intérieur des bords de la matière comprend les étapes suivantes : former les représentations vectorielles des segments reliant chaque sommet de la,' limite de marqueur ; identifier le contour à chaque sommet 69 45410 26 2027371 de pièce et à chaque sommet de limite ; placer la pièce pour qu'elle soit en contact tangentiel sans recouvrement avec la limite de marqueur ; multiplier les vecteurs de contact entre eux pour former le produit vectoriel ; essayer le signe du produit 5 vectoriel pour déterminer le vecteur de déplacement ; calculer la grandeur du déplacement à effectuer suivant 11information concernant le contour ; augmenter les données pour sipiuler le déplacement de la pièce conformément à la grandeur et/, à la direction antérieurement établies i examiner la longueur du marqueur après 10 chaque mouvement pour déterminer si la longueur nouvelle est plus petite qu'une longueur précédente ; mettre en mémoire les données représentant l'emplacement de la pièce qui a pour résultat une longueur de marqueur plus courte que celles fournies par les positions précédentes de la pièce de telle sorte que 1'emplacement de 15 la pièce à l'intérieur du bord a pour résultat la longueur de la place utilisée la plus courte qui puisse être déterminée. 10. Procédé suivant la revendication 8, caractérisé en ce que la manipulation des données chiffrées pour simuler une mise en position de chaque pièce successivement à l'intérieur des bordures 20 de la matière comprend lus étape» suivante* . 4Hoâif.i«r leê données pour les faire correspondre, à 1 'amenée de chagtÀc pièce dànr contact tangentiel avec la limite de marqueur formée par les pièces antérieurement mises en place, choisir la grandeur et la direction de chaque déplacement correspondant à une translation sans recouvre-25 ment de la pièce en contact de glissement avec la limite de marqueur; augmenter les données pour les faire correspondre à un déplacement de pièce onforme à la grandeur et à la direction précédemment établies ; faire l'essai de la longueur du marqueur après chaque mouvement de la pièce pour déterminer l'emplacement 30 qui produit l'augmentation la plus petite dans les dimensions du marqueur ; augmenter les anciennes, données de la limite pour comprendre la.pièce mise en place à l'endroit qui produit l'augmentation la plus petite dans la dimension du imarqueur et choisir la pièce suivante pour son placement. 35 11. Procédé suivant la revendication 10, caractérisé en ce que la sélection de la grandeur et de la direction de chaque mouvement de déplacement comprend les étapes suivantes : former la 'représentation vectorielle des segments reliant chaque sommet de lia limite de marqueur ; identifier le contour à chaque sommet de • » l { BAD ORIGINAL. 69 45410 27 2027371 pièce et à chaque sommet de limite ; mettre en position-la pièce pour qu'elle soit dans un contact tangentiel sans recouvrement avec la limite du marqueur ; multiplier les vecteurs de contact entre eux pour former leur produit vectoriel ; faire l'essai du 5 signe du produit vectoriel pour déterminer le vecteur de déplacement ; calculer la grandeur du déplacement à faire suivant 1'information de contour. 12. Procédé de mise en place de modèles pour réduire la perte de matière, caractérisé en ce qu'il comprend les étapes suivantes: 10 calculer les marques de contour des sommets représentant chaque pièce ; calculer les marques de contour représentant la limite formée par les pièces antérieurement mises en position ; ajuster les données représentant chaque pièce pour qu'elles correspondent à la mise en position de chaque pièce à tour de rôle à un empla-15 cernent de départ, choisir un vecteur de déplacement d'essai pour chaque déplacement de chaque pièce ; faire l'essai des marques de contour des sommets de contact pour déterminer s'il existe un recouvrement en puissance ; faire l'essai des données définissant la limite et la pièce pour déterminer si vin déplacement total de 20 sommets de contact concaves produit un recouvrement réel ; calculer la grandeur des déplacements partiels maximaux sans recouvrement possibles ; ajuster les données représentant chaque pièce pour les faire correspondre à un déplacement total vers un nouveau sommet ou à un déplacement partiel vers un nouveau point de con-25 tact sans recouvrement ; faire l'essai de l'emplacement nouveau de chaque pièce après chaque déplacement pour déterminer si la pièce est à l'intérieur des bords de la matière ; calculer les dimensions de la limite après chaque déplacement ; ajuster les données de la pièce pour les faire correspondre à la mise en posi-30 tion de chaque pièce à l'emplacement qui a pour résultat l'augmentation la plus petite des dimensions de la limite. 13. Procédé suivant la revendication 12, caractérisé en ce que le calcul de la grandeur d'un déplacement partiel d'une pièce comprend les étapes suivantes : superposer le vecteur de dépla- 35 cernent d'essai à chaque sommet de la pièce à déplacer ; déterminer si les vecteurs de déplacement d'essai superposés produisent une interférence avec les segments reliant des sommets voisins de la limite formée par les pièces mises en position antérieurement ; superposer un vecteur de déplacement d'essai dirigé en sens opposé 69 45410 28 2027371 sur chaque sommet de la limite formée par les pièces mises en position antérieurement ; déterminer si les vecteurs de déplacement dirigés en sens opposé sont en interférence avec les segments reliant des sommets adjacents de la pièce ; calculer le point d'in-5 tersection de chaque vecteur de déplacement interférant avec un segment pour déterminer le déplacement maximum sans recouvrement possible. 14. Procédé suivant la revendication 13, caractérisé en ce qu'il consiste à faire l'essai de la pièce et de la limite pour 10 éliminer les sommets et les segments qui ne sont pas des sommets et des segments interférants en puissance. 15. Procédé suivant la revendication 14, caractérisé en ce que les qpérations d'essai de la pièce et de la limite pour éliminer les sommets et les segments qui ne sont pas des sommets et 15 des segments interférants en puissance comprennent les étapes suivantes : construire un premier rectangle circonscrit autour de la pièce ; construire un second rectangle circonscrit autour de la limite formée par les pièces mises en position antérieurement ; superposer le vecteur de déplacement d'essai et un vecteur 20 de déplacement d'essai opposé sur chaque angle de la zone rectangulaire qui est commune au premier et au second rectangle ; étaler la zone rectangulaire qui est commune au premier et au second rectangle pour qu'elle comprenne les vecteurs positifs de déplacement d'essai à chaque angle ; étaler la zone rectangu-25 laire qui est commune au premier et au second rectangle pour qu'elle comprenne les vecteurs de déplacement d'essai à chaque angle ; éliminer tous les sommets et tous les segments se trouvant à l'extérieur des zones rectangulaires étalées comme n'étant pas interférants en puissance.