Brevet FR2646258A1 — publié le 19901026

PROCEDE DE DETERMINATION DES INTERSECTIONS DE COURBES PARAMETRIQUES POLYNOMIALES, POUR LA CONCEPTION ASSISTEE PAR ORDINATEUR DESCRIPTION La présente invention concerne un procédé de détermination des intersections de courbes paramétriques pour leur utilisation en conception assistée par ordinateur. Elle s'applique à la conception assistée par ordinateur (CAO) et plus particulièrement au dessin assisté par ordinateur (DAO). Elle peut apporter une aide très précieuse à la conception, notamment pour les graphistes, les mécaniciens, les architectes, etc Les courbes dont on souhaite déterminer les points d'intersection ne sont pas obtenues directement, mais par interpolation par des segments de droite ayant des extrémités situées sur ces courbes. Pour chaque courbe, ces segments de droite successifs forment une polyligne. Le choix des paramètres de définition de ces polytignes est particulièrement important puisqu'il conditionne une bonne représentation de chaque courbe et que, pour déterminer les points d'intersection de deux courbes, on détermine Les points d'intersection de deux polylignes interpolant respectivement ces deux courbes. Parmi Les méthodes connues pouvant servir à L'élaboration des polylignes d'une courbe, la plus performante est la méthode dite de de Cas.teljau11 décrite notamment dans l'ouvrage "formes à piles par PauL de Faget de Casteljau - volume 2 de 11Mathématiques et CAO - Hermès 1985 (1). Cette méthode consiste à considérer que toute courbe paramétrique polynomiale de degré d peut etre exprimée sous forme de courbe de Bézier, de type polynomial. Les courbes de Bézier sont décrites notamment dans l'ouvrage "Courbes et surfaces" par P. Bézier-mathématiques et CAO - volume 4 - Hermès 1986 (2). On sait par les documents (1, 2) précités qu'une courbe paramétrique poLynomiale de degré d, décrite mathématiquement par la fonction vectorielLe U(t) = (x(t), y(t)), avec Oct Dans cette relation U désigne les points de Bézier, et les B i,d (t) sont les polynomes de Bernstein qui sont notamment décrits dans le document (2) cidessus, ainsi que dans les documents suivants : - "NumericaL control : Mathematics and applications" Wi ley and Sons Ltd. 1972 par P. Bezier (3). - M. Lane et F. Riesenfeld. "A Theoretical Development for the Computer Generation and Disptay of Piecevise Polynomial Surfaces". IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.2(1) 35-46, 1980 (4). - L. Ramshaw. Blossoming : A Connect-the-Dots Approach to Splines. Research Report * 19, Digital Equipment Systems Research Center, PaLo Alto, 1987 . Les points successifs u@, ü , ..., U sont d qualifiés de points de contrôle, tandis que Le polygone défini parles points U0, U1, ..., Ud, U0, pris dans cet ordre, est qualifié de poLygone de contrôle. Chaque point de contrôle U peut être Localisé par des coordonnées réelles (xi, yi), dans un repère de référence. Ces coordonnées réeLles sont enregistrées dans La mémoire de l'ordinateur. La méthode de "de Casteljau" mentionnée plus haut et décrite dans les documents (i) et (2) précités, permet plus précisément d'obtenir La polyligne d'interpolation d'une courbe de Bézier. Une polyligne est formée de N segments successifs, permettant de représenter cette courbe au plus près.La méthode de "de Casteljau" est une méthode qui permet d'interpoler une courbe de Bezier par une polyligne obtenue gracie à une subdivision de type récursif : selon une variante de cette méthode La courbe est d'abord interpolée par une polyligne à deux segments (profondeur d'interpolation k=1), puis par une polyligne à quatre segments (k=2), et ainsi de suite, pour satisfaire le critère de proximité1, suivant : chaque segment de la polyligne n'est pas plus éloigné de plus d'une unité de grille de la portion de courbe qu'il interpole. L'unité de grille est l'unité qui est choisie dans le repère de référence. Cette méthode, bien que donnant une bonne représentation d'une courbe de setier a cependant pour iconvénient d'utiliser un traitement récursif d'interpolation, de durée importante. Le nombre N de segments d'une polyligne est lié à la profondeur k k d'interpolation, par La relation N=2 Des auteurs et notamment G. Wang ont montré que la profondeur d'interpolation k satisfaisant le critère de proximité précédent, est donnée par La relation: k=[Log4d(d-1)D] 8 dans laquelle d désigne le degré de La courbe et D La diagonale du polygone de contrôle de la courbe ; cette diagonale sera décrite-plus loin en détail. Le calcul de La profondeur dtinterpolation k de la valeur de la diagonale D du polygone de contrôle est décrit dans le document : "Comparison of t-hree Curve Intersection ALgorithms'i. Computer-Aided Design, vol.18(1) : 58-63, 1986 par T. Sedergerg et S. Parry Subdivision Method for Finding the Intersection between two Sérier Curves or Surfaces". Zhejiang University Journal, 1984. Special Issue on computationaL geometry, par G. Wang (7) qui décrit plus précisément ces deux calculs. Ces calculs théoriques n'ont toutefois jamais été utilisés pour générer une polyligne comparable à celle obtenue par La méthode de "de Casteljau", mais dont La construction serait pLus rapide qu'avec cette méthode. Il en résulte que la détermination des intersections de courbes de Setier interpolées par des polylignes obtenues par la méthode de "de Casteljau", présente pour un ordinateur utilisé en CAO, des temps de calculs importants De plus, les procédés connus de détermination de points d'intersection de courbes interpoLées par La méthode de "de Casteljau, utilisent une méthode dite de recherche par bottes engLobantes. Cette méthode est décrite notamment dans te document (7) précité. Selon cette méthode, pour rechercher Les points d'intersection appartenant à deux courbes, on définit pour chaque polyLigne, une zone rectanguLaire dite "bofte englobante", dont les côtés sont paraLlèles aux axes du repère de référence et sont locaLisés à partir des coordonnées des points de contra Le du poLygone de contrôle de ta courbe correspondante. Si Les courbes ont des points d'intersection, ceux-ci sont situées dans une zone commune aux deux bottes englobantes correspondant respectivement aux deux courbes. On subdivise ensuite Les courbes en deux parties, gauche et droite et on recalcule les bottes englobantes des quatre parties obtenues. Ces nouvelles bottes englobantes peuvent être qualifiées de "sous-botes englobantes".On recherche alors à nouveau les zones communes aux sous-bottes englobantes correspondant respectivement aux deux courbes. Ainsi, par subdivisions successives, on parvient à déterminer deux segments, interpolant respectivement chaque courbe, qui se coupent en un point correspondant à l'un des points d'intersection des deux courbes. Cette méthode a pour principal inconvénient de nécessiter des calculs dont La durée est importante puisque Les bottes englobantes doivent être recalculées à chaque étape. L'invention a précisément pour buts de remédier à ces inconvénients, notamment en permettant d'obtenir rapidement, par un traitement itératif, les polylignes représentatives des courbes dont on recherche les points d'intersection, ces polylignes étant équivalentes aux polylignes obtenues par la méthode de "de Casteljau" par un traitement récursif ; ces buts sont atteints en partant de La formule de Wang définie pLus haut, donnant La profondeur d'interpoLation k en fonction du degré b et de La diagonaLe 9 du poLygone de contrôle de chaque courbe, et en effectuant un traitement itératif dit de "différences en avant" permettant d'obtenir rapidement Les coordonnées des extrémités des segments de chaque polyligne. L'invention permet également de rechercher Les intersections de deux courbes en utilisant la méthode des bottes englobantes, mais en appliquant cette méthode de façon plus rapide, à des parties monotones de chaque polyligne de chaque courbe. Enfin, l'invention permet pour chaque point d'intersection, de fournir un contexte d'intersection, c'est-à-dire : - un numéro d'ordre sur la polyligne de chaque segment comportant une intersection, - pour chaque segment ' comportant une intersection, une mesure de la distance séparant Le point d'intersection de l'extrémité origine de ce segment, - Les coordonnées du point d'intersection dans Le repère de référence, - une liste ordonnée des portions orientées de segments, ou brins, autour du point d'intersection. L'invention concerne un procédé pour déterminer Les intersections de courbes paramétriques polynomiaLes de Bézier, pour la conception assistée par ordinateur, chaque courbe de degré d étant décrite mathématiquement par La fonction vectorielle U(t)=(x(t), y(t)), avec O k N=2 , N et étant spécifiques pour chaque courbe, cette profondeur étant donnée par la relation k=[Log4d(d-1)D], en calculant la diagonale D du 8 polygone de contrôle à L'aide de l'ordinateur à partir des coordonnées des points de contrôle enregistrées en mémoire, les valeurs de N, k et D étant enregistrées en mémoire, puis à déterminer, en calculant par récurrence à l'aide de l'ordinateur, les coordonnées (xi+1,yi+1) des extrémités des segments de chaque polyligne, entre Les points de contrôle UD et Ud en évaluant a priori des différences en avant (#xi, #yi) qu'il faut ajouter respectivemenmt aux coordonnées (xi,yi) de l'extremité d'un segment, pour passer aux coordonnées (xi+1, yi+1) de l'extrémité d'un segment suivant sur La polyligne, de sorte que : i+1 i i i+1 i i 2 2 avec #xi+1=#xi+#xi avec #yi+1=#yi+#yi avec 0 Selon une autre caractéristique de L'invention, Le procédé consiste à déterminer les coordonnées de chaque point d'intersection des deux courbes, à partir de L'intersection desdits deux segments caractéristiques, en ramenant à des valeurs entières, Les valeurs des coordonnées d'extrémités respectives des segments de chaque polyligne, calculées par l'ordinateur, ces valeurs entières correspondant respectivement aux coordonnées entières des points d'une grille du repère de référence, respectivement Les plus proches des extrémités des segments de la polyligne, ces valeurs entières étant enregistrées en mémoire. Selon une autre caractéristique, on calcule Les coordonnées de chaque point d'intersection des deux courbes à partir des valeurs entières correspondant respectivement aux coordonnées respectives d'extrémités des deux segments caractéristiques appartenant respectivement å deux polylignes interpolant respectivement Les deux courbes au voisinage de chaque point d'intersection. Selon une autre caractéristique, les deux segments caractéristiques sont déterminés en recherchant dans les polylignes de chaque courbe, à partir des valeurs entières des coordnnées d'extrémités des segments de ces polylignes, enregistrées en mémoire, des séquences monotones de ces valeurs entières, chaque séquence monotone correspond à une succession de segments délimitée par une première extrémité d'un premier segment extrême et par une deuxième extrémité d'un deuxième segment extrême, ces première et deuxième extrémités permettent de délimiter, pour chaque séquence monotone, une botte engLobante ayant deux bords parallèles à un premier axe du repère de référence et deux bords paralLèles à un deuxième axe du repère de référence, cette boite engLobante est déLimitée par Lesdites première et deuxième extrémités des segments extrêmes de la séquence monotone correspondante, les segments caractéristiques sont respectivement situés dans deux bottes engLobantes formant une paire de boites appartenant respectivement à deux séquences monotones des deux polyLignes, les deux boites de ladite paire se chevauchent au moins partiellement selon une zone commune, Lesdits segments caractéristiques sont situés dans Ladite zone commune. Selon une autre caractéristique, Le procédé consiste, par subdivisions successives des séquences des deux polylignes, à obtenir des paires successives de sous-boites englobantes, les coordonnées de chaque point d'intersection sont- calculées Lorsqu'à la suite desdites subdivisions successives, les sous-botes engLobantes de la paire obtenue par subdivision, contiennent respectivement et seulement les deux segments caractéristiques, un calcul des valeurs des coordonnées du point d'intersection est alors effectué à partir des valeurs des coordonnées respectives des extrémités des segments caractéristiques. Selon une autre caractéristique, le procédé consiste en outre à enregistrer en mémoire, pour chaque point d'intersection, un contexte d'intersection comprenant, Le numéro d'ordre de L'origine de chaque segment caractéristique, le rapport (P I /P P ou 01 Ol Q I IQ Q ) de La distance entre Le point d'intersection Cl 0 1 et L'origine de chaque segment caractéristique, à La longueur (P P ou Q Q ) de ce segment caractéristique, Cl Cl les coordonnées du point d'intersection mesurées dans Le repère de référence, et L'ordre des brins correspondant à chaque segment, autour du point d'intersection. Les caractéristiques et avantages de L'invention ressortiront mieux de la description qui va suivre, donnée en regard des dessins annexés dans Lesquels : - La figure 1 représente schématiquement un polygone de contrôle d'une courbe paramétrique C de degré 3, les diagonales D1 et D2 de ce polygone, ainsi qu'une polyligne PL interpolant La courbe C, la diagonale D étant La plus grande des deux Longueurs de D1 et D2, - la figure 2 représente schématiquement une portion de polyligne, dans La grille d'un repère de référence, - la figure 3 représente schématiquement deux polylignes P et Q présentant deux points d'intersection Il et IZ, et les boites englobantes pour des parties monotones de ces polylignes, - la figure 4 représente deux tableaux indiquant Les coordonnées des extrémités des segments de chaque polyligne, enregistrées en mémoire, - La figure 5 représente schématiquement des sous-boStes englobantes permettant de localiser L'un des points d'intersection de deux polylignes, - la figure 6 représente schématiquement les deux sous-boStes englobantes permettant de déterminer deux segments caractéristiques appartenant respectivement aux deux polylignes et définissant L'un des points d'intersection des polylignes, - La figure 7 représente schématiquement les deux segments caractéristiques et permet de mieux comprendre La détermination de L'un des paramètres d'un contexte d'intersection de deux polylignes, - La figure 8 représente schématiquement un ensembLe de traitement permettant de mettre en oeuvre Le procédé de L'invention, - ta figure 9 est un organigramme représentant Les étapes essentiel Les du programme mis en oeuvre dans Le procédé de L'invention. La méthode d'interpolation de "de Casteljau" sera mieux comprise à L'aide de la description de La figure 1. Cette figure représente schématiquement une courbe C de Bézier, de degré d=3 par exemple, dont le polygone de contrôle PC est défini par d+1=4 points de controLes UO, U1, U2, U3, de coordonnées (xO, y ), (x1, 0 y1), (x2, y2), (x3, y3), mesurées dans un repère de référence ( , x, y) ; ces coordonnées sont enregistrées dans La mémoire d'un ordinateur. Cette courbe peut être interpolée par une polyligne, selon La méthode de "de Casteljau" qui ne sera pas décrite ici en détail. La polyligne PL comporte N=4 segments dans L'exemple représenté ; la profondeur d'interpolation k nécessaire à l'obtention de cette polyligne est ici égale à 2, puisque N=2k=4. WANG: On a aussi représenté sur cette figure, Les deux diagonales Dl et D2 du polygone de contrôle PC. Selon L'invention, pour déterminer Ils intersections de deux courbes, on détermine tout d'abord Les polylignes respectives de ces courbes et pour cela, pour chaque courbe, on calcule tout d'abord la profondeur d'interpolation k par La formule de k=[Log4d(d-1)D] 8 k de manière à calculer le nombre N=2 de segments de chaque polyligne. Comme indiqué plus haut pour calculer k, il est nécessaire de rechercher, parmi Les valeurs des longueurs des diagonales D1 et D2 (dans l'exemple représenté sur La figure 1) du polygone de contrôle, la valeur maximaLe D. Cette recherche est aisée pour chaque courbe, puisque Les coordonnées de chaque point de contrôle du polygone de contrôLe de chaque courbe sont connues et sont enregistrées en mémoire. La connaissance de chaque valeur de N permet alors de connaltre chaque pas élémentaire (#x0, 6 yO) qui permet notamment de passer de chaque première extrémité de coordonnées (x0, y0) du premier segment S1 de chaque polyligne, à La deuxième extrémité de coordonnée (x1, y1) de ce segment. Cette deuxième extrémité du premier segment S1 correspond d'ailleurs à La première extrémité du segment suivant S2 de La polyligne. D'une façon générale, Les coordonnées (xi+1' yi+1) des extrém-ités des segments de chaque polyligne, sont calculées par récurrence par L'ordinateur, en évaluant a priori le pas (#xi, #yi) qu'il faut ajouter respectivement aux coordonnées (x;, yi) de l'extrémité d'un segment, pour passer aux coordonnées (xi+1, yi+1) de l'extrémité d'un segment suivant sur la polyligne. Ce calcul peut être qualifié de calcul de "pas en vant" ou "différences en avant". La reLation de récurrence s'établit de La manière suivante : xi+1 = xi + #xi et yi+1 = yi + #yi avec #xi+1 = #xi + #xi avec #yi+1 = #yi + #y̑i A L'initialisation, pour ;=0, on obtient : x1 = x0 + #x0 et #y0. x0 et y0 sont les coordonnées du premier point de contrôle U@. Le nombre N de segments 0 de la polyligne étant connu, on peut alors calculer par récurrence et a priori, les différences x1=x0+#2x0 et #y1=#y0+#2y0 et ainsi de suite jusqu'à #dxi+1 et #dyi+1. #x0 et #y0,#2x0 et #2y0, ...,#dx0 et #dy0, sont initialisés à partir des coordonnées des points de contrôle du degré d de-la courbe, et de La profondeur d'interpolation k. Ces calculs de coordonnées d'extrémités des segments de chaque polyligne de chaque courbe étant effectués, et ces coordonnées étant enregistrées en mémoire dans Leur ordre de calcul (pour C Chaque point d'intersection est recherché å partir de deux segments caractéristiques appartenant respectivement aux deux polylignes interpolant respectivement les deux courbes et se coupant au point recherché. La recherche de ces deux segments caractéristiques est d'ailleurs un autre aspect essentieL de L'invention. Avant de rechercher les points d'intersection, comme on Le verra plus loin en détail, les coordonnées calculées des extrémités des segments de chaque polyligne de chaque courbe, sont ramenées à des valeurs entières. Ces valeurs entières correspondent respectivement aux coordonnées entières des points d'une grille G du repère de référence (o,x,y), respectivement Les plus proches des extrémités des segments de chaque polyligne. Ces valeurs entières des coordonnées d'extrémités des segments, sont enregistrées en mémoire. La figure 2 représente la grille 6 dans Le repère (o,x,y), de pas p égal à L'unité. On a représenté schématiquement et en exemple, deux segments S1, S2 d'une polyligne d'une courbe, obtenue selon le procédé de L'invention. Ces segments présentent des extrémités ayant respectivement pour coordonnées ((x0,y0),(x1,y1)) et ((x1,y1),(x2,y2). Les valeurs des coordonnées (x0,y0) de la première extrémité du segment S1 sont ramenées aux valeurs entières Les plus proches, c'est-à-dire aux valeurs entières correspondant aux coordonnées du point d'intersection G1 de La grille G, le plus proche de cette première extrémité. De la même manière, Les valeurs des coordonnées (x1, > 1) sont ramenées aux valeurs entières des coordonnées du point G2 de la grille, le plus proche de l'extrémité de coordonnées (X1, y1). IL en est de même pour l'extrémité de coordonnées (x2, y) dont les valeurs sont ramenées aux valeurs entières des coordonnées du point le plus proche G3 de La grille. La figure 3 représente schématiquement et en exemple, deux polylignes P et Q respectivement interpolantes de deux courbes de Bezier, non représentées, dont on recherche les deux points d'intersection. La recherche des points d'intersection de ces deux courbes est ramenée à La recherche des deux points d'intersection I et I des polylignes qui leur 1 2 correspondent. On suppose que les intersections sont transverses, mais les explications qui suivent restent valables pour des courbes présentant des intersections non transverses, c'est-à-dire des courbes se chevauchant partielLement. On suppose par exemple que chaque polyligne comporte ici huit segments : P P , P P , ..., P P pour la polyligne P, et Q Q , Q Q t ..., Q Q , pour La polyligne Q. Les coordonnées (x01, yO), (x1, y1) (x8,y8) et (x0',y0'),(x1',y1'),...,(x8',y8') des extrémités P0,P1,...,P8 et Q0,Q1,...,Q8 de ces segments, sont enregistrées en mémoire dans leur ordre de calcul, l'indice i de repérage de chaque extrémité P ou Q allant ici de O à 8, tel que schématisé dans i i les tableaux 1 et 2 de La figure 4, relatifs respectivement aux polylignes P et Q. Les figures 4 et 5 vont maintenant permettre de mieux comprendre la recherche de chaque point d'intersection entre deux courbes, à partir des polylignes interpolant respectivement ces courbes. L'enregistrement en mémoire des coordonnées des extrémités Pot P1 ..., P8 et Q0, Q1' 1 Q8 des segments des polylignes P et Q, est représenté schématiquement -par Les tableaux 1 et 2 de La figure 4. On voit dans le tableau 1 que Les extrémités PO, P1, ..., P8 des segments de la polyligne P, de coordonnées respectives (x0,y0), (x1,y1),...,(x8,y8), sont enregistrées en memoire dans leur ordre chronologique de calcul, depuis la première extrémité P du premier segment, jusqu'à la deuxième extrémité P8 du dernier segment, L'indice i de ces extrémités étant ici compris entre 0 et N=8. Il en est de même pour les coordonnées (x0',y0'),(x1',y1'),...,(x8',y8') des extrémités Q0,Q1,...,Q8,des segments de la polyligne Q, comme représenté schématiquement dans Le tableau 2 de la figure 4. Selon L'invention, on recherche dans la polyligne de chaque courbe, à partir des valeurs entières des coordonnées d'extrémités des segments de cette polyligne, enregistrées en mémoire, des séquences monotones de valeurs entières (en x et en y). Chaque séquence monotone correspond à une succession de segments, délimitée par une première extrémité d'un premier segment extrême et par une deuxième extrémité d'un segment extrême. Dans L'exemple représenté sur la figure 3, La polyligne P interpolant L'une des courbes, présente une première séquence monotone dans les valeurs des coordonnées des extrémités P, P11 P2, P3, P4 des segments de cette polyligne, (valeurs de x et de y croissantes), et une deuxième séquence monotone dans les valeurs des coordonnées des extrémités P4, P5, P6, P P d'autres segments de cette polyligne (valeurs de 7' 8 x croissantes et valeurs de y décroissantes). Ces première et deuxième séquences monotones pour La polyligne P, sont désignées par M et Ma dans Le tableau 1 de la figure 3. Les coordonnées des extrémités des segments des séquences M et n forment des sous-tableaux du tableau 1. De La même manière, pour la polyligne Q interpolant L'autre courbe, on distingue une première séquence monotone dans les valeurs des coordonnées des extremités Q0,Q1,Q2,Q3,Q4 et une deuxiéme séquence monotone dans les valeurs des coordonnées t des extrémités Q4,Q5,Q6,Q7,Q8 des segments de cette polyligne. Ces deux séquences monotones sont désignées par M' et M' dans le tableau 2 de la figure 3. Les 1 2 coordonnées des extrémités des segments des séquences M' et M' forment des sous-tableaux du tableau 2. I 2 On voit sur ces figures que chaque séquence est délimitée par Les coordonnées de La première extrémité du premier segment de la séquence (premier segment extrême de La séquence), et par les coordonnées de ta deuxième extrémité du dernier segment de La séquence (deuxième segment extrême de la séquence). C'est ainsi par exemple, que La séquence M est délimitée par Les coordonnées (xO, yO) de La première extrémité P0 du püremier segment P0P1 de cette séquence, et par les coordonnées (x8,y8) de la deuxième extrémité P du dernier segment P de cette séquence. 8 8 La recherche des parties monotones de chaque polyligne est aisée, à partir des coordonnées des extrémités des segments, enregistrées en mémoire. Les délimitations des séquences monotones permet de définir des "bottes englobantes" B1, B2, correspondant respectivement aux séquences M1, M2, pour la polyligne P et des "bottes englobantes" 8' B' 2' correspondant respectivement aux séquences M' , M'2, pour la polyligne Q. Deux bords de chacune de ces bottes englobantes sont parallèles à L'axe x du repère de référence, tandis que deux autres bords sont parallèles à l'axe y. Les positions de ces bords sont fournies par les coordonnées des première et deuxième extrémités des segments extrêmes de chaque séquence, dont les valeurs sont enregistrées en mémoire. Sur La figure 3, on voit que les bottes B et B'1 forment une paire intéressante puisqu'elles présentent une zone commune Z1, délimitée par le chevauchement de ces deux bottes, dans laquelle est située le premier point d'intersection Il des deux polylignes P et Q. IL en est de même pour les boites englobantes B2 et B2' qui présentent une zone commune Z2, dans laquelle est situé le deuxième point d'intersection 12 des deux polylignes P et Q. La zone Z3, commune aux bottes englobantes B' et B , n'est pas intéressante, car elle me contient aucun point d'intersection. Le procédé de l'invention va consister, par subdivisions binaires successives dans les soustableaux relatifs aux parties monotones de chaque polyligne, à rechercher grâce aux bottes englobantes, des zones plus réduites de chevauchement éventuel. Pour cela, on subdivise chaque séquence monotone de chaque polyligne en deux parties, gauche et droite, dont les boites englobantes sont données sans calcul par les points extrémités de ces parties ; puis on recherche le chevauchement éventuel de chacune des deux sous-botes d'une polyligne avec chacune des deux sous-botes de l'autre polyligne. La figure 5 permet de mieux comprendre comment, après une ou plusieurs subdivisions de ce type, on peut, pour Le point d'intersection Il par exemple, déterminer les deux segments caractéristiques POP et Q Q qui définissent ce point d'intersection. Cl 01 Pour simplifier la compréhension de cette figure, on n'a représenté que la partie gauche de La figure 3, relative au point d'intersection Il. Chaque boite englobant est parfaitement délimitée et connue, puisque pour la botte B parexemple, on connaît, grace au tableau 1 de La figure 4, Les coordonnées des extrémités P et P4 délimitant 0 cette boite. IL en est de même pour la boite 8'1, délimitée par Les coordonnées des extrémités Q et Q 0 4 La zone Z1 de chevauchement des boites B et B' 1 I définie plus haut, est donc facile à déterminer. à partir de ces coordonnées. Cependant cette zone ZI, contient bien un seul segment P P pour la polyligne P, mais contient deuxsegments Q0Q1 et Q1Q2 pour la polyligne Q. Il est donc encore impossible de savoir si L'intersection Il recherchée est définie par l'intersection de P0P1 avec Q Q ou avec Q Q Cl 12 On effectue alors, comme Le montre la figure 5, une subdivision binaire de B et B'1, en "coupant" ces boites englobantes, chacune en deux sous-boîtes englobantes, B11 et B12 pour la boîte B1, B11' et B12' pour La boite B . On cherche alors les zones de chevauchement possibles entre la sous-boîte B11 de la polyligne P et les sous-boîtes B11' et B12' de la polyligne Q, puis entre la sous-boîte B12 de la polyligne P et les sous-boîtes B11' et B12' de la potyligne Q.Seule la zone Z4 de chevauchement des sous-boites S et B'11, est intéressante. Cette zone Il Z4 contient cependant encore deux segments pour la polyligne Q. On effectue alors une nouvelle subdivision des sous-boîtes B11 et B11', comme indiqué plus haut, de manière à obtenir de nouvelles sous-boîtes englobantes, parmi lesquelles deux sous-botes B et 111 B' telles que représentées sur la figure 6, se chevauchent selon une zone Z5 ; cette zone contient seulement les deux segments caractéristiques P0P et Q0Q1, ou des portions de ces segments, qui permettent de localiser le point d'intersection Il dans cette zone. Les coordonnées du point I sont calculées à partir des valeurs entières correspondant respectivement aux coordonnées d'extrémités des segments P0P1 et Q0Q1. Les coordonnées calculées du point d'intersection sont exprimées par des nombres rationnels. Le calcul de ces coordonnées n'est pas donné ici en détail car il est à la portée de l'homme de métier. On enregistre alors en mémoire, l'ordre ou indice i=0 de la première extrémité P0 du segment caractéristique concerné par L'intersection I1, pour la polyligne P, et un nombre rationnel représentant le rapport des distances P0I1/P0P1 (0,3/4) indique par exemple que 1 est aux 3/4 du segment P P , à partir de P0). Un enregistrement similaire est effectué pour segment caractéristique Q Q de la polyLigne Q (on CI enregistre l'indice -i=O de Q et le nombre rationnel 0 Q I /Q Q ). Cl Cl Enfin, on enregistre également les coordonnées de I1, calculées dans le repère de référence. Ce calcul n'est pas donné en détail car il est à La portée de L'homme de métier. Ces paramètres (valeurs de i correspondant à la première extrémité de chaque segment caractéristique, nombres rationnels exprimant les distances respectives entre ces premières extrémités des segments caractéristiques et Le point d'intersection I1, et coordonnées du point I1 dans Le repère de référence > appartiennent a un "contexte d'intersection. Ce contexte d'intersection, comporte en outre des paramètres supplémentaires qui vont être décrits à l'aide de la figure 7. Ces paramètres concernant L'ordre d'apparition des "brins" autour du point I1, lorsqu'on tourne autour de ce point, dans le sens direct par exemple, indiqué par La flèche F sur la figure. Ces brins sont des vecteurs bl, b2, b3, b4 ayant pour origine le point I .Si, pour des traitements graphiques ultérieurs éventuels, la polyligne P est parcourue de l'extrémité P vers l'extrémité P du O 1 segment P P , le premier brin rencontré est le brin b3, et l'ordre des brins autour du point I est donc b3, ba, b4, bl, Par permutation circulaire, on sait alors que si le segment Q Q par exemple est parcouru à Cl partir de Q1 L'ordre des brins rencontrés autour du point li &num; est alors ba, b4, bl, b3. Cet ordre peut être déterminé facilement par des calculs simples en géométrie, à partir des valeurs des coordonnées des extrémités des segments POP et Q Q CI CI Il est évident que d'autres contextes d'intersection sont enregistrées pour les autres points d'intersection. La figure 8 représente schématiquement un ensemble de traitement permettant de déterminer les points d'intersection de courbes paramétriques, selon le procédé de l'invention. Cet ensemble comporte de façon connue, un terminal 1 relié à un ordinateur 2, lui-meme relié à une mémoire 3 capable d'enregistrer les données à traiter, Les résultats des traitements, ainsi que le programme permettant d'effectuer les traitements qui viennent d'être décrits. Ce programme n'est pas décrit en détail et seul son organigramme est représenté schématiquement sur la figure 9. Les traitements essentiels qui apparaissent sur cet organigramme ont été décrits plus haut. Le procédé qui vient d'être décrit pour des courbes paramétriques polynomiales reste valable pour des calculs paramétriques rationnelles. En effet, les traitements effectués pour des courbes paramétriques rationnelles peuvent etre- ramenés aux traitements effectués pour les courbes paramétriques polynomiales. REVENDICATIONS 1. Procédé pour déterminer Les intersections de courbes paramétriques polynomiales de Bézier, pour l'aide au graphisme dans la conception ou le design-as sisté par ordinateur relié à un terminal graphique, cha que courbe de degré d étant décrite mathématiquement par la fonction vectorielle U(t)=(x(t), y(t)),avec 0 définie par d+l points de contrôle Ui, avec i=O, 1, d, d, délimitant un polygone de contrôle, chaque point de contrôle Ui ayant des coordonnées réeles (xi, yi) dans un repère de référence, ces coordonnées étant enregistrées dans une mémoire de l'ordinateur, le procédé consistant à déterminer les points d'intersection des courbes, à partir de polylignes (P, Q) interpolant respectivement ces courbes, chaque polyligne étant formée de N segments successifs ayant chacun deux extrémités situées sur un arc de courbe correspondant, caractérisé en ce qu'il consiste à choisir le nombre N de segments de chaque polyligne en relation avec une profondeur k d'interpolation, tel que N=2k, N et k étant spécifiques pour chaque courbe, cette profondeur étant donnée par la relation k=[Log4d(d-1)]D, en calculant la diagonale D du 8 polygone de contrôle à l'aide de l'ordinateur, à partir des coordonnées des points de -contrôle enregistrées en mémoire, les valeurs de N, k et D étant enregistrées en mémoire, puis à déterminer, en calculant par récurrence à l'aide de l'ordinateur, les coordonnées (xi+1,yi+1) des extrémités des segments de chaque polyligne, entre les points de contrôle U et Ud, en évaluant a priori des différences en avant (#xi,#yi)qu'il faut ajouter respectivement aux coordonnées (xi, yi) de l'extrémité d'un segment pour passer aux coordonnées (xi+1,yi+1) de l'extrémité d'un segment suivant sur la polyligne, de sorte que : xi+1=xi+#xi et yi+1=yi+#yi avec #xi+1=#xi+#2xi et #yi+1=#yi+#2yi avec 0 de deux courbes est déterminé par L'intersection de deux segments caractéristiques (P P , QoQ1) appartenant respectivement aux deux polylignes interpolant respectivement Les deux courbes, Les coordonnées des extrémités des segments de chaque polyiigne sont enregistrées en mémoire de manière ordonnée selon les valeurs croissantes de i entre 0 et N, les coordonnées des extrémités des segments pouvant être lues en memoire,- en vue d'obtenir le dessin de ces segments et de chaque point d'intersection, par le terminal. 2. Procédé selon La revendication 1, caractérisé en ce qu'il consiste à déterminer les coordonnées de chaque point d'intersection des deux courbes, à partir de L'intersection desdits deux segments caractéristiques, en ramenant å des valeurs entières les valeurs des coordonnées d'extrémités respectives des segments de chaque polyligne (P, Q) calculées par L'ordinateur, ces vaLeurs entières correspondant respectivement aux coordonnées entières des points d'une grille (6) du repère de référence (O, x, y), respectivement les plus proches des extrémités des segments de La polyligne, ces valeurs entières sont enregistrées en mémoire. 3. Procédé se Ion la revendication 2, caractérisé en ce qu'on calcule les coordonnées de chaque point dtintersection (I1, I2, . > des deux courbes à partir des valeurs entières correspondant respectivement aux coordonnées respectives d'extrémités des deux segments caractéristiques appartenant respectivement aux deux polylignes interpolant respectivement les deux courbes au voisinage de chaque point d'intersection. 4. Procédé selon la revendication 3, caractérisé en ce que les deux segments caractéristiques (P P , QQ sont déterminés en recherchant dans lespolylignes (P,Q) de chaque courbe, à partir des valeurs entières des coordnnées d'extrémités des segments de ces polylignes enregistrées en mémoire, des séquences monotones (M1, M1'-M2,M2'...) de ces valeurs entières, chaque séquence monotone correspond à une succession de segments délimitée par une première extrémité d'un premier segment extréme et par une deuxième extrémité d'un deuxième segment extrême, ces première et deuxième extrémités permettent de délimiter pour chaque séquence monotone, une boite englobante (B1 ou B' ou B ...) ayant deux bords parallèles à un premier axe du repère de référence et deux bords parallèles à un deuxième axe du repère de référence, cette boite englobante est délimitée par lesdites première et deuxième extrémités des segments extrêmes de la séquence monotone correspondante, les segments caractéristiques sont respectivement situés dans deux boites englobantes formant une paire de boites appartenant respectivement à deux séquences monotones respectives des deux potytignes, les deux boites de Ladite paire se chevauchent au moins partiellement selon une zone commune, lesdits segments caractristiques sont situés dans Ladite zone commune. S. Procédé selon La revendication 4, caractérisé en ce qu'il consiste, par subdivisions successives des séquences monotones des polylignes, à obtenir des paires successives de sous-botes englobantes, Les coordonnées de chaque point d'intersection sont calculées lorsqu'à La suite desdites subdivisions succesives, les sous-boîtes englobantes de la paire obtenue par subdivisions, contiennent respectivement et seuLement les deux segments caractéristiques, un calcul des valeurs des coordonnées du point d'intersection est alors effectué à partir des valeurs des coordonnées respectives des extrémités des segments caractéristiques. 6. Procédé selon la revendication 5, caractérisé en ce qu'il consiste en outre à enregistrer en mémoire, pour chaque point d'intersection, un contexte d'intersection comprenant, le numéro d'ordre de L'origine de chaque segment caractéristique, le rapport (P0I1/P0P1 ou Q0I1/Q0Q1) de la distance (P0P1 ou Q0i1) entre le point d'intersection I1 et l'origine (P ou G > de chaque segment caractéristique, à ta longueur (P0P1 ou Q0Q1) de ce segment caractéristique, -les coordonnées du point d'intersection mesurées dans te repère de référence, et L'ordre des brins correspondant å chaque segment, autour du point d'intersection.