Synthese d'image: Algorithmes elementaires 9782040164270, 204-016427-8 [PDF]

Zitiervorschau

Monographies de I’AFCET-Informatique Un regard de professionnels

PREFACE

. D. Le Verrand, Le langage ADA, manuel d’&wluation, Dunod, 1982. Bnluating ADA, North Oxford Academic Publishing Company, 1985. . F. André, D. Herman et J.P. V~~US, Synchronisation des programmes partiètes, Dunod, 1983. Synchronization of parallel programs, North Oxford Academic Publishing Company, 1985. 0 M. Raynal, Algorithmique du parallélisme : le probléme de l’exclusion mutuelle, Dunod, 1984. Algorithms for mutual exclusion, North Oxford Academic Company, 1985. l

C. Chrkment, J. k Crampes et G. Zurfluh, Dunod, 1985.

Bases d’informations

0 G. Hégron, Synthèse d’image : algorithmes &mentaires,

g&kaüsees,

Dunod, 1985.

Ouvrage publie avec le ccmcours des minist&es de l%ducation nationale (direction de la recherche) et de la recherche et de la technologie. (MIDIST) Programme mobihsateur : «promotion du français langue scientifique et diffusion de la culture scientifique et technique. »

@ BORDAS, PARIS 1985 ISBN 204-016427-8

A rheure où tout un chacun peut admirer les images produites par ordinateur. en particulier pour leur degré de réalisme et de finition, on peut se poser la question de savoir s’il St ré&zment utile de cm~s~rer un ouvrage complet à l’étude des techmques élémentaires pour la synthése d’image. Et pourtant, I’explosion de la micro - mformatique conduit des milliers de personnes à recréer sur leur ordinateur personnel des algorithmes de base. Et pourtant. les ingénieurs chargés de concevoir et réaliser les génératet!rs $imageS synthétiques souhaitent connaître les meilleurs algorithmes pour pouvoir les mtegrer dans leur machine. Et c’est là tout le paradoxe : des images extraordinaires sont produites quotidiennement, & partir d‘algorithmes qui ne sont pas forcément maîtrisés. ou tellement nombreux que l’on ne sait plus lequel choisir et pourquoi. Le mérite de cet ouvrage est de passer en revue de manière systématique un certain nombre d’algorithmes plus ou moins célèbreS, en mettant en valeur pour chacun ses avantages et ses inconvénients Ce travail méticuleux et très austère a comme premier r&ultat de rassembler en un même endroit des techniques habituellement éparpillées dans des publications qui ne sont pas toujours facilement accessibles. Le deuxième mérite est de fournir une bibliothèque d’outils raisonnés, dans trois domaines à la base de la synthke d’image (même au delà des algorithmes élémentaires), g savoir la génération de courbes, le remplissage de taches et les traitements de nature géométrique. Ainsi, le lecteur trouvera rassemblés les fondements de tout système de synthk d’image. Enfin, par delà la diversité des algorithmes, l’auteur a su faire converger les différentes idées, en traitant plus particulièiement de deux techniques, qui relient entre eux quelques algorithmes, et peuvent donc servir de base systématique à un logiciel : les générations de courbes avec le mécanisme de Bresenham. et les traitements variés à partir du suivi de Contour. Cet aspects synthétique à partir de méthodes a priori très diverses constitue un des apports les plus importants de cet ouvrage. Je crois fermement que ce livre rendra beaucoup de services et que, par suite, il aura bem~oup dïnfluence sur la conception des logiciels graphiques. Je lui souhaite longue vie. Michel Lucas Professeur & l’Université de Nantes

SOMMAIRE

pREF*CE.

...........................................................

SOMM*IRE

.........................................................

INTRODUCTION

....................................................

I

, - GENERALITES SUR LES TRAITEMENTS ELEMENTAIRES EN SYNTHESE D'IMAGE ........................................ 1.1. Algorithmes et traitements éMmentaires .............................. 1.2. LÏnfortnation image ............................................. I .3. Codilkation de lïmage. ........................................... 1.4. Les traitements en synihése dïmage ................................. 2 - GENERATION

DE COURBES SUR UNE SURFACE ................................................ *.,.In,rod”ctio” .................................................... 2.2. Classification générale ............................................ 2.2.1. Les méthodes numériques ................................... 2.2.2. Les méthodes incrémentales. ................................. ............................................. 2.2.3.Conclusion., 2.3. Les méthodes incrémentales. ....................................... 2.3.1.Introduction .............................................. 2.3.2. Les méthodes incrémentales générales. ......................... ......................................... 2.3.2.1. Généralités 2.3.2.2.Laméthode&IORDANetal........................... 2.3.2.3.Conclusion ......................................... 2.3.3. Les méthodes incrémentales spécifiques ........................ ....................................... 2.3.3.1.Généralitb.. 2.3.3.2. Généralisation du principe de BRESENHAM .............. 2.3.3.3.Conclusion ......................................... 2.4 Génération des segments de droite, .................................. 2.4.1. L’algorithme de LUCAS. .................................... .............................. 2.4.2. Valgorithme de BRESENHAM. 2.4.3. Gén&tion d’un ensemble de segments de droite. ................. 2.4.3.1. Compression. ....................................... 2.4.3.2.Répétition. .........................................

APOINTILLAGE

II II 12 12 13 13 14 14 14 14 15 18 18 18 18 21 21 21 22 23 24 24

2.5.Génératiandsscerc,es

............................................

