II.2.2. Remplissage
Le remplissage d'une courbe fermée discrète
consiste à allumer les points de l'écran qui correspondent
à la partie de l'espace discret délimitée par cette
courbe. Nous présentons le cas où la courbe est un polygone
à n sommets{Pi} avec i=1...n.
L'algorithme de remplissage consiste alors à partir du
point le plus à gauche et à suivre la suite des segments qui
composent le polygone jusqu'au point le plus à droite.
Pour se faire, nous avons deux types d'algorithme de
remplissage :
ü L'algorithme de remplissage du polygone
convexe ;
ü L'algorithme de remplissage du polygone quelconque.
Figure II.1: Polygone convexe
rempli.
a. Remplissage d'un polygone
convexe
Un polygone convexe est une figure plane à plusieurs
angles.
Dans le cadre de 2D, pour la représentation de ce dernier,
on utilise l'algorithme suivant :
1. Initialisation
Pi = le plus à gauche des sommets. SH le segment
montant qui part de Pi. SB le segment descendant qui part de Pi. x = l'abscisse
de Pi.
2. Faire
(a) Mettre à jour les segments SH et SB (si on atteint
l'extrémité droite du segment, on passe au segment suivant). (b)
Calculer l'ordonnée yH du point d'abscisse x sur le segment SH. Calculer
l'ordonnée yB du point d'abscisse x sur le segment SB. (c) Tracer le
segment vertical reliant (x,yB) à (x,yH). (d) Incrémenter x de
1.
3. Tant que x n'a pas atteint l'ordonnée du point le
plus à droite du polygone.
Figure II.2: Polygone convexe.
b. Remplissage d'un polygone
quelconque
Quand le polygone n'est plus convexe, sa forme peut devenir
très complexe. Dans ce cas on ne gère plus
séparément les segments inférieurs et supérieurs
mais on détermine à chaque étape la liste des
intersections de l'ordonnée courante avec le polygone (en comptant
double l'intersection avec un sommet). En partant du bord, on trace les
segments reliant les intersections paires aux intersections impaires.
Voici l'algorithme découlant correspondant :
1. Initialisation
x =l'ordonnée du point le plus à gauche.
2. faire
(a) calculer la liste des intersections avec le polygone et
trier cette liste (on note 2nx le nombre de ces intersections
et{(x,ui)}i=1..2nx la liste triée)
(b) tracer les nx segments qui relient (x,u2i) `à
(x,u2i+1) (i va de 0 ` a nx -1). (c) Incrémenter x de 1.
3. tant que x n'a pas atteint l'ordonnée du point
le plus à droite du polygone.
Figure II.3: Polygone quelconque.
| 
