Algorithmique de base de l'Infographie Page 1 of 31

Algorithmique de
base de l'Infographie
DESSIN DES Dessin 2D des objets de base
OBJETS
BASIQUES Algorithmes de tracé de segments
Segments
Cercles Algorithme de base pour beaucoup de traitements de
Ellipses l'Informatique Graphique:

CLIPPING
dessin en fil de fer,

REMPLISSAGE
remplissage,
2D
élimination des parties cachées,
Polygone convexe
...
Polygone non convexe
Zones de pixels On désire tracer un segment entre deux points (xi,yi) et (xf,yf)
de couleur
de R2.
€
Ce tracé est effectué sur un écran bitmap (composé d'une
matrice de n x m pixels carrés).
RETOUR
-> Le segment doit être discrétisé (rasterisé).

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 2 of 31

Le programme GLUt

Exécutable GLUt

Problème: Quels pixels doit-on tracer?

Trois impératifs:

Tout pixel du segment discret doit être traversé par le

segment continu.

Tout pixel du segment discret doit toucher au moins un

autre point soit par l'un de ses cotés, soit par un de ses
sommets (8-connexité).

4-connexité 8-Connexité

Le programme GLUt

Exécutable GLUt

On doit tracer le moins de pixels possible.

On trace 1+max(abs(xi-xf),abs(yi-yf)) pixels.

Si abs(xi-xf) < abs(yi-yf), on trace un pixel et un seul par ligne

interceptant le segment, sinon on trace un pixel et un seul par
colonne interceptant le segment.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 3 of 31

Bons tracés

Mauvais tracés

Mauvais tracés

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 4 of 31

Le programme GLUt

Exécutable GLUt

Tracé de segments par l'équation cartésienne

On pose comme hypothèse simplificatrice: xf > xi, yf > yi et (xf-

xi) >= (yf-yi). Tous les autres cas peuvent s'y rapporter.

-> Le coefficient directeur de la droite passant par les deux

sommets est positif et inférieur ou égal à 1.

On utilise l’équation cartésienne de la droite:

y = a x + b avec a = et b = yi - a xi

void ligne(int xi,int yi,int xf,int yf) {

int x,y ;
double a,b ;
a =(double) (yf-yi)/(xf-xi) ;
b = yi - a * xi ;
for ( x = xi ; x <= xf ; x++ ) {
y = a * x + b ;
allume_pixel(x,y) ; }
}

Le programme Aux Le programme GLUt

Exécutable Aux Exécutable GLUt

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 5 of 31

Caractéristiques:

simplicité algorithmique

lenteur due à l'utilisation de réels, d'une division et de
multiplications

Bresenham pour le tracé de segments

Algorithme incrémental en x et en y

Au cours de l'exécution, on quantifie pour chaque pixel la

différence entre ses cordonnées entières (utilisées pour
l’affichage raster) et réelles telles qu'elles sont calculées sur
le segment continu.

On pose de nouveau les hypothèses: xf > xi, yf >= yi, xf - xi > yf

- yi.

-> On allume un pixel en chaque abscisse entière x de xi à xf.

-> On utilise une variable cumul pour stocker la différence

entre l'ordonnée entière et l'ordonnée réelle.

void ligne(int xi,int yi,int xf,int yf) {

int dx,dy,cumul,x,y ;
x = xi ;
y = yi ;
dx = xf - xi ;
dy = yf - yi ;
allume_pixel(x,y) ;
cumul = dx / 2 ;
for ( x = xi+1 ; x <= xf ; x++ ) {
cumul += dy ;
if (cumul >= dx) {
cumul -= dx ;
y += 1 ; }
allume_pixel(x,y) ; }
}

Le dernier pixel allumé a pour coordonnées (xf,yf) car

dx/2+dy*dx est la valeur totale de ce qui a été ajouté à cumul
au cours de l'exécution.

-> = dy est le nombre de fois où y a été

incrémenté de 1.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 6 of 31