2.5.1. L’algorithme de BRESENHAM............................... 2.5.2.Gé”ératio”desarcsdecercle.. ............................... 2.5.2.1.Leprohlèrne ........................................ 2.5.2.2.L’alg?rithmedeBRESENHAM ......................... 2.6. Génération des ellipses ........................................... 2.6.1. Ellipses simpls(aJgorithme de ROY). .......................... 2.6.2. Ellipses quelconques (algorithme de ROY). ...................... 2.7. Génération des paraboles. ......................................... 2.7.l.ArcsdepambolesimpleklgorithmedeROY). ................... 2.7.2.Arcsdepw&,lequelco”que ................................. 2.8. Génération des hyperboles ......................................... 2.8.1. Généralisation de I’algorithme de BRESENHAM aux hyperboles « simples » .................................................... 2.8.2.Hyperholesavecrotîfio”. ................................... 2.9. Am~liomtion du dessin au trait ..................................... 2.9.1.In~oduction .............................................. 2.9.2. M6thode BRESENHAM .................................... 2.9.2.1.Leprincipe ......................................... 2.9.2.2.Améliorationdutracédessegmenbdedroite.. ............ 2.9.3.Améliorationdutracédesmniques ............................ 2.9.3.1.LaméthodedeROY.. ................................ 2.9.3.2. Amélioration du tracé des ellipses ....................... 2.9.3.3. Amélioration du tracé des arcs de parabole ................ 2.9.4. Simulation des grisés ....................................... 2.9.4.1. Introduction. ....................................... 2.9.4.2. Utilisation des cellules prédéfinies ....................... 2.10.Conclusion .................................................... 3 - REMPLISSAGE DE TACHES. .................................... 3.1.l”trodudion .................................................... 3.2. Le coloriage ..................................................... 3.2.l.Leprincipedebase. ........................................ 3.2.2.L’algorithmedeSMITH.. ................................ .. 3.2.3.L’algorithmedePAVLIDlS. ................................. 3.2.4. Conclusion. .............................................. 3.3.Leremplissagedetaches .......................................... 3.3.l.Introduction.. ............................................. 3.3.2.Lebalayageligneparligne.. ................................. 3.3.2.1.l”troduction ........................................ 3.3.2.2. Le remplissage de taches polygonales. .................... 3.3.2.3. Le remplissage de taches “on-polygonales ................. 3.3.2.4.Conclusion ......................................... 3.3.3.Lesuividecontour ....................... ~~ ................ 3.3.3.1.Leprincipe ......................................... 3.3.3.2. Le remplissage de taches polygonales. .................... 3.3.3.3. Le remplissage d’un ensemble de taches polygonales. ........ 3.3.3.4. Le remplissage de taches “on-polygonales. ................ 3.3.3.5. Une application : écriture d’un texte dans une tache polygonale quelconque ......................................... 3.3.4.Conclusion ...............................................

25 25 27 27 29 31 31 34 37 37 39 39 39 46 47 47 48 48 49 51 51 52 57 60 60 60 64 67 67 68 68 70 72 76 77 77 78 78 79 83 85 85 85 86 93 94 96 107

3.4. Décomposition des taches polygoraks en él&nents simples ............... 3.4.1.Introduction .............................................. 3.4.2. Nouvel algorithme de décomposition. .......................... .................. 3.4.2.l.LaméthodedeBENTLEYetOT-TMAN 3.4.2.2. Utilisation de la méthode de BENTLEY et OTTMAN ........ ............................................. 3.4.3.Conclusion.. 3.5.Lehachuragedetachespolygo”ales ................................. 3.5.1.Lehachurageverticalouhorizontal.. .......................... 3.5.2. Hachurage oblique de co”tours polygonaux ..................... 3.5.2.1.Introductio” ........................................ 3.5.2.2. Le hachurage oblique par (< suivi de contour 4 ............. 3,6,Conclusion................................................~ ....

4 - ALGORITHMES DE~DECOUPAGE ET TRAITEMENTS DE NATURE GEOMETRIQUE

...................

4.1.Introdüctio”..................................................: 4.2. Classification des problèmes de découpage ............................ .................... 4.3.Comparaisond’unpointetd’unco”tourpolygonal.. 4.3.1.Inuoduction .............................................. 4.3.2. Comparaison point - contour convexe ......................... 4.3.2.1.I”troduction ........................................ ................................ 4.3.2.2.MélhodedeSHAMOS 4.3.3. Comparaison point- contour non-convexe. ..................... ...................................... 4.3.3.1.Introd”ction.. 4.3.3.2.Mélhodedusuividecontour.. ......................... 4.3.4.Conclusion ...............................................

108 108 109 109 IlO 113 113 113 114 114 1 l4

122

125

125 126 132 132 132 132 132 135 135 135 137 137 4.4. Découpage d’un segment de droite par un contour polygonal. ............. 4.4.l.Introduction .............................................. 137 4.4.2. Découpage par rapport à une fenéue rectangulaire ................ 137 ........................................ 4.4.2.l.InUod”c,ion 137 .............. 4.4.2.2. L’algorithme de SUTHERLAND-SPROULL 139 ........................... 4.4.2.3.L’algo~thmedePA”L,D,S., 141 4.4.3. Découpage pu rapport a un C~“~O”T convexe .................... 143 4.4.3.1. lntrcduction ........................................ 143 4.4.3.2. Algorithme de PAVLIDIS ............................. 143 4.4.4. Découpage par rapport à un contou, quelconque ................. 147 ........................................ 4.4.4.1.l”troduction 147 4.4.4.2. L’algorithme de suivi de contour ........................ 147 4.4.5.Conclusion ............................................... 150 4.5. Découpage d‘un polygone par une fenêtre polygonale ................... 15 I ............................................ 4.5.1.Introductian.. 151 4.5.2. L‘algorithme de SUTHERLAND et HODGMAN ................. i 51 ................... 4.5.2.l.D&xwpaged’unpolygoneparunedroik 151 4.5.2.2. Généralisation du decoupage d‘un polygone par une fenêtre. .. 153 4.5.3. t”tersection de deux polygones co”vexes. ....................... 153 4.5.3.l.LaméthodedeSHAMOS.. ............................ 153 ...................... 4.5.3.2.LamêthodedeO’ROURKEetal... 163 4.5.3.3.Intersection.de deux segments de droite. .................. 166 4.5.3.4.Ccmclusion ......................................... 168

4.5.4.

Intersection de deux polygones 4.5.4.l.Uneapprochep~culiére

454.2. L’algorithme 4.5.5.Co”clusia”.

................... non-convexes. .............................

de ATHERTON

et WEILER

................

..............................................

4.6. Découpage d’une tache pu une fen&tre polygonale. ..................... 4.6.1.I”uod”ctio” 4.62. Découpage

..............................................

4.6.4.

..............................................

explicite ........................................ 4.6.3. Découpage implicite ........................................ Conclusion.

4.7.Découpaged’unetacheparuneautre 4.7.,.,ntro*uction

................................

..............................................

...................... 4,7,2,Tachedéfrce%ux par bandes, et pour chaqu' bande d'engendrer chaque courbe point par point puis de l'afficher. Nous ~OU% %onmw intéressés à deux modes de génération image sur des surfaces à pointillage :

des terminaux l'affichage

r

. Codage de 1% structur% : - primitives : la tache est décrite cormne la juxtaposition de primitives globales (barres, courbes...) sur lesquelles on peut opérer certaines opérations (inclinaisons, symétries,...). - sq"elettes : 1% tache est codée par son squelette et par une fonction qui en définit l'épaisseur en tout point.

d'une

avec l'apparition récurrent) : c'est

km engendrer un% tache %ur l'écran, NIUS aborderons oPd=%tion% suivantes (vair figure 1.6.):

%ucce%%ivem%nt

- inscription du contour d'une tache point à point : c'est général de la génération des courbes, - génération d'une tache monochrome (remplissage proprement loriage) ou hachurée (hachura&. Comme nous le remarquons sur la figure 1.6. nous pouvons certaines opérations en passant d’un espace à l'autre (flèches lés).

le prab dit

et

réaliser en pain

:. ::. .. .. . . . . . ::::::Y ensemble de points .w::::. :::* f --1 t co*uriage e--. .* : .* L*** CO”lOYïdéfini

l.

0.. l ..*..’

puint i point

l **

Figure

1.6.:

Mais la ensemble de entre elles res de nature la structure de points ou

Codifications

d'une

tache

et traitements.

création d'une image résulte également de la combinaison d' taches. NOUS nous intéresserons alors au découpage des Lach et de leur contour. Nous verrons que les problèmes élémenta géométrique qui en résultent, sont très différents suivan de la tache sur laquelle nous raisonnons (contour, ensembl d'intervalles horizontaux, etc...).

Parmi l'ensemble des procédés employés pour d'entre eux a retenu notre attention. Il permet traitements abordés ici à partir d'une description

créer une image, l'un de résoudre la plupart structurée du ccmt~u

d'une tache dans l’espace utilisateur et sans avoir besoin de nous ramener 2 une description de la rache,dans l'espace écran : il s'agir du principe &-,éral de la techuque du SULYI de contour. Nous n'explorerons pas les problèmes d'acquisition, ni les autres techniques (analyse, reconnaissance) qui sont plutôt du ressort de ce que ly22q-;

figure

Les deux 2.4.)

candidats

possibles

- soit

le point

(r+l,q+l)

- soit

le point

(r+l,q)

Le point

P2 peut

vérifier

pour

l'étape

correspondant correspondant l'un

suivante au mouvement

au mouvement

des 4 cas de figures

a) 4 + ; > y2 à q+1 mouvement b) q + 1 > y2 > q+ ; c) q++>y*aq d) q > y2 a q- +

