remplissage

**Psycos** · 25/01/2006, 09h48

J'aimerai savoir comment remplir une image bmp en noir et blanc, en ayant juste un contour d'une forme. Je voudrais remplir l'interieur de la forme.

Exemple :

**fearyourself** · 25/01/2006, 10h13

C'est plutôt une question à demander dans le forum algorithmique puisque si tu ne sais pas comment le faire, tu n'es pas encore au point pour l'implémenter en C.

Avant même de répondre à un algorithme, est-ce que tu as résolu comment ouvrir une image bmp, comment savoir la couleur d'un pixel, comment modifier une couleur?

Sans cela, ce n'est pas encore la peine de chercher un algorithme... Ensuite, il faut savoir si tu veux un algorithme rapide ou est-ce que l'algorithme naïf te suffirait...

Si la figure est fermée, ceci peut marcher

Pour une image IM
Pour chaque colonne,
Récupérer dans min la position inférieure de la figure (ie tel que IM[min] = noir et que pour tout 0<=i<min, M[ i ] soit blanc).
Récupérer dans max la position supérieure de la figure (ie tel que IM[max] = noir et que pour tout max<i<Nbr de lignes de l'image, M[ i ] soit blanc).
Colorier tous les pixels M [ i ] avec min < i < max en noir

Jc

**Psycos** · 25/01/2006, 10h25

On a deja reussi a optenir le contour de la forme, on veu juste remplir l'interieur de la forme. La methode ke tu as proposee ne fonctionne pas toujours, imagine si tu avai cette forme :

**fearyourself** · 25/01/2006, 10h34

Exact, à ce moment il faut faire un peu plus de travail pour chercher l'intérieur...

- Soit tu te débrouilles pour que pendant le parcours en colonne tu saches si tu ressors de la figure (en repassant sur un ou plusieurs pixels noirs) et lorsque tu reviens dedans (en repassant sur un ou plusieurs pixels noirs)

Soit tu te débrouilles pour trouver un point qui est dans la figure et tu fais une version récursive/itérative avec pile qui colories tous les points autour et boucle tant qu'il existe un point qui n'a pas été colorié... Cela marche bien sûr si de n'importe quel point dans la figure, tu peux accéder à n'importe quel autre point dans la figure sans ressortir de la figure...

Jc

**fearyourself** · 25/01/2006, 10h53

Quelques bons liens sur le sujet:

http://www.cs.uvm.edu/~snapp/teachin...anlinefill.pdf

http://www.codeproject.com/gdi/QuickFill.asp

Jc

**j.p.mignot** · 25/01/2006, 19h04

Cela me semble facile.
Il suffit de calculer l'aire inluse via une relation du type
0.5 * abs(somme (xdy-ydx) )
et de voir si l'adjonction d'un point supplémentaire accroit ou décroit cette aire.
J'ai déjà commenté sur toutes une série de posts ce sujet. Il a fait l'objet de nombreuses reflexions et je pense qu'1 solotion raisonnable peut y être trouvée.

**Psycos** · 25/01/2006, 19h54

Merci je vais chercher une solution.

**Hephaistos007** · 25/01/2006, 20h15

Peut-etre qu'il suffit de créer un procedure de coloriage qui colorie un pixel si celui-ci n'est pas déjà colorié. La procedure de coloriage se rappelle récursivement dans toutes les directions (8 en tout). Cette procèdure doit être lancée la première fois sur un pixel quelconque intérieur à la forme. C'est une sorte de coloriage par "inondation".

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
procedure Colorier(pixel currentPix, Couleur c)
debut
 
  si non estDejaColorie(currentPix) alors
         currentPix <- c; 
 
         Colorier(haut(currentPix), c);
         Colorier(bas(currentPix), c);
         Colorier(gauche(currentPix), c);
         Colorier(droite(currentPix), c);
         Colorier(diagHG(currentPix), c);
         Colorier(diagHD(currentPix), c);
         Colorier(diagBG(currentPix), c);
         Colorier(diagBD(currentPix), c);
 
  finsi;
 
fin;

PS : Cela doit marcher si la bordure de ta forme fais au moins 2 pixels d'épaisseur ce qui a l'air le cas d'après ton image.

**LLB** · 25/01/2006, 23h49

Oui, la méthode proposée par Hephaistos007 est un algo de remplissage classique. On peut aussi limiter à 4 appels récursifs (en supprimant les diagonales), le résultat sera identique (sauf cas particuliers).

Pour des raisons de performances, faire tant d'appels récursifs n'est pas toujours une bonne idée, la pile prend cher.

Je conseille de faire le parcours de manière itérative, en utilisant une pile ou une file.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
f.enfile(currentPix);
tant que f n'est pas vide, faire :
  currentPix = f.défile();
  colorier(currentPix);
  f.enfile(haut(currentPix));
  f.enfile(bas(currentPix));
  f.enfile(gauche(currentPix));
  f.enfile(droite(currentPix));
fin tant que

En faisant bien sûr une vérification pour éviter les boucles infinies (le mieux est de mettre un booléen dans la matrice).