-> l’ordonnée du dernier pixel allumé est yi + dy = yf.

Caractéristiques

Plus grande complexité algorithmique.

Rapidité due à l'utilisation exclusive d'entiers courts (valeurs

maximales de l'ordre de la résolution de l'écran -> petites
valeurs) et d'opérations arithmétiques simples sur ces entiers
(additions, soustractions et comparaisons).

Algorithme adapté pour le tracé de tout segment

Utilisation de deux variables xinc et yinc pour gérer des

incréments de 1 ou -1 pour x variant de xi à xf et y variant de yi
à yf.

Deux parties dans l'algorithme:

une pour l'incrémentation en x,

l'autre pour l'incrémentation en y,

en fonction de la pente du segment.

void ligne(int xi,int yi,int xf,int yf) {

int dx,dy,i,xinc,yinc,cumul,x,y ;
x = xi ;
y = yi ;
dx = xf - xi ;
dy = yf - yi ;
xinc = ( dx > 0 ) ? 1 : -1 ;
yinc = ( dy > 0 ) ? 1 : -1 ;
dx = abs(dx) ;
dy = abs(dy) ;
allume_pixel(x,y) ;
if ( dx > dy ) {
cumul = dx / 2 ;

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 7 of 31
for ( i = 1 ; i <= dx ; i++ ) {
x += xinc ;
cumul += dy ;
if (cumul >= dx) {
cumul -= dx ;
y += yinc ; }
allume_pixel(x,y) ; } }
else {
cumul = dy / 2 ;
for ( i = 1 ; i <= dy ; i++ ) {
y += yinc ;
cumul += dx ;
if ( cumul >= dy ) {
cumul -= dy ;
x += xinc ; }
allume_pixel(x,y) ; } }
}

Exemple d'exécution

On souhaite tracer le segment (3,2)-(18,11).

-> dx = 15, dy = 9.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 8 of 31

Le programme GLUt

Exécutable GLUt

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 9 of 31

Le programme Aux Le programme GLUt

Exécutable Aux Exécutable GLUt

Bresenham pour le tracé de cercles

Principes

On désire tracer un arc de cercle de centre O et de rayon r

circonscrit au second octant du plan.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 10 of 31

-> On trace un arc entre les points (0,r) et ( , ).

Un pixel sera allumé sur chaque colonne d'abscisse comprise

entre 0 et .

Comme dans le cadre de l'algorithme de Bresenham pour le

tracé de segments, le tracé du cercle est réalisé
incrémentalement:
La position d'un pixel P dépend de la position du pixel
précédent. Elle est déterminée via l'évaluation de la position de
P au dessus ou en dessous de l'arc réel.

Si un pixel est allumé en position (x,y), le prochain pixel sera