diagonal

seront

donc

: (voir

diagonal

particulièrement

intéressants,

celui

de

; 2.4.1

axial. suivants

Deux algorithmes s'avèrent LUCAS et celui de BRESENHAM.

:

- L'ALGGJZITHME DE LUCAS

Pour engendrer un segment de droite, LUCAS(CLUCAS 77>) se ramène au Premier actant. Comme nous nous déplacons systématiquement à chaque pas suivant l'axe des X, nous évaluons l'erreur cotise sur les ordonnées si on ne modifie pas y. A chaque étape, l'erreur ainsi commise se cumule. POU~ la minimiser, il suffit de modifier y (en ajoutant 1) lorsque cette erreur atteindra ou dépassera l'unité.

23

Sous sa forme générale, Génétin

l'algorithme

s'écrit

:

SEGMENT-1 [xd, yd> x6, y6 : uU.bd zti -tiZiti

--D6bu.f CO m&thode de LUCAS CO uUicn : AX,AY, XINCR,Y P NCR.CUMUL,X,Y;

x 2’ Xd, y := yd’ a&chen

p&U

Ix,yl;

XINCR := &i xd < x6 a&h4

+l bhx~

YZNC := &

-1;

&

yd < y6 a.%~& +l A.&on -1; -:= nbs(xd-x6), Ab’ := abAf‘,d-Y6);

AX > AY CO on deaa&x Le matium de po.int.4 * CUïaoL := X/2; Pola I := I ‘U6 u’à AX @ x :=x .!-+h. + CUMUL := CUMUL’+ AY; 6.i CUMUL a AK - MWA CUMUL := CUMUL - AX; Y := Y + YINCR;

yd c yA e

+1 duron

@

VX w POUn 1 := I jtiqu’à Ai s20 - doti Y := Y+YINC; -s := S+~UXYl; &m7n s := .s+lDYZl; i%iINC

a6&icheA point

- L’ALGORITHME

VE BRESENHAM

2.4.3

Pour la génération des segments de droite, BRESENHAM () cherche conme pour son algorithme de génératio" des segments de droite, & engendrer les points les plus proches possibles du cercle initial en n'utilisant que des valeurs entières, l'addition et la soustraction. qu'au

lieu

caractérisé

axial.

fime - - - __CM __- : segment diegonal, i.e. AX=AY 0" a alors une repétition

est

Soit

NI-partie

L'analyse point

se fait dans le ler quadrant à partir du point CO,@ jusdu cercle étant ramené à l'origine. (R,O) ; le centre

en A partir d'un point donné, trois mouvements élémentaires peuvent être en évaluant de manière envisagés m,, m , m : le r~~uvement est déterminé récurrente la 'diskce minimale qui existe entre le cercle idéal ?F celui passant par les trois points candidats (voir figure 2.6.).

27

26

ration

des mouvements

a) Sens de parcours Figure

2.6.:

L'algorithme et de rayon R.

Positions au cercle

relatives initial

de BRESENMM

y:=R+KMI := M3: M2 := MI+I,

qui

des candidats possibles (méthode de BRESEWAM). suit,

calcule

le cercle

par

rapport

de centre

Figure

1.

Exemple

des mouvements

élémen-

Conventions

génération

de cercles

par

1; méthode

de BRESENHAM.

& a := a-Y; & 320 &&A Aimm

- GENERATION DES ARCS DE CERCLES

. Le problème est de dessiner de rayon R où l'arc est déterminé Y := Y-2, n:=a + Y; MOVE 0 -&h5~c:=+I ziIiizi xim := -1 si Iiy>o - &hA Ycnc := l 1 6uzon Yinc := -1 x :;; Y := w A&&heh point IX, Y, I~X)

51

