algorithme de remplissage en 4 connexité (lent) -> image non remplie complètement

**piponux** · 17/12/2016, 08h03

Bonjour,
j'ai écrit une fonction de remplissage en 4 connexité, mais le résultat n'est pas "plein". Il y a beaucoup de pixels oubliés. Cela vient-il du fait qu'il s'agit d'une '4-connexité' et non d'un '8-connexité'?

Code c :

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
void flood_fill (image I, int x, int y, colour couleur_de_remplissage)
{
 int position_P1 = image_offset (I, x, y);
 
 fifo F = standard_empty_fifo_create (NULL, NULL, NULL, NULL);
 fifo_push (F, (void*) position_P1);
 
 
 int position_P_nord = 0;
 int position_P_sud = 0;
 int position_P_est = 0;
 int position_P_ouest = 0;
 
 int position_P_diagonale_haut_gauche = 0;
 int position_P_diagonale_bas_gauche = 0;
 int position_P_diagonale_haut_droite = 0;
 int position_P_diagonale_bas_droite = 0;  
 
 
 while (!is_fifo_empty (F))
  {
    /* 
   assert (position_P1 >= 0);
   assert (position_P_nord >= 0);
   assert (position_P_sud < I->h);
   assert (position_P_est < I->w);
   assert (position_P_ouest >= 0);
   */
 
   if (position_P_sud > I->h) position_P_sud = I->h - 1;
   if (position_P_nord < 0) position_P_nord = 0;
   if (position_P_est < 0) position_P_est = 0;
   if (position_P_ouest > I->w) position_P_ouest = I->w -1;
 
 
   position_P1 = (int) fifo_pop (F);   
 
 
 
 
   /*if ((I->pixel[position_P1] != c) && (I->pixel[position_P1] == 0x000000FF)) return;*/
   /*if (I->pixel[position_P1] == 0x000000FF) return;*/
   if (I->pixel[position_P1] != couleur_de_remplissage) I->pixel[position_P1] = couleur_de_remplissage;
 
 
   position_P_nord = position_P1 - I->w;
   position_P_sud = position_P1 + I->w;
   position_P_est = position_P1 + 1;
   position_P_ouest = position_P1 - 1;
 
   position_P_diagonale_haut_gauche = position_P_nord - 1;
   position_P_diagonale_bas_gauche = position_P_sud - 1;
   position_P_diagonale_haut_droite = position_P_nord + 1;
   position_P_diagonale_bas_droite = position_P_nord + 1;  
 
/*
   if (position_P_diagonale_haut_gauche < 0) position_P_diagonale_haut_gauche = 0;
 
   if (position_P_diagonale_haut_droite > I->w) position_P_diagonale_haut_droite = I->w - 1;
   if (position_P_diagonale_haut_droite < 0) position_P_diagonale_haut_droite = 0;   
 
   if (position_P_diagonale_bas_droite > I->w) position_P_diagonale_haut_droite = I->w - 1;
   if (position_P_diagonale_bas_droite > I->h) position_P_diagonale_bas_droite = I->h - 1;   
 
   if (position_P_diagonale_bas_gauche < 0) position_P_diagonale_bas_gauche = 0;
   if (position_P_diagonale_bas_gauche > I->h) position_P_diagonale_bas_gauche = I->h -1;   
 
*/
 
   if ((I->pixel[position_P_nord] != couleur_de_remplissage) && (I->pixel[position_P_nord] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_nord);
 
   if ((I->pixel[position_P_sud] != couleur_de_remplissage) && (I->pixel[position_P_sud] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_sud);
 
   if ((I->pixel[position_P_est] != couleur_de_remplissage) && (I->pixel[position_P_est] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_est);
 
   if ((I->pixel[position_P_ouest] != couleur_de_remplissage) && (I->pixel[position_P_ouest] != 0x000000FF)) 
     fifo_push (F, (void*) position_P_ouest);
 
 
/*        
    if ((I->pixel[position_P_diagonale_haut_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_gauche);
 
   if ((I->pixel[position_P_diagonale_haut_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_droite);
 
 
   if ((I->pixel[position_P_diagonale_bas_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_gauche);
  
   if ((I->pixel[position_P_diagonale_bas_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_droite);
      
        
  */      
 
 
 
 
 
   fifo_remove(F);
 
  }
 
 fifo_destroy(&F);
 
}

**Matt_Houston** · 17/12/2016, 10h09

Code :

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

position_P_diagonale_bas_droite = position_P_nord + 1;

Il semble déjà qu'un bug se soit glissé ici.

**devbreizhbugs** · 17/12/2016, 15h49

Envoyé par Matt_Houston

Code :

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

position_P_diagonale_bas_droite = position_P_nord + 1;

Il semble déjà qu'un bug se soit glissé ici.

Il me semble que cette partie est commenté car il ne l'utilise pas en 4-conexités...

Moi je miserai plutot sur le fifo_remove ligne 100 qui n'as pas lieu d'être puisqu'un fifo_pop (ligne 36) est censé retiré l'élément de tête...
Cela dit, il me semble que le calcul
position_P_nord = position_P1 - I->w;
position_P_sud = position_P1 + I->w;
position_P_est = position_P1 + 1;
position_P_ouest = position_P1 - 1;
est faux pour est et ouest aux abord de l'image!... il est plus facile de passer par de la 2d(x,y) ...
Pourquoi ne pas simplement pusher un vecteur 2D et juste faire la conversion 1D pour l'accès au tableau?

**piponux** · 17/12/2016, 16h13

Bonjour et merci pour votre intérêt sur la question.

Effectivement, la position de la diagonale bas droite n'était pas bonne.
J'utilise la 4 connexité. Je commente la 8 connexité car j'ai des erreurs de segmentation en pagaille.

Et, je ne l'avais pas vu, mais c'est vrai, la fonction fifo_pop retire l'élément après qu'on l'ait récupéré. A la différence de fifo_remove, qui retire purement et simplement l'élément, sans qu'on l'ait récupéré.

Merci à tous deux, je reviendrai ici pour vous dire si j'ai réussi (ou pas) à faire tourner ma fonction de remplissage.

**piponux** · 17/12/2016, 18h14

Bon, voilà, en rajoutant le pixel en haut à gauche et le pixel en bas à droite, j'arrive presque à ce que je veux, sauf qu'il y a deux pixels non peints (à côté de chaque "fenêtre" - j'ai dessiné une maison - elle est pas belle ma maison ?)

ça ne marche toujours pas en 8 connexité.

Code c :

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
void flood_fill (image I, int x, int y, colour couleur_de_remplissage)
{
 int position_P1 = image_offset (I, x, y);
 
 fifo F = standard_empty_fifo_create (NULL, NULL, NULL, NULL);
 fifo_push (F, (void*) position_P1);
 
 
 int position_P_nord = 0;
 int position_P_sud = 0;
 int position_P_est = 0;
 int position_P_ouest = 0;
 
 int position_P_diagonale_haut_gauche = 0;
 int position_P_diagonale_bas_gauche = 0;
 int position_P_diagonale_haut_droite = 0;
 int position_P_diagonale_bas_droite = 0;  
 
 
 while (!is_fifo_empty (F))
  {
   assert (position_P1 >= 0);
   assert (position_P_nord >= 0);
   assert (position_P_sud < (I->h * I->w));
   assert (position_P_est < (I->w * I->h));
   assert (position_P_ouest >= 0);
 
   position_P1 = fifo_pop(F);
   fifo_remove(F);
 
   if (I->pixel[position_P1] != couleur_de_remplissage) I->pixel[position_P1] = couleur_de_remplissage;
 
 
   position_P_nord = position_P1 - I->w; 
   position_P_sud = position_P1 + I->w; 
   position_P_est = position_P1 + 1;     
   position_P_ouest = position_P1 - 1; 
 
   if ((I->pixel[position_P_nord] != couleur_de_remplissage) && (I->pixel[position_P_nord] != 0x000000FF))
     fifo_push (F, (void*) position_P_nord);
 
   if ((I->pixel[position_P_sud] != couleur_de_remplissage) && (I->pixel[position_P_sud] != 0x000000FF))
     fifo_push (F, (void*) position_P_sud);
 
   if ((I->pixel[position_P_est] != couleur_de_remplissage) && (I->pixel[position_P_est] != 0x000000FF))
     fifo_push (F, (void*) position_P_est);
 
   if ((I->pixel[position_P_ouest] != couleur_de_remplissage) && (I->pixel[position_P_ouest] != 0x000000FF))
     fifo_push (F, (void*) position_P_ouest);
 
 
 
   position_P_diagonale_haut_gauche = position_P1 - I->w - 1;
   position_P_diagonale_bas_droite = position_P1 + I->w + 1;  
 
   if ((I->pixel[position_P_diagonale_haut_gauche] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_haut_gauche] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_haut_gauche);
 
 
   if ((I->pixel[position_P_diagonale_bas_droite] != couleur_de_remplissage) && (I->pixel[position_P_diagonale_bas_droite] != 0x000000FF)) fifo_push (F, (void*) position_P_diagonale_bas_droite); 
 
  }
 
 fifo_destroy(&F);
 
}

**devbreizhbugs** · 17/12/2016, 20h12

Envoyé par piponux

Et, je ne l'avais pas vu, mais c'est vrai, la fonction fifo_pop retire l'élément après qu'on l'ait récupéré. A la différence de fifo_remove, qui retire purement et simplement l'élément, sans qu'on l'ait récupéré.
.

Ben supprime tes appels à fifo_remove alors!
Tes calculs de position sont toujours incorrects!

**piponux** · 17/12/2016, 20h41

Si je retire fifo remove j ai des erreurs de segmentation.

algorithme de remplissage en 4 connexité (lent) -> image non remplie complètement

C

Vue hybride

Discussions similaires

Partager

Partager