obligatoirement soit en position (x+1,y) soit en position(x+1,y-1)
(tangente au cercle de coefficient directeur compris entre 0 et
-1 sur notre portion d'arc).

L'algorithme est basé sur l'étude, pour chaque colonne de

pixels, de la position (vis à vis du cercle continu: au dessus ou en

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 11 of 31

dessous) du point intermédiaire entre les deux pixels

superposés définis ci-dessus qui encadrent le cercle (d'où le
nom algorithme du midpoint).

Si ce point intermédiaire est situé dans le cercle (cas 1), le

pixel allumé sera le pixel situé en dehors du cercle. Sinon (cas
2), le pixel situé à l'intérieur du cercle est allumé.

L'idée de l'algorithme est donc de définir la position de chaque

point intermédiaire de façon incrémentale, colonne de pixels
après colonne de pixels.

La position d'un point P de coordonnées (x,y) vis à vis du cercle

continu est donnée par l'équation cartésienne f(x,y) = x2 + y2 -
r2.

-> Si f(x,y) < 0, P est dans le cercle, sinon il est à l'extérieur.

Première alternative : L'obtention d'un résultat négatif pour

cette équation pour un point intermédiaire M conduit au choix
du pixel extérieur E. Le prochain point intermédiaire sera situé
en ME, c'est à dire un pixel à droite de M.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 12 of 31

Seconde alternative : Un résultat positif conduit au choix du

pixel intérieur SE, et au prochain point intermédiaire MSE situé
un pixel à droite et un pixel plus bas que M.

Définition récurente de l'algorithme

P = (xp,yp) est la position d'un pixel allumé.

La variable d (évaluant la position du point intermédiaire

précédent vis à vis du cercle) calculée à partir de P est:

d = f(xp+1,yp- ) = (xp+1)2 + (yp- )2 - r2.

(1) Si d est inférieur à 0, E est choisi. Le prochain point

intermédiaire est alors ME et la valeur d est ajustée de la
manière suivante:

newd = f(xp+2,yp- ) = (xp+2)2 + (yp- )2 - r2

d = newd = d + (2xp + 3).

(2) Si d est supérieur à 0, SE est choisi. Le prochain point

intermédiaire est MSE et la valeur d est ajustée:

newd = f(xp+2,yp- ) = (xp+2)2 + (yp- )2 - r2

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 13 of 31

d = newd = d + (2xp - 2yp + 5).

-> On obtient une définition récurrente incrémentale de d

n'utilisant que des entiers.

La première valeur de d est obtenue à partir de la position (0,r)

pour un point intermédiaire de position placée en (1,r- ).

-> dinit = 1 + r2 - r + - r2 = - r.

-> en entier: dinit = 1 - r.

On connaît maintenant totalement la définition récurrente de d.

Implantation

On peut écrire une fonction de tracé d'un arc de cercle où le

rayon r est un paramètre entier placé en entête.

void arcDeCercle(int r) {
int x,y,d ;
x = 0 ;
y = r ;
d = 1 - r ;
allume_pixel(x,y) ;
while ( y > x ) {
if ( d < 0 )
d += 2 * x + 3 ;
else {
d += 2 * (x - y) + 5 ;
y-- ; }
x++ ;
allume_pixel(x,y) ; }
}

Exemple d'exécution

Arc de cercle de 20 pixels de rayon:

15 pixels tracés

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 14 of 31

Le programme GLUt

Exécutable GLUt

Cette fonction pourra ensuite être adaptée (au moyen de

symétries) pour tracer un cercle entier.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 15 of 31

Le programme Aux Le programme GLUt

Exécutable Aux Exécutable GLUt

Le tracé d'ellipses

Un algorithme incrémental de tracé d'ellipses basé sur une

technique du midpoint peut être défini. Le travail est plus
complexe par le fait que le tracé à l'intérieur d'un quadrant
n'est plus symétrique par rapport à la diagonale.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 16 of 31

L'algorithme réalisera le tracé en deux passes consécutives

pour un quadrant. Par exemple pour le quadrant 1, une passe
avec un pixel par colonne pour la région 1 et une passe avec un
pixel par ligne pour la région 2. La limite entre ces deux régions
est le point où la pente est de -1.

void ellipse(long a,long b) {

int x,y ;
double d1,d2 ;
x = 0 ;
y = b ;
d1 = b*b - a*a*b + a*a/4 ;
allume_pixel(x,y) ;
while ( a*a*(y-.5) > b*b*(x+1) ) {
if ( d1 < 0 ) {
d1 += b*b*(2*x+3) ;
x++ ; }
else {
d1 += b*b*(2*x+3) + a*a*(-2*y+2) ;
x++ ;
y-- ; }
allume_pixel(x,y) ; }
d2 = b*b*(x+.5)*(x+.5) +
a*a*(y-1)*(y-1) - a*a*b*b ;
while ( y > 0 ) {
if ( d2 < 0 ) {
d2 += b*b*(2*x+2) + a*a*(-2*y+3) ;
y-- ;
x++ ; }
else {
d2 += a*a*(-2*y+3) ;
y-- ; }
allume_pixel(x,y) ; }
}

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 17 of 31

Ellipse de différents grands-axes

Le programme GLUt

Exécutable GLUt

Le clipping (découpage)

Définition

Clipping écran: Traitement permettant de réduire le dessin

d'un objet graphique à une région de l'écran.

Cette région est classiquement un rectangle mais peut être de

toute autre forme.
Le clipping peut aussi être réalisé en 3D.

Exemple: Clipping de 2 segments à l'intérieur d’un rectangle.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 18 of 31

Le programme GLUt

Exécutable GLUt

Clipping dans un rectangle : Traitement de base de

l'Informatique Graphique -> nécessité d'efficacité.

Cohen-Sutherland pour le clipping d'un segment à l’intérieur

d’un rectangle

Algorithme basé sur la détection d’un certain nombre de

configurations de placement d'un segment relativement à un
rectangle.

On associe à chaque extrémité du segment un code sur quatre

valeurs pseudo booléennes indiquant la position (x,y) du sommet
par rapport aux quatre droites définissant le rectangle de
clipping (xmin, xmax)-(ymin, ymax):

la première valeur = 1 si x < xmin,

la deuxième valeur = 1 si x > xmax,

la troisième valeur = 1 si y < ymin,

la quatrième valeur = 1 si y > ymax.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 19 of 31

Le programme GLUt

Exécutable GLUt

Dans trois cas on sait si un segment de coordonnées (xi,yi)-

(xf,yf) passe ou ne passe pas à l’intérieur du rectangle
(xmin,ymin)-(xmax,ymax):

(1) Si les codes des deux extrémités sont égaux à

0000 (cas (1) ci-desous), le segment est entièrement
dans le rectangle de clipping.

(2) Si un seul des codes des deux extrémités est égal

à 0000, le segment est pour partie dans le rectangle
de clipping (cas (2)).

(3) Si aucun des codes des extrémités n'est égal à

0000, et que le "et logique" entre les deux codes est
différent de 0000 (un 1 apparaît en position 1, 2, 3 ou
4), le segment est obligatoirement situé à l’extérieur
du rectangle (cas (3)).

Dans tous les autres cas, on ne peut pas conclure avec certitude
(cas (4)).

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 20 of 31

Le programme GLUt

Exécutable GLUt

Principe de l'algorithme

A partir du segment s initial, on déplace successivement les

extrémités de s vers les droites AB, BD, AC ou CD définissant
le rectangle de clipping ABDC jusqu'à établir que s n'appartient
pas à ABDC (cas (3)) ou que s appartient entièrement à ABDC
(cas (1)).

Au cours de l'exécution, chaque fois qu’il est établi qu'une des

valeurs du code d'une extrémité n'est pas égale à 0000, on
déplace cette extrémité pour qu'elle vienne rejoindre l'une des
droites AB, BD, AC ou CD. Ainsi, on en change le code.
Le choix de la droite cible est réalisé en choisissant le premier
booléen du premier code d'extrémité qui n'est pas à faux.

Ces modifications sont réalisées itérativement jusqu'à pouvoir

conclure.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 21 of 31

Cet algorithme de clipping peut facilement être adapté à R3

pour le clipping de segments de droites à l’intérieur d’un
parallélépipède rectangle.

Algorithme

procedure clip(point_2D p1,point_2D p2,

fenetre f) {
code c1,c2 ;
point_2D p ;
c1 = code(p1,f) ;
c2 = code(p2,f) ;
tant que (c1 ou c2 contient un 1) et
(c1 et c2 n'ont pas de 1 commun) {
si c1 égal 0000 {
permuter p1 et p2 ;
permuter c1 et c2 ; }
si (c1 & 0001) égal 0001 {
abscisse de p1 = abscisse
de l'intersection entre (P1,P2)
et l'horizontale en ymax de f ;
ordonnée de p1 = ymax de f ; }
sinon
si (c1 & 0010) égal 0010 {
abscisse de p1 = abscisse
de l'intersection entre (P1,P2)
et l'horizontale en ymin de f ;
ordonnée de p1 = ymin de f ; }
sinon
si (c1 & 0100) égal 0100 {
ordonnée de p1 = ordonnée
de l'intersection entre (P1,P2)
et la verticale en xmax de f ;
abscisse de p1 = xmax de f ; }
sinon
ordonnée de p1 = ordonnée
de l'intersection entre (P1,P2)
et la verticale en xmin de f ;
abscisse de p1 = xmin de f ; }
c1 = code(p1,f) ; }
si (c1 égal 0000) et (c2 égal 0000)
tracer entre p1 et p2 ;
}

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 22 of 31