Suivant CilA ti -TZTAX>= 7Jhm D[b -4

:= a Poti 1 := I e I judq(r’a ïmzti x := xixtic 0 := V+VELTAY

&

VELTAX &

debut si

Z’V-VELTAXVELTAX D&b& 0 := 0 Pow 1 := 7 t-0 1 jll6qrant

*/

!?ET?&

-1

TRACER-@lAVRANT

Y.iYlc := -1 1' 4s quadMti TRACER-@lAL'&WT

DYT 6"e

Y := YIYinC

V := D-S-AZ

*/

si D0 &%A ZZ%

? XINC := ii XZNC := -1

-.

DYXI aLoILA YlEiC := +I dinon YZNC := -1

x := XIJ Y := Y0 A&$ischeh

point

:= i’+YINC u := v+vsx Si lJysf (voir figure 3.29.).

et sf(fin)

::,

117

k2

Sf2 YSf,>

YSf2

x

i Figure

3.29.:

cent sant

Orientation

des arêtes.

Dans l’algorithme de remplissage par stivi de contour, nous nous déplaçons sur le contour suivant la direction verticale. Ici, nous suivons le contour dans une direction perpendiculaire aux lignes de hachurage. Le calcul des intersections rient compte de la cohérence qui existe entre deux lignes de hachurage consécutives. Pour ce faire, nous calculons pour chaque arête l’accroissement en X et en Y existant entre les lignes. Le premier point d’intersection est obtenu en réalisant le calcul d’intersection entre deux droites, la ligne de hachurage et la droite support de 1’ZVSte. 3.~ MiAe-en-o~euvhe On se servira des structures

de données

suivantes

:

- La liste des so-ts définie par : - s(*) : tableau servant pour la numérotation des sommets : coordonnées des sommets du contour - x(*),y(*) : intersections des droites passant par les sonmets - Ys(*) l’axe oy (droites parallèles aux lignes de hachurage). - La liste des arêtes orientées - sd(*) : sommet début (donné - sf(*) : sommet fin - a(*) : accroissement en x - b(*) : accroissement en y : accroissement en x - dax(*) : accroissement en y - day(*) sant

- Liste des arêtes qui par les sommets (ordre

commencent décroissant

: par

entre entre

le numéro

les les

du sanrmet)

lignes lignes

sur chaque des ys)

avec

ligne

de hachurage de hachurage de hachurage

pas-

qui counnen- S(*) : S(i) pointe sur la liste des arêtes k,,k2,..., respectent l’or “a re décroisau sonmet i (les sommets i=1,2 ,...nbsom des ys; correspondant ). - La liste des arêtes coupant la ligne - ‘Ai(*) : liste des arêtes - interx(*), intery : coordonnées arête *wc la ligne i.

de hachurage des intersections

i : de chaque

Comme pour l’algorithme de remplissage, le contour de la tache est constitué d’un ensemble de polygones. NOUS disposons également de 1’Ecart qui existe entre deux lignes de hachurage consécutives et de leur Pente. L’algorithme

a la

forme

HACHURAGE OBLLQUE lN,TI*ll Utbut Pnémtement:

générale

suivante

:

&:=i

. Yd:=T[i+ll; Xd:=T[i) ,&=i+2 ; io:=T[il; w[Nbal:=Xd ; y[Nbsl:=Yd; Ysd:=Yd-Pente'Xd ; Nsd:=Nbs; d[Nbdl:=Nbd ; YblNbd):=Ysd; Nbd:=Nbb+l; F.Ln:=&uw;

q fi

o#NlL

&XJ:=Xo,

Y6:=T[i+11; x(Nbhl:=Xd ; y[Nbs):=Yd; ~~&=Y6-?ente'X6 ; Ndd:=Nbb; 6(Nb&]:=Nb6 ; Y&tNb6l:=Yb& Nbs:=Nb&+l; *x6:=T[*ol ; Y(:=JTlh+ll ; i:=i+l; Y66:=Y6[Nbul, Nh6:=Nbm FuZ:=v~ai CO demi&te ah& du poLygone L'ahète [[%LV&[X6,Y611 &

CO .ïkLfm - Ybd>Y66 atoxb Nba:=Nbatl; -ddINbal:=Nbd, 66[Nbal:=Ns6; Ax:=Xd-Xd ; Ay:=Yd-Yd; a[Nbal:=Aw ; b[Nbal:=Ay; &x[Nbal:=[ûy*Axll[Ay+Petie*Axl; duy~Nbal:=Pente*d.axlNbal-Dy; 6utOyI Ai Ydd2. nbam. nba ah nbam est le nombre moyen d'arêtes coupant une ligne de hachurage, mais cette inégalité demande à être vérifiée dans la pratique).

3.6. Conclusion De manière générale, les performances et les ressources requises par les algorithmes de remplissage ou de hachurage de taches dépendent de la complexité des contourS. Mais le critère primordial demeure leur Sdapration à la synthèse d'image dans un cadre d'application donné : faire

intensité lumineuse taches polygonales interactivité, mémoire disponible.

variable ou non,

Pour chacune des classes les remarques générales

ou constante,

d'algorithmes qui suivent.

de remplissage,

. Les algorithmes de coloriage Sont avant interactive (détermination du point intérieur,

nouS pouvons

tout utilisables de manière convexité de la tache).

. La méthode de remplissage par codage du contour nécessite la plupart du temps une mémoire d'image supplémentaire et s'adapte mal à un ensemble de taches qui se chevauchent. Cependant, sa généralisation à des contours

simple.

. Parmi ces diverses classes d'algorithmes, une méthode générale SS de la technique du suivi de contour. En effet, raisondégage : il s'agit ,,ant à partir d'une représentation structurée du contour, elle permet non seulement de réaliser le remplissage d'une tache ou d'un ensemble de taches polygonales ou non, mais encore elle s'adapte facilement Su hachurage, au découpage de taches polygonales en éléments simples et au parallélisme (voir ).

Co%tv&-' entr*

- ConUbn

La mise en oeuvre oblique sans rotation

e8t

s :ii

le chapitre suivant'que à certains problèmes

les principes de découpage

du Suivi de et de nature

Chapitre 4

Algorithmes de découpage et traitements de nature géométrique 4.1. Introduction Il est extrêmement fréquent que, lors de la mise en page ou d’une image, on ait besoin de ne représenter sur l’écran de la scène considérée. Lorsqu’on travaille dans le plan, le sique consiste à utiliser une fenêtre, espace rectangulaire lèles aux axe* (figure 4.1).

Figure

4.1.:

Découpage

d’une

scène

d’un dessin qu’une partie problème clasà bords paral-

par une fenêtre.

Cependant, on peut avoir besoin de faire des calculs dans le cas où l’on ne dispose plus de la facilité donnée par le parallélisme aux axes. Le problème revient alors à découper une sLène par une fenêtre constituée par un polygone convexe ou non, le nombre de ses côtds étant quelconque. De façon plus générale, nous sommes parfois amenés à comparer deux polygones quelconques et à déterminer tous les polygones résultant de leur intersection (du découpage de l’un par rapport à l’autre). Nous utilisons ce découpage en particulier dans l’algorithme d’élimination des parties cachées d’une scène tridimensionnelle.de ATHERTON et WRILER CATHERTEONmILER 77>, ou B partir de l’ensemble des faces polygonales qui la composent, nous voulons obtenir un ordre total sur un ensemble de facettes. Ce découpage peut également s’avérer utile pour la manipulation d’image. Ainsi, et suivant

selon le type de la scène que nous manipulons le résultat que nous voulons obtenir (structures

(dessin ou image) de données,

Algorithmes

126

affichage sur l’écran) le res très différentes. Dans fication des problèmes de res de nature géométrique

problème du découpage peut être traité de mani& le paragraphe suivant, nous ferons une classidécoupage en degageant les problèmes élémentai:’ inhérente à chacun d’eux.

fenêtre polygone résultant

Pour l’ensemble des traitements abordés , nous svons constaté la digparité des méthodes proposées dans la littérature, provenant de la diversité des préoccupations qui ont conduit à la résolution du problème dorme. A la lumière des chapitres précédents, nous montrerons dans le souci d’une démarche unitaire. cormnent nous avons utilisé les principes de la techoique du suivi de co”to”r pour résoudre les.problèmes de découpage.

0 polygone

1.

Découpage

d’un

Le problème est fenêtre polygonale.

nous ne raisonnerons que sur des co”to”rs être généraljsée pour des co”to”fs quelconques.

polygone

par

de calculer la Deux hypothèses

a) Si nous produisons de la notion de contour, segmenf par un polygone

simplement le problème

initial

a

4.2 Classification des problémes de découpage Dans cette classification, polygonaux, mais elle peut

127

de dlcoupage

On calcule ici l’ensemble composent le polygone résultant 2. Découpage

une fenêtre partie visible peuvent être

d’un polygone envisagées :

dans une

du dessin élémentaire

au trait sa”8 tenir est le découpage

compte d’un

:

d’une

tache

des contours (intérieurs du découpage. par “ne

fenêtre

Nous voulons ici afficher la partie remplie) dans une fenêtre polygonale. Deux solutions

peuvent

être

qui

polygonale

visible

envisagées

et extérieurs)

d’une

tache

(hachurée

ou

:

a) Déterminer le polygone résultant du découpage du polygone initial par la fenêtre (coorme en l-b). Puis hachurer ou remplir ce polygone (on se ramène au problème élémentaire du remplissage ou du hachurage d’une tache) .

seglsents

visibles

polygone

découpé polygone

On n’affiche

que les

parties

des arêtes

visibles

dans la

fenêtre.

b) Si nous voulons conserver la notion de contour, par exemple la “otio” de facette plane pour le dessin au trait, ou la notion de tache pour la synthèse d’image, le problème est de calculer le polygone résultant, situé à l’intérieur de la fenêtre qui résulte du découpage du polygone initial par celle-ci.

chant

résultant

b) Pour le hachurage, a” hachure tout que les parties visibles des lignes

parties

le polygooe de hachurage

des hachures

parties

I

initial :

en n’affi-

affichées

des hachures

“on

affichées

Algorirhmes

Le problème élémentaire (hachure) par un polygone. tial

demeure

le découpage

d'un

de droite il

Pour le remplissage proprement en n'affectant que les points

dit, on remplit tout situés à l'intérieur ensemble

P

G

le polygone inide la fenêtre :

des points

ensemble (extérieur Le problème élkkntaire rieur ou non du polygone

segment

visibles

estd e savoir si un point (comparaison point-contour).

Dans le cas du hachurage (et peut-être aussi vère nécessaire d'afficher les parties visibles menons alors au problème exposé en (1-a).

est

situé

du remplissage),s'il du contour, nous

-

s'anous ra-

Pour la première solution (a) le temps de calcul et d'affichage est proportionnel à la complexité de l'image initiale et non & la complexité de l'image visible. Mais si le temps de calcul du remplissage ou du hachurage dans la seconde méthode (b), est proportionnel à la complexité de l'image visible, il faut lui ajouter le temps de calcul du découpage proportionnel à la complexité des contours. Le problème est de savoir, dans quels cas, l'une ou l'autre des deux solutions est la plus avantageuse.

Q on obtient

PnQ,

Si q découpe

P on obtient

PnQ,

~

4.

aussi

Découpage

vouloir d'une

obtenir tache

Pn Q

P3

Si P découpe

On peut

P2

2 4

a

à l'inté-

#d piTQ 0Vd PS

0

des points non affichés à la fenêtre) a

129

de ddcoupage

QI,

Q2, Q3

Pl,'PZ, PnQ,

P4 D a3

P3, P4, P5

Pi,

PZ, P3, P4, P5 et Ql,

92,

Q3.

par une autre

Pour composer une image en deux dimensions, nous manipulons un ensemble de taches. Les taches peuvent se superposer ou se combiner, suivant certaines règles de composition. Ainsi, quand deux tâches se chevauchent, nous devons découper l'une par rapwrt à l'autre. suivant le résultat escompté :

En (b), nous proposons d'afficher la partie visible d'une tache, en effectuant le remplissage ou le hachurage de toute la tache initiale, mais en n'affectant que le sous-ensemble de l'ensemble des points ou des lignes de hachurage visibles dans la fenêtre. L'appartenance d'un point ou d'un segment terminé dans ce cas, de differentes façons : - Soit en utilisant ou de découpage d'un

l'un segment

des algorithmes par un polygone.

à la fenêtre, de comparaison

peut

être

dé-

point-contour

- Soit en effectuant le remplissage ou le hachurage de la fenêtre et de la tache simultanément et en n'affichant que les points ou les parties des lignes de hachurage qui appartiennent à l'intérieur de la tache et à l'intérieur de la fenêtre. 3. Découpage Il section

d'un

polygone

s'agit de déterminer de deux polygones

par un autre

tous les quelconques.

polygones

qui

résultent

de l'inter-

Q devant

0"

P

Nous pouvons

envisager

deux

solutions

P

devant

Q

:

a) On découpe l'un des contours par le contour Ve devant, en conservant les polygones résultants nière : c'est le problème énoncé en (3).

de la tache qui se tronextérieurs & cette der-

Si Q est

devant

P an obtiendra

Pi,

P2, P3, P4, P5

Si P est

devant

Q on obtiendra

01,

Q2, Q3.

130

qui

Svnthèse

d ‘image

: Algoriihmes

Ensuite, an affiche les taches est devant avec leurs couleurs

Dans ce cas, si uns ambiguïté, tervient. nous devons Calculer le

él&enroires

extérieures appropriées. illustrée résultat

ainsi

définies

et fa tache

sur la figure ci-dessous indu déccum~e des deux taches

ambiguïté Sur l'exemple

du paragraphe (3), nous devrons déterminer et Q3 où Pr-,Q sera de la couleur de P, si P est devant Q, ou de Q si Q est devant P, où Pl, P2, P3, P4 et P5 seront de la couleur de P, et où Q,, 92, et Q3 seront de la couleur de Q. Puis à partir de ce nouvel ensemble de taches, on pourra réaliser~le découpage de la même facon avec les autres taches de la scène qui sont en conflit. Une fois le traitement de toute la scène effectué, on affichera ce nouvel ensemble de taches. PnQ,

mais d'un

P,,

P2,

P3,

de la figure P4,

P5,

QI,

Q2,

b) On découpe les taches non plus en raisonnant sur leurs surfaces. On retrouve ici le problème ensemble de taches (voir ).

sur leurs contours, de la manipulation

Avant d'entreprendre le découpage, on peut essayer tout d'abord de determiner, si les deux contours polygonaux à comparer sont disjoints, si l'un contient l'autre OU s'ils se coupent (même chose pour les taches). 5.

Conclusion

:

Dans la classification quatre grandes classes l- Découpage Découpage Découpage Découpage

234-

des problèmes

du découpage,

mm

avons

dégagé

:

d'un polygone par une fenêtre, d'une tache par une fenêtre, d'un polygone par un autre, d'une tache par une autre.

Mais pour l'étude de chacune d'entre elles, il conviendra de distingua les cas particuliers où les fenêtres, les polygones ou les taches sont rectangulaires aux bords parallèles aux axes, convexes ou quelconques, pour tirer parti dans chacun des cm de leurs propriétés intrinsèques. D'autre élémentaires

part, :

nous

avons

mentionné

l'utilisation

de trois

problèmes

comparaison d'un point et d'un contour Le découpage d'un segment de droite par un contour 3- L'intersection de deux segments de droite. l2-

La

Le tableau récapitulatif qui suit, nous redonne toutes les opérations géométriques et de découpage citées plus haut, en y ajoutant des opération6 élémentaires telles que comparaison entre deux points, encre un point et

Algorhhmes

132 in effet, un algorithme de découpage peut cambir un segment ou une droite. ner plusieurs opérations élémentaires. Par exemple, l'algorithme d'intersection de deux contours convexes de SHAHOS, utilise la comparaison d'un point et d'un contour, la comparaison d'un point et d'une droite (au segment de droite) et le calcul d'intersection de deux segments de droite.

4.3. Comparaison d’un point et d’un contour polygonal 4.3.1

- INTROVUCTION

Le problème à résoudre est de savoir si un point est situé à l'intérieur ou à l'extéri+r d'un contour polygonal. La comparaison d'un point et d'un co,,touï est très so"vent rencontrée, en particulier, pour l'identification d'un contour ou d'une tache de manière interactive, dans le découpage d'un contour par un autre et dans certains algorithmes d'élimination de parties cachées. Nous blème en vexes de ordonnée

4.3.2

allons étudier les différents algorithmes qui résolvent ce prodifférenciant ceux qui s'appliquent uniquement aux contours conceux qui traitent les contours quelconques définis par la suite de leurs nbsom sommets si où i=l,...,nbsom (vair Table 4).

- CUMPARAISON POINT-CUtiTOUR

4.3.2.1

CONVEXE

- Itiodutin

Il existe deux méthodes qui ne traitent que des contours méthode de DAHAN LE TUAN, et celle de SHAMOS.

convexes

: la

La complexité du premier algorithme est en O(Nbsom). Par contre, si dans l'algorithme de SHAKOS nous effectuons un prétraitement sur le contour convexe dont le comportement est en O(Nbsorn), la comparaison effective du point et du contour convexe possède une complexité en O(Log Nbsom). 4.3.2.2

- Méthode

de SHAMUS Ivoin

h partir d'un point en N secteurs angulaires. : coordonnées polaires \*z s3

)

C intérieur au polygone convexe, C est considéré cozmne l'origine

02

on divise le plan d'un système de

axe de référence 8

1

s1

Soit

w p le point

à comparer

au contour.

-

de découpage

133

134

135

Cm détermine son angle dichotomique, an détermine Secteur calculé, on regarde L'algorithme ------_-__ Soit (1:nbsom) On obtient

polaire (cs,,cp), puis suivant une recherche le secteur auquel il appartient. Une fais le de quel côté de l'arête se situe le point p.

:

(xc,yc) les le tableau l'algorithme

coordonnées des angles suivant

du point intérieur polaires ordonnés :

par

au contour, et Taigle valeur croissante.

hrpahnhon POINT CONTOUK CONVEXE Début CO method e de SHAMOS 40 --$nontiehe: = aux. vxl:=xc-X[l +; vyi:=yc-yl71; v*z:=xc-w;

4.3.3

- COMPARAISON POINT-CONKXR

4.3.3.1

*

d'un

point

et d'un

contour

quelconque

de

- dénombrement d'intersections, - angles capables, - codage. Mais ces algorithmes ne surmontent pas facilement toutes les singularités (voir cas particulier de la Table 4). Pour pallier simplement ces difficultés, nous proposons un algorithme, fondé sur le raisonnement du "suivi de contour". - Mthode

du nuiui

Princiw On résoud le contrôle sonnement du remplissage figure 4.2).

a:=wlind*retll-xlindicel; b:=y[i,,dicetl)-y&fice); c:=a.yitiel+b.wL&dicel; )urod:=(a.yptb.wp-c)(a.yc+b.xc-cl; bi Pnod sk+,).

respectivement les ), et (s.,s. 1 JC'

. Le tableau v(O..4) contient les signes des valeurs ui, i=l à 4, représentant les signes des extremirés du segment par rapport aux 2 aretes caupées par la droite support. (qn)n=,,Z sont les caordonnées du segment à afficher.

Soient

s.,s. et sk,sk+, les paires de somoefs où ce changement de 2 I+l signe intervient, et Ll et L2 les segments respectifs qu’ils définissent (S. peut être nulle pour l’un des sommets de l’une ou des deux paires (cas 4)?. Connaissant maintenant les deux arêtes du polygone qui coupe la droite passant par le segment (pl,p2), il faut déterminer le position relative des points pl et p2 par rapport aux deux segments Ll et L2 à partir du signe des quatre quantités : ul = det(pl,s.,s. = xl

) 3 I+l (Yj-Yj+,)+yl(xj+,-xj)+(xjYj+,-Yjxj+,)

(position

du point

u2 = d=t(p2,sj,sj+,) = x2 (Yj-Yj+,)+y2(X. (position du point

pl par rapport

li

,+,-xj)+(XjYj+,-YjXj+,) p2 par rappart à Ll) (2-c) à L2) -

Si nous parcourons le cantour dans le cens des aiguilles’d’une mantre, le signe de U sera négatif quand un point se situera à l’intérieur du polygone. Cette expression sera nulle si ce point appartient au cOntOur. Soit L le segment (pI,pZ) et (ql,q2) les extrémités du segment a afficher résultant du découpage de L par le polygone. L’algorithme qui suit, calcule ?,,et q2 en tenant compte des différentes configurations possibles des extremrtés p, et p2 du segment L.

. (xl,yl)

utiliser

X(l..N)

ef (xî,y2)

les structures

de données suivantes

ef Y(1. .N) contiennent sont

II) &

les coordonnées

-

k#ZI d”e

(2-d)

u4 = d=f(p2,sk,sk+,) = x2 (Y k -Y k+,)+y2(Xk+,-Xk)+(XkYk+,-YkXk+l) (position du point p2 par rapport à L2).

L’algorithme : NOUS supposons

equation

Si:=Xlii.dytYlil.dx+dry; v:=n.igwlS~l; ai U#V et ut0 -ai?o.aCo changemont de aigrie 40 lK=k+l: Blk,ll;=Xli-Il ; Blk,Zl:=Yii-11; Clk,ll:~=Xlil ; Cik,ZI:=Yfil; Gwn ai lu=0 +J v=Ol ateohh ,&I découpage - 2. &g--u: =v;

(2-b)

= xl (Yk-Yk+,)+y1(4+,-~)+(~Yk+,-Yk~+,) (position du point pl par rapport

; -

(2-a)

u3 = det(pl,sk,sk+,)

. Les tableaux du palygane.

,~X!i).dytYlil.dx+dxy

les coordonnées

des points

pl et p2.

: des N sommets

cztoti ul:=det uZ:=det u3:=det u4:=de*

fpl,Bif,*l, lpZ,Blt,*), (p1,812,‘), ipZ,ElZ,‘l,

CtI.*II clt,*)l c12,“)l ClZ,*ll

; 0 ; ; ;

éQ&ti

2 40

146

Algorilhma

Traitement droite mités

des

singularités

:

4.4.4 t:, / ;,'

Nous rencontrons une singularité si la droite support du segment de passe par l'un des sormets du polygone ou bien si l'une des extrédu segment appartient à l'une des arêtes du polygone.

- Parcours du contour : il y a une singularité s'il existe i tel qk~e le signe (Si) est nul. Dans le cas où deux sommets consécutifs ont un signe nul (~=V=O) nous considérons alors le segment L invisible. Sinon, si un sosmet si est de signe nul, nous prenons en compte uniquement l'arête (signe(Si_,)#signe(Si) et signe (Si-,)#O). (Si-, ,Si) - Calcul de la partie visible une ou deux valeurs Ui est nulle. Si deux valeurs tiennent au contour ta.

du segment

U. sont nulles alors d: polygone et L est

L : il

y a une singularité

Si une seule des valeurs U. est nulle, alors une (p) du segment L appartient aulcmfour. Dans ce cas, tre extrémité (p') par rapport à l'arête Lp A laquelle mité p. est positive, alors L est invisible. Sinon si alors ql=p et qZ=p' si signe de p par rapport à Lp' sinon (voir figure 4.5.).

seule des extrémités si le signe de l'auappartient l'extréce signe est négatif, est négatif, qZ=Lp'fiL

- DECOUPAGE PAR RAPPORT A UN CONTOUR f&ELCONQUE

4.4.4.1

- ?tiodu&n

Nous ne pouvons .vas aénéraliser l'alaoritbme de SUTHERLAND pour le dé_ coupage d'un segment de droite par un polygone non convexe, parce que ce dernier peut chevaucher, de part et d'autre, les droites supports de ses arêtes. i

si _,

q,=p, et q2=p2 car p, et p2 apparcontenu par ce polygone (convexi-

147

de découpage

Nous avons cherché à généraliser l'algorithme de PAVLIDIS pour des polygones non convexes (voir -GRON 83a>). La généralisation est possible mais complexe. En effet, nous avons montré que la mise en oeuvre du traitement des singularités est délicate et onéreuse car pour une arête (si.si+,), dès que le signe de l'un des somwts est ml (c'est-à-dire que et compte des deux vamets précédents s. s.=o 0" si+, =O) il faut tenir sfl-,,ou et des deux soumets suivants si+te$ si+3 du sommet précédent si-, ou smplement du smmet suivant si+*. Pour pallier ces difficultés, rithme de hachurage oblique sans tO"ï.

nous avons utilisé l'idée de notre algorotation par la méthode du suivi de con-

4.4.4.2

de contmt”

- L’dgodhme

Le problème par un polygone

de ?bu.&.i

est donc, de calculer non-convexe (figure

le découpage 4.6.).

d'un

segment

de droite

(entre parenthèses: signe du point p' par rapport à Lp'; sinon signe du point p' par rapporr à LP).

Figure Critiques

4.5.:

Cas particulier tour.

où une des extrémités

appartient

Figure

:

Dans la recherche des arêtes qui coupent sonnets du contour n'est pas nécessairement section) et les singularités sont surmontées devons parcourir le contour dans le sens des tation a priori).

parties=

au con-

la droite, le parcours exhaustif (quand il y a simplement. Cependant, aiguilles d'une montre

des internous (orien-

4.6.:

segment Découpage vexe.

d'un

segment

de droite

de droite

par une fenêtre

non con-

Le principe Nous considérons l'équation de la droite.passant par le segment. a et b les accroissements respectifs en x et en y du segment. Nous

ment est

raisonnons équivalent

dans le cas en inversant

où lai>-lbl. x et y.

Soit y= kx+yO l'équation de la droite données .

Nous avons dans ce chapitre, envisagé le découpage d'un en distinguant trois types de fenêtre : rectangulaire, convexe (voir tableau récapitulatif : table 5).

part, "ous avons de droite :

- la première la droite passant

polygone

arêtes

- CONCLUSION

D'autre un segment

- INT!UVUCTION

nécessairement

en supprimant du calcul qui lui sont parallèles

: C""~OUT~

4.5.1

Le problème est d'effectuer l'intersection entre un polygone et une fenêtre polygonale, de telle sorte que le résultat du découpage soit un co*tour polygonal. (figure 4.9.) fenêtre polygonale polygone dkoupé

: "on

4.5. Découpage d’un polygone par une fenêtre polygonale

exhiber,

deux facons

utilise

un point

4.5.2

et l'un

méthode consiste à calculer par le segment en ce point

possibilité

de comparer

Puis S&AMOS, -0 si

le vecteu

fi se dirige

ou

164

Synrhèse

d’ïmage

: Algorithmes

dlémenroir~

Partant de deux arêtes p et 4 choisies arbitrairement, on progresse sur l'un ou l'autre des cmtours, de telle sorte que l'une des deux 11pointe" vers l'autre. Ces règles sont résumées dans la table 6. poinrer(fi,CJ pointer

(4,fi)

evancer à partir te extérieure

l------------L

----------------

poiater(+,fi)

p suivant

Table

6 : Règles

A chaque et un sommet trouvées en l'algorithme

4pointer($,$

de l'arê-

q suivant

--------A------------

------

J

evemer à partir de l'arête exrérieure

de progression

autour

des contours.

pas, deux arêtes 6 et 5 sont comparées (test de PnQ est obtenu. Toutes les intersections parcourant au plus, deux fois chaque contour, d'avoir un comportement en Oh+m).

d'intersection) peuvent être ce qui permet

@; à

3) Singularités Trois

2) L'algorithme

types

a) Un samec

L'algorithme consiste principalement à utiliser les règles de progression, dans une structure répétitive, qui permettent d'avancer d'une arête sur l'un ou l'autre des contours à chaque pas. De plus, à chaque pas, deux arêtes mnt comparées (test d'intersection) et un somet est obtenu. Quand le boucle est terminée, fou8 les somets du polygone PfiQ ont été calculés excepté lorsque PnQ = 0. Sans prendre générale suivante

particuliers

en compte :

les

cas particuliers,

l'algorithme

d'intersections

de P appartient

peuvent

B une arête

se présenter

:

de Q :

/---’

l-T--lQ

a la forme

b) P et Q ont deux

sonmoets communs : /---p

C)

Une arête

Ces singularités section qui suit.

de P chevauche

sont

une arête

suI7nmtéeS

grâce

de Q (colinéarité)

à notre

définition

:

de l'inter-

167

166

x -xA + (XI%-XA) t, Y = YA + (YB-YA) t,

Intersection de 6 et $ : Soient p-(spi.spi+,), +(sqj,sqj+,). , ou sq. ou *q.+, prenons-nous en compte cette - si pfl+sp. ou sp. intersection ? ‘Si oui:+kus obtkmns dk points d’intersection identiques (voir singularité (a)). ou quatre points d’intersection identiques (voir singularité (b)). Pour obtenir un unique point d’intersection, dans ce cse particulier, il y surs intersection, pniquement si pn: est égal B “Pi+, ou sqj+,. - si i, et 6 sont colinéaires

alors

fini

- 0

de nième pour (CD), on a : x = xc + @D-XC) t2 Y = YC + (YB-YC) t2 La valeur

du paramétre

indique

la position

du point

(X,Y)

SUT la droi-

re :

(cl).

(singularité

t,>1

4) Conclusion : . Ls complexité de l’algorithme B (n+m), su nombre d’intersections

B t,-1

de O’WUPJG? et al., est proportionnelle et su nombre de sosrsets de PnQ. oy2-2

rencontrer

par une seule E*=(x~,Y~)

. Y,-mx,‘Y2-~2

où A=pzm2-(l+m2)(pz-R2) Nous

passe

:

(E,,E2).

- la droite kTX+p

se présentent

E,=(x,,YI),

de l'arc

Intersection en Ed (point de naissance :*)

en Ed :t)

-

X

:

186 b) ~a droite passe par les deux extrémités E, et E2 avec ~~=Sd(l) . XIx2

:

e

2. Extraction 'jt

- intersection

est vertical,

x1

on inversera le rôle des X et

L'inconvénient de cette méthode est l'utilisation de la fonction gonométrique inverse arctg pour le calcul des angles. Si

E,=Ef

c'est

le

contraire.

du cercle avec un segment de droite:

x

La complexité de l'algorithme est proportionnelle au nombre de primitives. Nous pouvons également tirer parti de la convexité e" arrêtant la comparaison de la droite support avec les primitives du contour dès que l'on a trouvé deux points d'intersection.

(1)

des parties visibles.

Commepour le découpage d'un segment de droite, pour éviter les singularités (cercle passant par un sommet), on oriente les segments vers le bas et on ne prend pas en compte les points d'intersection confondus avec l'extrémité fin :

L'ensemble des intersections de la droite support définit sur celle-ci un ensemble de segments de droite intérieurs à la tache et joignant ses bords. La partie visible du segment à découper sera calculée en effectuant l'intersection de celui-ci avec l'ensemble des segments intérieurs au.conto"r "on polygotil (vair chapitre 4.4.4.2.). Si le segment de droite des Y.

d'un arc de cercle situé

On calcule l'intersection de la droite support avec le cercle. Puis s'il y a deux intersections distinctes, on récupère les points d'intersection appartenant au segment de droite.

: pas d'intersection au point T (point de mort) : intersection au point T (point de naissance).

f Y,-y'Y2-==2

POLYGONAL

l- Calcul des points d'intersection

. e, la droite est tangente au cercle au point T. Deux cas peuvent se présenter : l- le point T diffère des extrémités de l'arc de cercle : il "'y a pas d'intersection. 2- Le point T est confondu BYPCl'une des extrémités de l'arc : soient E,=(x,,y,) cette extrémité et E2=(x2,y2) la seconde. . Y,-~, G. HRGRON Techniques de remplissage Con~. P et T n'82 35068, bre 1982.

Septembre



(HEGRON

pour

76)

How to color in a coloring book Camp. graphies, Vol. 12, August

82> et

et al.

él&mentaires

J.F. &IR"IS, C.N. JUDICE, W.H. NINKE A survey of techniques for rhe display bilevel displ~ays. CGIP, ~01.5, pp. 13-40, 1976.

82>

EDMONDS,

83c>

G. HEGRON Etude comparative d'algorithmes par ordinateur. Thèse de 3ème cycle, Université