Brevet FR2646259A1 — publié le 19901026

PROCEDE D'INSERTION ET/OU DE GOMMAGE DE COURBES ET/OU D'ELEMENTS DE COURBES, DANS UN DESSIN REALISE PAR ORDINATEUR DESCRIPTION L'invention concerne un procédé d'insertion et/ou de gommage de courbes et/ou d'éléments de courbes, dans un dessin réalisé par ordinateur et ceta de manière interactive, par un opérateur à partir d'un périphérique d'entrée de L'ordinateur, le dessin mémorisé dans l'ordinateur étant visible directement sur L'écran de l'ordinateur et pouvant être reproduit avec une résolution variable au moyen d'une imprimante. Le procédé est basé sur une description du dessin sous forme de carte planaire. Cette description consiste selon le procédé à établir une structure de données décrivant les données réelles que L'on enregistre dans la mémoire de l'ordinateur. On pourra trouver une description d'une carte planaire Limitée au cas des segments de droite dans Le document intitulé "Actes de MICAD 84" Hermês-Paris, 1984 - D. Michelucci et M. Gangnet - "Saisie de plans à partir de tracés à main-levée" et dans le document intitulé "Rapport de Recherche 84-12" - Ecole Nationale Supérieure des Mines de Saint-Etienne, 1984 - M.Gangnet et D. Michelucci. Cependant, afin de faciliter la compréhension de la présente demande, on rappelle dans ce qui suit Les définitions essentielles concernant une carte planaire, en référence aux figures la et lb. Une carte planaire décrit la partition du plan définie par un ensemble fini de courbes. Une carte planaire est définie par Le couple (S, A) dans lequel S est un ensembLe fini de sommets, chaque sommet étant distinct et dans lequel A est un ensemble fini d'arêtes décrites par des arcs de courbes n'ayant d'autres intersections que Les sommets de L'ensemble S. Dans La description du dessin, qui se trouve en mémoire sous forme d'une structure de données, on associe à chaque arête deux brins qui définissent Les deux côtés de L'arête. Deux cas peuvent se produire : - si l'arête e est incidente à deux sommets S1 et S2, alors Les deux brins sont définis par Les couples (51,52) et (S2,S1) respectivement ; - Si L'arête e est incidente à un seul sommet, alors e forme une boucle et les deux orientations directe et indirecte définissent Les deux brins associés à e. Par ailleurs, à chaque sommet est associé un ensemble non vide de brins qui peut être ordonné. On appel Le *(b) Le brin suivant du brin b dans L'ordre direct autour du sommet incident à b. On appelle ordre la reLation d'ordre total définie par i sur L'ensemble des brins incidents à un même sommet. On appelle (b) L'autre brin de l'arête associée à b. Les deux applications &alpha; et # représentent mathématiquement des permutations de S. Un contour peut alors être décrit par L'ensembLe C(b) : C(b) = {b, &alpha;#(b),..., (&alpha;#)@ (b)} où L est Le pLus petit entier naturel te que 1+1 b=(#w) (b). Connaissant &alpha; et #, il suffit donc de connaître un brin d'un contour pour obtenir la Liste des brins de ce contour. En pratique on ira Lire en mémoire un brin d'un contour et un parcours de la structure de données permettra d'obtenir La Liste des brins de ce contour. IL est rappelé également que L'on associe une structure arborescente à la structure d'une carte planaire, cette structure arborescente définissant une reLation d'ordre partiel d'incLusion des composantes connexes formées par Les arêtes. La structure arborescente est appelée arbre d'inclusion des contours (figure lob). La racine de L'arbre est un contour virtuel c interne qui décrit La face infinie du plan. Les fiLs d'un contour interne sont Les contours externes des composantes connexes contenues dans ce contour interne (E et E sur la figure la). Les fils d'un contour I 3 externe sont Les contours internes connexes d'une même composante (cl, c2, 3 sur la figure la). Dans cet arbre, une face est décrite par un contour interne et éventuellement par l'ensemble de ses contours externes fils. Une# composante connexe est décrite par un contour externe et .éventuellement par l'ensembLe de ses contours internes fils connexes. Ainsi, Les feuilles de l'arbre des contours sont soit des contours internes ne contenant aucune composante connexe, soit des contours externes sans aucun contour interne fils. L'arbre d'inclusion fournit une bonne représentation de la partition du plan et est donc utilisé pour : obtenir Les contours frontière d'une face, obtenir Les composantes connexes, localiser un point, etc. Ainsi, dans Le procédé conforme à L'invention, La carte planaire qui est décrite dans une structure de données n'est pas Limitée à des segments de droite. Ladite structure est divisée, selon le procédé conforme à L'invention, en deux parties distinctes : une structure de données géométriques et une structure de données topologiques. Conformément à L'invention également, dans La structure de données géométriques : - une courbe est décrite par un polygone de contrôLe et une série ordonnée d'arcs. - L'orientation d'une courbe est donnée par L'ordre de ses points de contrôle. - un arc est une portion de courbe délimitée par deux points, L'orientation d'un arc est donnée par L'ordre des paramètres de ses points extrémités. - Les arcs se projettent sur les arêtes. - un point est repéré par un paramètre curviligne sur une courbe. Un point peut être un point extrémité d'une courbe, un point dtauto-intersection d'une courbe, ou un point dtintersection entre deux courbes. Les points se projettent sur Les sommets Il est rappelé que La structure de données topologique comprend des données représentant des brins, des sommets, des arêtes, des contours. Conformément à l'invention, -dans ta structure de données topologiques - un brin b est décrit par le brin & b), le brin t (b), Le sommet autour duquel est incident Le brin b, L'arête à laquelle est associe Le brin b et Le contour auquel appartient Le brin b. - un sommet s est décrit par des coordonnées cartésiennes dans un espace que L'on s'est borné au départ et que Lton nomme grille, et par un brin b incident autour de ce sommet s. Ce brin permet d'obtenir la Liste des brins incidents à s. - une arête e est décrite par la liste des arcs confondus portés par cette arête e et par un brin b de e. L'autre brin de e est obtenu par La relation - un contour c est décrit par un brin b appartenant à ce contour c et des Liens vers les contours peres, fils et frères de c utilisés pour le parcours de L'arbre d'inclusion des contours. On a donc représenté sur La figure la un exempLe de dessin sur lequel a été repéré chaque élément de sa topologie, ainsi que sur La figure lb l'arbre d'inclusion des contours de La carte associée à de dessin, sous la forme d'une structure arborescente. En cherchant à procéder à des insertions et/ou à des gommages de courbes et/ou d'éléments de courbes pendant La réalisation d'un dessin par ordinateur, la demanderesse s'est heurtée au problème de la réalisation d'un outil interactif, c'est-à-dire d'un outil qui permette à L'utilisateur d'insérer La courbe qu'il désire dans Le dessin de façon quasi instantanée, L'utilisateur n'ayant pas à attendre. A La suite de longs travaux menés par la demanderesse, cette dernière a cherché à résoudre Le problème non encore posé qui est celui, non seulement d'obtenir un procédé interactif, mais également un procédé qui soit incrémental, et qui permette en particuLier d'éviter le recalcul de la carte planaire après chaque insertion de courbes etlou d'éléments de courbes. D'autre part, les procédés actuels de dessin assisté par ordinateur ne présentent pas une grande souplesse car il est pratiquement impossible d'effacer un élément de courbe Limité par des points d'intersection sans effacer La courbe tout entière. La présente invention permet de remédier à ces problèmes. ELLe a pour objet un procédé d'insertion et/ou de gommage de courbes et/ou d'éléments de courbes dans un dessin réalisé par ordinateur qui permet à la fois d'obtenir une grande précision dans le tracé du dessin et d'être interactif, et dans lequel l'insertion se fait de façon incrémentale si bien que, lorsqu'un élément de courbe est inséré, une mise à jour de certaines des informations de la structure de donnée de La carte stockée en mémoire suffit, tous les éléments de La carte planaire n'étant pas recalculés. La présente invention concerne un procédé d'insertion et/ou de gommage de courbes et/ou d'éléments de courbes dans un dessin réalisé par ordinateur, ledit ordinateur comportant une mémoire dans Laquelle est stockée une structure de données caractérisé en ce que la structure décrit Les données du dessin dans lequel on réalise des insertions et/ou des gommages, sous forme d'une carte planaire à laquelle on associe un arbre d'inclusion des contours, Ladite carte comportant un ensemble de faces, chacune étant délimitée par un ou plusieurs contour(s) porté(s) par les arêtes du dessin, et caractérisé en ce qu'il comporte Les étapes suivantes : a) - au préalable - associer à la courbe à insérer Les paramètres t et o t , t correspondant à L'origine P de La courbe, t n o o n à l'autre extrémité P ; n - locaLiser La face de la carte dans LaqueLle se trouve L'origine de La courbe à insérer ayant pour paramètre t, o - affecter à un paramètre t la valeur du paramètre t, o b) - puis de façon itérative - déterminer les intersections entre l'arc de courbe de paramètre (t#, t ) à insérer et toutes Les courbes n portées par les arêtes des contours te la face ;; - insérer les points d'intersection de paramètre t sur L'arc (t , t ) ; n - affecter Le paramètre ti+1 au point d'intersection suivant Le point de paramètre ti ; - insérer dans la face considérée, en l'enregistrant en mémoire dans La structure de données, L'arc ayant pour paramètre (tj, t ). i+l Selon une deuxième caractéristique du procédé, La Localisation de la face dans laquelle se trouve l'origine de La courbe à insérer et ayant pour paramètre t comporte les étapes suivantes : o - insérer fictivement une droite D ayant pour origine o P , L'origine de la courbe à insérer, et pour o extrémité un point P connu situé dans une première e face dite face infinie ; - déterminer les intersections entre la droite D et o toutes Les courbes de la carte planaire a) - dans le cas où des intersections ont été déterminées - caLcuLer la distance d entre ces intersections et le point origine P o - déterminer l'arête e pour laquelle cette distance d est minimum, - enregistrer L'origine P dans La face â laquelle o appartient le brin de L'arête e qui voit P o b) - dans le cas où aucune intersection n'a été déterminée :: - enregistrer L'origine P dans La première face. o Selon une troisième caractéristique du procédé, L'étape d'insertion dans La carte planaire d'un arc ai dont on connaît Les points extrémités, Pi, Pi+1, cet arc a étant porté par une arête e et décrit par deux brins de l'arête e, de sommet S, S', consiste à: - créer un sommet pour chaque brin de e en enrelistrant dans la structure de données S et S', dans le cas ou ces sommets ne sont pas déjà dans La carte ; - créer l'arête e en enregistrant dans la structure de données une donnée comportant L'arc a et un des deux brins, dans Le cas où cette arête n-'existe pas déjà dans la carte. Selon une quatrième caractéristique de l'invention, l'étape de détermination des intersections entre la courbe à insérer et une face donnée comporte en outre une étape de marquage de cette face. Avantageusement, étape de marquage de la face consiste à réserver un champ dans le codage d'une face en mémoire, susceptible d'être renseigné des que l'on procède à la détermination des intersections entre L'arc de paramétres (t,, t ) et la face. 1 n Avantageusement, le procédé comporte une étape consistant, après l'insertion d'un arc de paramètres (t , t ) par enregistrement dans La i+l structure de données, à effectuer une comparaison du paramètre courant t au paramètre t et à passer à La i n face suivante Lorsque ces deux paramètres ne sont pas égaux, l'insertion étant terminée dans le cas contraire. Avantageusement, le procédé comporte une étape de comparaison de La face en cours avec Les faces déjà traitées pour insérer directement L'arc de paramètres (t., t. ) dans cette face dans le cas ou la i i+l face a déjà été traitée et passer dans une nouvelle face dans le cas contraire. Selon un autre aspect de L'invention, le procédé comporte en outre une étape de mise à jour de l'arbre d'inclusion des contours consistant à insérer ou à supprimer une arête dans la structure de données. Avantageusement, L'étape de mise à jour de L'arbre d'inclusion des contours dans le cas de l'insertion consiste, pour une arête e portée par l'arc a de paramètres (t i, t 1) å : i i+1 a) - au préalable : - répertorier sous forme d'une table en mémoire un ensemble de cas possibles pour une arête dans une carte planaire ; b) - puis après l'insertion d'un arc a - déterminer par comparaison avec les différents cas possibles le cas de L'arête e portée par l'arc a ; c) - mettre à jour L'arbre des contours en fonction du cas précédemment déterminé en effectuant éventuellement une - suppression d'un contour Lorsque deux contours sont fusionnés, ou - création d'un nouveau contour, ce contour devenant fils ou frère du contour scindé dans L'arbre des contours. Selon un autre aspect de l'invention, L'étape de mise à jour de l'arbre d'inclusion des contours dans le cas d'une suppression, consiste, pour une arête e, à: a) - au préalable - répertorier sous forme d'une table en mémoire un ensemble de cas possibles pour une arête dans une carte planaire ; b) - pour l'arête e à supprimer : - répertorier le nombre de sommets pendants de L'arête, le type de contour interne ou externe auquel appartiennent les brins de cette arête ; - déterminer par comparaison avec les différents cas possibles de la table te cas de cette arête ; c) - puis à mettre à jour L'arbre des contours en fonction du cas précédemment déterminé en effectuant éventuellement : - une suppression ; - une scission ; - aucune modification. Selon une autre caractéristique, le procédé comporte une étape de gommage d'une courbe etiou d4un élément de courbe consistant à : 1) Localiser L'élément à gommer ; 2) gommer cet élément - en effectuant une suppression dans la structure de données topologiques des sommets, arêtes et contours associés à la courbe, - en conservant en mémoire dans la structure de données les arcs et les points de cet élément, - en renseignant un champ prévu dans les données relatives aux arcs et aux points signifiant que les éléments correspondant aux arcs et aux points sont effacés. 3) mettre à jour L'arbre d'inclusion des contours. Avantageusement l'étape de gommage des arêtes pendantes, d'un contour, d'une face, d'une composante ou d'une carte consiste à A) chercher une arête e dont au moins un sommet est pendant ; B) si l'arête e existe (a) conserver le sommet s non pendant de e, (b) supprimer l'arête e, (c) si s est devenu un sommet pendant après L'étape B. (b), réitéer en B.(a) avec une arête e incidente en s, (d) réitérer en A. D'autres caractéristiques et avantages de l'invention vont apparaître à la Lecture de la description faite -à titre illustratif et nullement limitatif, en réference aux dessins annexés sur Lesquels - les figures la et lb représentent respectivement un exemple de dessin à représenter avec en référence les éléments de la carte planaire correspondante et un graphe représentant la structure arborescente de l'arbre des contours correspondant à ce dessin, - les figures 2a et 2b représentent un ordinogramme représentant les étapes essentielles du procédé selon l'invention, - les figures 3a et 3b représentent l'étape de détermination du cas lors de la mise à jour de L'arbre des contours, respectivement dans le cas d'une insertion et dans le cas d'une suppression, selon le procédé conforme à l'invention, et - la figure 4 représente un exemple de dessin correspondant à chaque cas répertorié dans la table, selon le procédé conforme à l'invention. Le procédé est susceptible d'être mis en oeuvre au moyen de tout type d'ordinateur, par exemple une station de travail de Digital Equipment Corporation programmée à cet effet. L'ordinateur comporte une mémoire dans laquelle est stockée une structure de données qui permet de décrire les données de n'importe quel dessin que l'on désire réaliser au moyen de cet ordinateur et qui pourra être visualisé directement par l'écran de L'ordinateur ou à l'aide d'une imprimante quelle que soit la définition de l'imprimante. La structure de données permet à la fois d'effectuer une description d'un dessin sous sa forme topologique et sous sa forme géométrique. Tout dessin à réaliser par le procédé est vu sous forme d'une carte planaire. La description d'une carte planaire consiste donc à prévoir une structure de données topologique dans laquelle seront prévus des champs destinés à recevoir des données correspondant à des contours, des données correspondant à des sommets, des données correspondant à des arêtes et des données correspondant à des brins. Elle consiste également à prévoir une structure de données géométrique dans laquelle sont prévus des champs destinés à recevoir des points en liaison avec un sommet, des arcs en liaison avec une arête, des données correspondant aux brins attaches aux arcs, ces brins étant tes Liens entre La structure géométrique et la structure de données topo logique. La figure 2a représente un ordinogramme dans lequel les blocs tracés en pointillé représentent les étapes essentielles du procédé selon l'invention Le premier bloc I est relatif à L'étape d'initialisation, Le deuxième bloc Il est relatif à L'étape de calcul des intersections, le troisième bloc III est relatif à L'étape de mise à jour et le quatrième bloc IV est relatif à l'étape d'itération. Le premier traitement de la courbe à insérer consiste à modéliser la courbe en la transformant sous la forme de courbe de Bézier puis en procédant à une interpolation, par exemple au moyen de la méthode de De Casteljau. De manière préférée, ta méthode utilisée est la méthode qui est décrite dans la demande de brevet n0 déposée ce même jour par La demanderesse, relative à un procédé d'intersection de courbes dans un dessin réalisé par ordinateur. Ce premier traitement ne fait pas l'objet de L'invention puisqu'il se situe en amont de L'étape d'initialisation I. On pourra se reporter au document cité pour plus de détails. L'étape préalable d'initialisation consiste tout d'abord à affecter à la courbe å insérer un paramètre t =t pour lequel t correspond à l'origine i o o P de la courbe, le paramètre t correspondant à o n L'autre extrémité de la courbe. Cette étape d'initialisation I consiste en outre à localiser La face de la carte planaire dans laquelle se trouve L'origine de la courbe à insérer ayant pour paramètre t (bloc 20) et à mémoriser La o face F dans laquelle se trouve cette origine (bloc 21). L'étape d'intersection II (blocs 30, 32) consiste à trouver tous Les points d'auto-intersection de La courbe à insérer puis les points d'intersection de La courbe à insérer avec les courbes portées par les arêtes des contours de cette première face identifiée. L'étape de mise à jour III (blocs 50, 51) consiste dans le cas de L'insertion à insérer le premier arc trouvé de paramètres (ti, i+1). A la première itération t est l'origine de la courbe. Cette étape consiste en outre à effectuer une mise à jour de l'arbre d'inclusion des contours (bloc 51). L'étape IV consiste à effectuer une itération du paramètre t en comparant ce paramètre au paramètre t et, dans La mesure où t n'est pas égal à t , a n i n passer de La face incluant L'arc défini par les paramètres (ti, ti+1), à la face adjacente suivante et, à recommencer chacune des étapes à partir de l'étape 11. De manière plus détaillée, dans l'étape d'initialisation I, il s'agit de trouver à quelle face F appartient Le point P de paramètre t de la courbe C o o à insérer bloc 20). Le procédé consiste alors de manière avantageuse à insérer fictivement une droite D o ayant pour origine ce point P et pour extrémité un o point P connu, situé à L'extérieur d'un rectangle e contenant la carte planaire. Le point P appartient e donc à la face qualifiée de face infinie F#. La demi-droite est insérée de manière fictive, c' est-à-dire qu' elle est uniquement utilisée pour effectuer Le calcul des intersections et ne fait pas l'objet d'une mise à jour de La carte planaire. Le principe de la localisation de L'origine de La courbe à insérer consiste à chercher L'arête e telle que La distance entre l'intersection des arêtes e avec La droite D et Le point P soit minimale. Au départ Le o o point courant est Le point P , ce point étant situé e dans La face infinie F Pour obtenir l'arête e de façon optimale, on parcourt Les faces adjacentes de proche en proche du point P vers te point P le long de la droite D , la e o o dernière intersection trouvée étant La plus proche. Ce parcours consiste à déterminer les points d'intersection entre la droite et chacune des faces au moyen de L'arbre des contours. Une méthode particulière qui permet de déterminer les intersections entre deux courbes est décrite dans La demande déposée ce même jour par La demanderesse. On mémorise la face F à laquelle appartient te point P . Dans le cas où aucune intersection n'a été o déterminée, on mémorise la face infinie F (bloc 21). Deux cas particuliers peuvent se produire le point à localiser P se trouve sur un sommet ou sur o une arête de La carte. Si le point se trouve sur un sommet, on utilise Il ordre en ce sommet pour déterminer la face contenant le brin incident à P . Si o le point se trouve sur une arête e on utilise I' ordre au sommet (associé à P ) nouvellement créé o par scission de L'arête e. Le paramètre t pour le point P correspond 1 o au paramètre t o L'étape d'intersection Il comporte une sous étape 30 consistant à effectuer des comparaisons de L'arc ai défini par les paramètres (t1, tn) en l'occurrence (t , t ), Lors de la première itération, n avec toutes les courbes de la face F. L'on détermine pour cela les intersections entre L'arc a de paramètres (t , t ), c'est-à-dire la i i n courbe toute entière à la première itération, et toutes les courbes portées par Les arêtes du contour de la face F. Le point d'intersection te plus proche du point de départ, soit P à La première itération, 0 définit un premier arc de paramètres (ti, ti+ 1), qui va être inséré dans la face considérée (bloc 32). L'étape de mise à jour III comporte donc une sous étape 50 d'insertion de L'arc (tj, t ), courant dans la face considérée, soit F pour le premier arc. Puis dans L'étape d'itération IV, on procède à L'itération du paramètre ti qui devient Le paramètre ti+1 en ayant auparavant comparé ti+1 à tn , c'est-à- dire en ayant vérifié que l'on n'a pas atteint l'extrémité P de la courbe (bloc 70). n Dans Le cas où il s'agit de l'extrémité P de n la courbe, le procédé d'insertion est terminé. Dans le cas contraire, L'on passe de La face dans laquelle on vient d'insérer un arc à la face adjacente (bloc 71) et l'on recommence à nouveau à L'étape Il d'intersection, c'est-à-dire à comparer l'arc (t., t ), i ayant été incrémenté, avec toutes les i n courbes de La nouvel Le face non encore intersectées. On va décrire maintenant La sous-étape 31 de comparaison de L'arc (ti, tn ), avec toutes Les courbes de La face courante de manière plus détaillée. Cette étape comporte une phase de calcul des intersections. Soit C la courbe à insérer et B une courbe de La face courante. La détermination des points d'intersection permet d'obtenir pour chaque intersection entre la courbe C et La courbe B un contexte dtintersection contenant - les paramètres t et t des points d'intersection C B P et P sur C et B, - L'&alpha;-ordre &alpha;CB des brins de C et de B, autour des points d'intersection de C et de B. Le calcul des contextes d'intersection est réalisé par La méthode précédemment citée qui a été décrite dans la demande n0 déposée ce jour même par La demanderesse. On procède ensuite à une mise à jour des intersections dans la carte planaire. A chaque intersection trouvée entre la nouvelle courbe C à insérer et une courbe B de La face courante, on met à jour Les K-ordres de La carte autour des points d'intersection trouvés : 1) - soit L'ensemble (tC, PC, tB, pB, &alpha;CB)le contexte d'intersection obtenu par l'étape permettant de déterminer Les intersections, 2) - Si P n'est pas un point de B : B a) scinder L'arête e portant L'arc contenant t , b) scinder B en t et tous les arcs portés par e, B 3) - Si. P n'est pas un point de C, scinder C C en t , 4) - soit s Le sommet sur Lequel se projettent P et P , fusionner L'*-ordre du sommet s et B C L'*-ordre i CB La mise à jour de L'ordre s'effectue en chaque sommet d'intersection trouvé en insérant les brins d'intersection de C et de B s'ils n'existent pas déjà, auquel cas Les arcs partagent Les mêmes brins. Pour mettre à jour L'ordre des brins autour de ces sommets, on utilise La pente des cordes d'intersection comme cela est décrit dans La demande précédemment référencée. Tous Les brins d'intersection non-existants autour d'un sommet d'intersection sont insérés, y compris ceux de la nouvelle courbe C. Ceux-ci permettent ensuite d'obtenir la face F contenant L'arc a en prenant la face associée au contour attaché au i+1 brin &alpha;(b), où b est le premier brin de l'arc ai+1. On procède également Lors de cette sous-étape à un marquage de la face courante F et cela, de façon préférentielle, en réservant un champ dans le codage des faces de manière à renseigner ce champ des que l'on a déterminé des intersections entre l'arc de courbe paramétré (t , t ) et ta face. n On va maintenant décrire de manière plus explicite la sous-étape 50 d'insertion de l'arc de paramètres (ti, ti+1 ) dans une face F. Après avoir cherché toutes Les intersections entre La nouvelle courbe C et la face F et mis à jour Les &alpha;-ordres autour de ces intersections, l'on insère l'arc ai dans la carte. A cette étape du procédé, ai intersecte la carte au plus en ses points extrémités (Pi, Pi+1). extrémités Lors de l'insertion de L'arc a on crée - un sommet pour chaque brin de a si ce sommet n'existe pas déjà dans la carte ; dans le cas contraire l'arc de courbe avait un de ses points extrémités se projetant sur un sommet de la carte, - une arête si elle n'existe pas déjà dans La carte ; dans le cas contraire, l'arc a se projette sur une arête existante, ce qui signifie qu'il y a un recouvrement d'arc. Si L'arête portant L'arc a n'existe pas, on met à jour l'arbre des contours avec cette arête. Dans L'étape III de mise à jour, à La suite de L'insertion de l'arc (ti, ti+1), on procède à une sous-étape 51 de mise à jour de l'arbre d'inclusion des contours consistant dans ce cas à modifier L'arbre pour tenir compte de la-nouvelle arête. Pour#décrire La sous-étape 51, on définit la terminologie suivante : Arêtes pendantes/arêtes séparatrices Un sommet est un sommet pendant si et seulement si une et une seule arête est incidente à ce sommet. Une arête e est une arête pendante si et seulement Si ses deux brins b et (b) appartiennent au même contour. Sinon e est une arête séparatrice. On distingue 3 types d'arêtes pendantes suivant Le nombre de sommets pendants de cette arête : - une arête de connexion est une arête pendante dont aucun des sommets n'est pendant, - une arête terminale est une arête pendante dont un et un seul des sommets est pendant, - une arête isolée est une arête pendante dont les deux sommets sont pen#dants. Une arête dont les 2 sommets sont confondus est une boucLe . Une boucle dont Le sommet est de degré 2 est une boucle isolée Dans le procédé conforme à L'invention, on a répertorié huit cas possibles pour une arête dans une carte planaire. Ces huit cas sont mis dans une table en mémoi-re (figure 4). - Cas 1 - L'arête est une arête terminale dont les deux brins sont incidents à un contour interne, noté Ci, - Cas 2 - L'arête est une arête de connexion dont les deux brins sont incidents à un contour interne C , - Cas 3 - L'arête est une arête séparatrice dont les deux brins sont incidents à deux contours internes distincts C et C' , 1 1 - Cas 4 - l'arête est une arête siparitrice dont un brin est incident à un contour interne C et L'autre brin est incident à un contour externe C e - Cas 5 - L'arête est une arête isolée, - Cas 6 - L'arête est une arête terminale dont Les deux brins sont incidents à un contour externe C e - Cas 7 - L'arête est une arête de connexion dont Les deux brins sont incidents à un contour externe C e - Cas 8 - l'arête est une boucle isolée. En pratique la mise à jour de L'arbre des contours lors de l'insertion d'une arête consiste à effectuer : 1. la détermination du cas, ce qui fournit Le (ou les) contour(s) à mettre à jour dans L'arbre d'inclusion, 2. la mise à jour proprement dite de L'arbre d'inclusion des contours. Pour La détermination du cas de l'arête, on se reportera au schéma de la figure 3a (blocs 510519) : - L'arbre des contours est mis à jo#ur après L'insertion de chaque arête dans la carte. Ainsi, Les brins, les sommets de l'arête, et l'*-ordre autour de ces sommets sont à jour avant de procéder à la mise à jour de L'arbre des contours. - On peut donc consulter Les contours CO, C1 auxquels appartiennent Les brins voisins des brins de e (K(b) et#W(b) avec b=un brin de e). Le type (interne ou externe) de ces contours, associé au nombre des sommets pendants de L'arête à insérer e permet de déterminer le cas de cette arête. Le tableau 1 ci-dessous résume comment est déterminé le cas de l'arête à insérer e, b étant un brin de e. T A B L E A U 1 TABLEAU 1 Nombre de sommets anciens contours cas pendants (C0, C1) (bloc 511) 0 contours internes identiques 3 contours externes identiques 4 (bLoc 512) contours interne et externe 2 contours externes distincts 7 aucun 8 I contour interne 1 (bLoc 517 > contour externe 6 2 sans objet s Pour la mise à jour proprement dite Quand deux contours sont fusionnés en un, un contour est supprimé de l'arbre d'inclusion, Le contour conservé hérite des brins et des contours descendants du contour supprimé. Quand un contour est scindé en deux, un contour est créé, ce contour devient fils ou frère du contour scindé. Les contours descendants du contour scindé sont partagés entre les deux contours : on détermine leur ascendant par localisation (comme L'on a procédé pour l'origine P ) o Les cas 1 et 6 (arête terminale) ne donnent pas lieu à une modification de L'arbre des contours. - Pour le cas 2 : On procède à une fusion d'un contour interne et d'un externe en un contour interne ; les fils du contour externe deviennent les frères du contour interne ; l'externe est supprime de L'arbre des contours. - Pour le cas 3 : -On procède à une scission d'un contour interne en deux contours internes ; le contour interne créé devient frère du contour scindé- ; certains fils du contour scindé deviennent fils du contour créé. - Pour le cas 4 : on procède à une scission d'un contour externe en un contour externe et un interne ; Le contour interne créé devient fiLs du contour externe ; certains frères du contour externe deviennent fiLs du contour créé. - Pour le cas 5 : on procède à une création d'un contour externe ; son père interne est détermine par La Localisation de L'origine de La courbe insérée (résultat du processus de Localisation). - Pour le cas 7 : on procède à une fusion de deux contours externes en un contour externe ; un contour externe est supprimé de l'arbre des contours, les fils du contour supprimé deviennent fils du contour externe résultat de La fusion. - Pour le c : On procède à une création d'un contour externe et d'un contour interne. Le contour interne créé devient fils du contour externe. On détermine le père du contour externe par la Localisation du sommet de La boucle (résultat du processus de Localisation). Certains fils du père du contour externe deviennent fils du contour interne créé. On va maintenant décrire La mise à jour de l'arbre des contours dans Le cas de ta suppression d'une arête. Comme pour l'insertion, La mise à jour se compose de deux phases 1. détermination ~du cas de l'arête à supprimer, 2. mise à jour de L'arbre des contours en fonction du cas de 11 arête Pour La détermination du cas de l'arête on se reportera au schéma de la figure 3b (blocs 61û-619) -: Dans Le cas de La suppression d'arête, La mise à jour est réalisée avant La suppression de L'arête. On connais donc Le nombre de sommets pendants de l'arête (bloc 611), et le type (interne ou externe) des contours auxquels appartiennent Les brins de L'arête. Le tableau 2 ci-dessous résume comment est déterminé le cas de L'arête e à supprimer, b étant un brin de L'arête e. TABLEAU 2 Nombre de sommets contours incidents cas pendants (C0,C1) (bloc 611) 0 contours internes identiques 2 (bLoc 612) contours externes identiques 7 contours interne et externe 4 contours internes distincts j 3 contours interne et externe 8 1 contour interne 1 (bloc 617) contour externe 6 2 sans objet 5 Dans Le cas du bloc de comparaison 615 aboutissant au cas 4, au moins un des contours C ou C contient pLus d'un brin. o 1 Dans Le cas du bloc de comparaison 615 aboutissant au cas 8, Les deux contours C et C ne o 1 contiennent qu'un seul brin. Pour la mise à jour proprement dite Les cas t et 6 (arête terminale) ne modifient pas L'arbre des contours. - Pour le c 2 : On procède à une scission d'un contour interne en un contour interne et un contour externe ; L'externe créé sera fils de l'interne ; certains contours qui étaient frères du contour interne deviennent fils du contour externe créé ; Pour le cas 3 : On procède à une fusion de deux contours internes en un contour interne et on fusionne les fils externes de chacun des deux contours ; - Pour le cas 4 : On procède à une fusion d'un contour interne et d'un externe en un contour externe ; les contours fils du contour interne deviennent frères du contour externe; Pour Le cas 5 On procède à une suppression d'un contour externe ; - Pour le cas 7 : On procède à une scission d'un contour externe en deux contours externes ; certains fils du contour externe scindé deviennent fils du contour créé. - Pour le cas 8 : On procède à La suppression d'un contour externe et d'un contour interne. Les contours fils du contour interne supprimé deviennent fils du père du contour externe supprimé. Conformément à l'invention, lors d'une operation de suppression, les éléments de ta structure de données géométrique ne sont jamais supprimés, mais ils sont marqués gommés. Par contre, les éLéments de la structure de données topologique : sommets, arêtes et contours peuvent être supprimés. L'arbre des contours est mis å jour. Le procédé permet de gommer les objets suivants : une arête, une courbe, une composante connexe, les arêtes pendantes d'un contour, d'une face, d'une composante ou de la carte toute entière. La phase de gommage comporte les étapes V et VI de La figure 2b. L'objet à gommer est tout d'abord Localisé dans la carte (V) par la localisation de toutes ses arêtes e (blocs 40, 41). On procède ensuite à une mise à jour (VI) consistant à effectuer un gommage proprement dit et à une mise à jour de l'arbre des contours (bloc 60). Gommer une courbe signifie marquer "gomme" les arcs de cette courbe, et enlever ces arcs des arêtes qui les portent. Si des arêtes ne portent plus d'arcs, elles sont supprimées : leurs brins sont ôtés de I' #-ordre des sommets autour desquels ils étaient incidents, et leurs sommets sont supprimés s'ils n'ont plus de brins incidents. Ainsi, gommer une composante signifie gommer toutes les arêtes de cette composante. Afin d'éviter toute création non voulue de composante connexe, on ne va pas procéder au gommage arête par arête de Ladite composante. La demanderesse a remarqué que seules Les arêtes de connexion (cas 2 et 7) produisent, quand on Les gomme, une deuxième composante (par scission de La première). Par contre tous Les autres cas n'en produisent pas. En particulier Les arêtes de cas 4. Et une composante qui ne contient pas d'arêtes de cas 4 ou n'est pas réduite à une arête de cas 8 est un contour externe pendant (contour constitué d'une arête de cas 5 ou d'arêtes de cas 6 et 7). Une telle composante peut être gommée en gommant ses arêtes pendantes. On procède alors aux étapes suivantes : 1. gommage de toutes les arêtes de cas 4 (si elles existent). 2. gommage de toutes les arêtes pendantes de La composante (si elles existent). 3. gommer l'arête de cas 8 (si elle existe). Pour l'étape 1 : on parcourt le contour externe de la composante, en effet toutes Les arêtes de cas 4 (si elles existent) se trouvent sur ce contour. Dans le cas où il nty a pas d'arêtes de cas 4 à supprimer, cela signifie que La composante est un contour externe pendant ou est réduite à une arête de cas 8. Pour L'étape 2 : si la composante n'est pas une arête de cas 8, il suffit alors de supprimer Les arêtes pendantes de cette composante. Pour L'étape 3 : supprimer l'arête de cas 8. Ainsi, pour réaliser le gommage des arêtes pendantes d'un contour, d'une face, d'une composante ou d'une carte, on procède avantageusement à un gommage des arêtes pendantes en supprimant de façon récursive les feuilles des arborescences pendantes. Pour cela, on parcourt l'objet à nettoyer en cherchant une arête dont au moins un sommet est pendant (arête terminale ou isolée). Si après suppression d'une arête terminate, Le sommet non pendant de L'arête devient pendant, alors l'arête incidente en ce sommet est devenue terminale. On réitère ainsi en suivant tes arêtes terminales à travers Les sommets pendants. De façon pratique, on met en oeuvre les étapes suivantes : A. chercher une arête e dont au moins un sommet est pendant, (s'iL n'en existe pas it nty a plus d'arête pendante), B. si e existe : (a) conserver le sommet s non pendant de e, (b) supprimer l'arête e, (c) si S est devenu pendant après L'étape B(b), réitérer en B(a) avec une arête e = l'arête incidente en s, (d) réitérer en A. Le procédé conforme à L'invention peut être mis en oeuvre dans tout ordinateur programmé à cet effet, le programme étant à La portée de L'homme de La technique à partir de l'enseignement apporté par La présente demande. Ce procédé est de manière avantageuse mis en oeuvre par La demanderesse sur une station de travail. REVENDICATIONS 1. Procédé d'insertion et/ou de gommage de courbes et/ou d'éléments de courbes dans un dessin réalisé par ordinateur pour L'aide au graphisme dans La CAO ou DAO, ledit ordinateur comportant une mémoire dans laquelle est stockée une structure de données caractérisé en ce que la structure décrit les données du dessin, dans lequel on réalise des insertions et/ou des gommages, sous forme d'une carte planaire à laquel Le on associe un arbre d'inclusion des contours, ladite carte comportant un ensemble de faces (F), chacune étant délimitée par un ou plusieur contour(s) porté(s) par des arêtes de courbes du dessin, Ledit procédé étant caractérisé en outre en ce qu'il comporte les étapes suivantes 1) Saisir l'élément à gommer ou à insérer au moyen d'un périphérique d'entrée et éventuellement afficher cet élément sur l'écran de L'ordinateur. a) - au préaLable : - associer à La courbe à Insérer les paramètres t et o t , t correspondant à l'origine P de La courbe, t n o o n à L'autre extré#ité P ; n - localiser La face de la carte dans laquelle se trouve L'origine de la courbe à insérer ayant pour paramètre t0 ; - affecter à un paramètre ti La va Leur du paramètre t o b) - puis de façon itérative - déterminer les intersections entre ta courbe de paramètre (t1 , tn) à insérer et toutes les courbes portées par les arêtes des contours de La face ;; - insérer les points d'intersections de paramètre t sur l'arc (t1, tn) (t1, ; - affecter Le paramètre ti@ 1 au point d'intersection tj suivant le point de paramètre ti ; - insérer dans la face considérée en l'enregistrant en mémoire dans la structure de données l'arc ayant pour paramètre (ti, tri+1), 2) Lecture en mémoire de L'arc obtenu en vue d'un affichage du dessin en cours. 2. Procédé selon la revendication 1, caractérisé en ce que la localisation de la face dans laquelle se trouve L'origine de La courbe à insérer et ayant pour paramètre t comporte les étapes suivantes o - insérer fictivement une droite D ayant pour origine o P L'origine de La courbe à insérer, et pour o extrémité un point P connu situé dans une première e face dite face infinie ; - déterminer Les intersections entre La droite D et o toutes les courbes ; a) - dans le cas où des intersections ont été déterminées - calculer la distance j entre ces intersections et le point origine P o - déterminer L'arête e pour laquelle cette distance b est minimum, - enregistrer L'origine P dans la face à laquelle o appartient le brin de L'arête e qui voit P o b) - dans le cas où aucune intersection n'a été déterminée : - enregistrer l'origine P0 dans La première face. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que L'étape d'insertion d'un arc a dans ta carte, L'arc a étant porté par une arête e et par deux brins déterminés de e consiste à - créer un sommet S, S' pour chaque brin de L'arête e en enregistrant les sommets S et S' dans la structure de données dans le cas où ces sommets ne sont pas déjà dans la carte ; - créer l'arête e en l'enregistrant dans la structure de données comportant l'arc ai et un des deux brins dans le cas où cette arête n'existe pas déjà dans la carte. 4, Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que L'étape de détermination des intersections entre la courbe à insérer et une face. donnée comporte en outre une étape de marquage de cette face. 5. Procédé selon ta revendication 4, caractérisé en ce que L'étape de marquage de la face consiste à réserver un champ dans le codage d'une face en mémoire susceptible d'être renseigné des que L'on procède à La détermination des intersections entre L'arc paramétré (t1, tn) et la face. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'après L'insertion d'un arc (ti, ti+1) par enregistrement dans la structure de données, on procède à une comparaison du paramètre ti+1 au paramètre tn , on passe à la face suivante lorsque ces deux paramètres ne se correspondent pas, l'insertion étant terminée dans le cas contraire. 7. Procédé selon l'une quetconque des revendications 1 à 6, caractérisé en ce qu'il comporte une étape de comparaison de la face en cours avec les faces déjà traitées pour insérer directement L'arc de paramètres (t1, t i+1) dans cette face dans le cas où La face a déjà été traitée et passer dans une nouvelle face dans le cas contraire. 8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce qu'il comporte en outre une étape de mise à jour de l'arbre d'inclusion des contours consistant à insérer ou à supprimer une arête. 9. Procédé selon la revendication 8, caractérisé en ce que L'étape de mise à jour de L'arbre d'inclusion des contours dans le cas de l'insertion consiste, pour une arête e portée par L'arc ai de paramètres (ti, ti+1), à : a) - au préalabLe : - répertorier sous forme d'une table en mémoire un ensemble de cas Possibles pour une arête dans une carte planaire ; b) - puis après l'insertion d'un arc a1 : - déterminer par comparaison avec les différents cas possibles le cas de l'arête e portée par L'arc ai ; c) - mettre à jour l'arbre des contours en fonction du cas précédemment déterminé en effectuant une - suppression d'un contour lorsque deux contours sont fusionnés, ou - création d'un nouveau contour, ce contour devenant fils ou frère du contour scinde dans l'arbre des contours. 10. Procédé selon la revendication 8, caractérisé en ce que L'étape de mise à jour de L'arbre d'inclusion des contours dans le cas d'une suppression, consiste, pour une arête e correspondant à L'arc de paramètre ti, ti+ 1 inséré, à : a) - au préalable : - répertorier sous forme d'une table en mémoire un ensemble de cas possibles pour une arête dans une carte planaire ; b) - pour L'arête e à supprimer : - répertorier le nombre de sommets pendants de L'arête, le type de contour interne ou externe auquel appartiennent les brins de L'arête, - déterminer par comparaison avec Les différents cas Possibles de la table te cas de cette arête ; c) - puis mettre å jour L'arbre des contours en fonction du cas déterminé en effectuant soit : - une suppression ; - une scission ; - aucune modification. 11. Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce qu'iL comporte une étape de gommage d'une courbe et/ou d'un élément de courbe consistant à : 1) localiser l'éLément à gommer, 2) gommer cet élément : - en effectuant une suppression dans La structure de données des sommets, arêtes et contours associés à la courbe, - en conservant en mémoire dans La structure de données les arcs et Les points définissant la courbe, - en renseignant un champ prévu dans Les données reLatives aux arcs et aux points signifiant que les éléments correspondant aux arcs et aux points sont effacés, 3) mettre à jour L'arbre d'inclusion des contours. 12. Procédé seLon La revendication 11, caractérise en ce que L'étape de gommage des arêtes pendantes, d'un contour, d'une face, d'une composante ou d'une carte consiste à : A) chercher une arête t dont au moins un sommet est pendant ; B) Si l'arête e existe : (a) conserver le sommet s non pendant de e, (b) supprimer l'arête e, (c) si s est devenu un sommet pendant après l'étape B(b), réitérer en B(a) avec une arête e incidente en s, (d) réitérer en A.