Le programme Aux Le programme GLUt

Exécutable Aux Exécutable GLUt

Le remplissage 2D

Définition

Ligne brisée 2D: Courbe polygonale 2D définie par une suite

non circulaire de points reliés par des segments.

Polygone 2D: Surface 2D bordée par une suite circulaire de

points reliés par des segments.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 23 of 31

Le programme GLUt

Exécutable GLUt

Remplissage d’un polygone convexe

Remplissage trame après trame en commençant du sommet

inférieur et en remontant les trames tout en gérant le parcours
des suites de faces droite et gauche.

Suite gauche: B, A, F, E

Suite droite: B, C, D, E

Remplissage d’un polygone éventuellement concave

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 24 of 31

Principe

Processus de remplissage traçant les trames internes au

polygone les unes à la suite des autres.

Chaque trame interceptera un nombre paire n de cotés du

polygone.

Après tri en x des n intersections Pi (1 <= i <= n), on tracera des

segments entre chaque couple de coordonnées (P2*j-1,P2*j) avec
1 <= j <= .

Mise en œuvre

Une liste chaînée LCA permet de gérer une suite de cotés

actifs.
file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 25 of 31

Cette liste indiquera quels sont les cotés ayant une intersection
avec la trame en cours de traitement.

Elle est mise à jour à chaque avancée d’une trame au cours de

l’exécution de l’algorithme.

Elle est triée en permanence par ordre croissant des abscisses

x des points intersections.

LCA pour la trame 7

LCA pour la trame 13

Création d’une structure intermédiaire SI contenant les

informations qui seront nécessaires à la gestion de LCA.

SI est un tableau de listes chaînées.

Pour chaque coordonnée y, on stocke l’ensemble des cotés c du

polygone tels que y est l'ordonnée minimale ymin des deux
extrémités de c.

(1) En parcourant SI on pourra savoir quels cotés devront

entrer dans LCA pour telle ou telle ordonnée.

(2) Pour gérer le retrait des cotés de LCA, on mémorise

l'ordonnée maximale de chaque coté.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 26 of 31

On stocke aussi pour chaque coté:

- l’inverse 1/a de son coefficient directeur (incrément en x pour

un déplacement unitaire en y),

- l’abscisse xmin correspondant à ymin.

Les listes de SI sont triées par ordre croissant de xmin, puis

pour deux xmin identiques, par ordre croissant de la valeur 1/a.
Ce tri a pour but de faciliter le déplacement des cotés vers
LCA car cet ordre de classement devra être respecté dans
LCA.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 27 of 31

Algorithme

Procedure remplir_polygone(p:polygone) ;
début
créer la structure SI
initialiser la structure LCA à vide
pour chaque trame intersectant
le polygone
début
gérer les entrées dans LCA à partir
de SI
gérer les sorties de LCA à partir
des informations contenues dans SI
afficher tous les morceaux de trames
décrits dans LCA

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 28 of 31
fin
fin

Remplissage d'une zone définie par une couleur

Définition

On entend par zone définie par une couleur:

(1)€un ensemble connexe maximum de pixels de même couleur,

(2)€un ensemble connexe maximum de pixels dont la couleur

n'est pas une couleur définie (couleur du bord de la zone)

Cas€(1):€Chacune des zones grise, noire et blanche.

Cas€(2):€L'union des zones grise et noire vis à vis de la zone

blanche.

Le remplissage est réalisé à partir d'un pixel germe.

Un premier algorithme

Principe

Au cours du remplissage, à chaque fois qu'un pixel devant être

rempli est parcouru, on le remplit, puis on lance récursivement
l'algorithme sur les pixels qui lui sont connexes.

Algorithme pour le remplissage d'une zone bordée

L'implantation est naturellement récursive. c est la couleur de

tracé. lim est la couleur limite.

void remplissage(int x,int y,

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 29 of 31
int c,int lim) {
cp = getpixel(x,y) ;
if ( ( cp != lim ) && ( cp != c ) ) {
putpixel(x,y,c) ;
remplissage(x,y+1,c,lim) ;
remplissage(x,y-1,c,lim) ;
remplissage(x+1,y,c,lim) ;
remplissage(x-1,y,c,lim) ; }
}

L'utilisation de la récursivité entraîne très fréquement des

problèmes de dépassement de capacité de la pile du programme
si les zones remplies sont trop grandes (ce qui conduit à une
profondeur de récursivité trop grande).

Un deuxième algorithme

Principe

Le remplissage est effectué suite horizontale maximale de

pixels après suite horizontale à partir d'un pixel germe initial.

A chaque itération:

On remplit tous les pixels Pi jusqu'à la couleur limite à

droite et à gauche du germe courant.

On recherche parmi les pixels au dessus et en dessous des

Pi ceux qui sont le plus à droite d'une suite horizontale
maximale à remplir.

Ces pixels sont empilés comme germes des itérations

suivantes.

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 30 of 31

...

Algorithme pour le remplissage d'une zone bordée

L'implantation nécessite la définition d'une pile de positions de

germes. L'algorithme prend la forme d'une boucle exécutée
tant que la pile n'est pas vide.

void remplissage(int xx,int yy,

int c,int lim) {
int x,y,xi,xf ;
p.sp = 1 ;
p.x = calloc(1000,sizeof(int)) ;
p.y = calloc(1000,sizeof(int)) ;
p.x[0] = xx ;
p.y[0] = yy ;
setcolor(c) ;
while ( p.sp != 0 ) {
xi = xf = x = p.x[p.sp-1] ;
y = p.y[p.sp-1] ;
x++ ;
cp = getpixel(x,y) ;
while ( cp != lim ) {
xf = x ;
x++ ;
cp = getpixel(x,y) ; }
x = p.x[p.sp-1]-1 ;
cp = getpixel(x,y) ;
while ( cp != lim ) {
xi = x ;
x-- ;
cp = getpixel(x,y) ; }
line(xi,y,xf,y) ;

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009
Algorithmique de base de l'Infographie Page 31 of 31
p.sp-- ;
x = xf ;
while ( x >= xi ) {
cp = getpixel(x,y+1) ;
while ( ((cp == lim) || (cp == c))
&& (x >= xi) ){
x-- ;
cp = getpixel(x,y+1) ; }
if ( (x >= xi) && (cp != lim)
&& (cp != c) ) {
p.x[p.sp] = x ;
p.y[p.sp] = y+1 ;
p.sp++ ; }
cp = getpixel(x,y+1) ;
while ( ( cp != lim )
&& ( x >= xi ) ) {
x-- ;
cp = getpixel(x,y+1) ; } }
x = xf ;
while ( x >= xi ) {
cp = getpixel(x,y-1) ;
while ( ((cp == lim) || (cp == c))
&& (x >= xi) ){
x-- ;
cp = getpixel(x,y-1) ; }
if ( (x >= xi)
&& (cp != lim)
&& (cp != c) ) {
p.x[p.sp] = x ;
p.y[p.sp] = y-1 ;
p.sp++ ; }
cp = getpixel(x,y-1) ;
while ( ( cp != lim )
&& ( x >= xi ) ) {
x-- ;
cp = getpixel(x,y-1) ; } } }
free(p.x) ;
free(p.y) ;
}

file://C:\Inetpub\Raphaello\Ig\Algorithme\Algorithmique.htm 15/08/2009