Remplir en "pot de peinture" un morceau de grille

Bonjour !

Je cherche un peu d'aide pour une fonction de remplissage qui fonctionnerais comme le pot de peinture des logiciels graphiques.

J'ai réussi à avoir un code fonctionnel mais si la zone à remplir est trop grande j'ai droit à un joli StackOverflowError. Ce n'est pas un problème de "boucle infinie" mais de trop grande récursivité (si je prend une zone plus petite tout vas bien, mais je doit pouvoir gérer de grandes zones)

Ma question étant : quelqu'un pourrait convertir ce code pour obtenir la même chose en non-récursif ?

Code:

---

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

public void fillGrid(Point point) { // grid est un boolean[][] sans limite de taille fillBlockedArea(point, !grid[point.x][point.y]); }   private void fillGrid(Point point, boolean set) { grid[point.x][point.y] = set; if (point.x - 1 > 0) { if (grid[point.x - 1][point.y] != set) fillGrid(new Point(point.x - 1, point.y), set); } if (point.x + 1 < grid.length) { if (grid[point.x + 1][point.y] != set) fillGrid(new Point(point.x + 1, point.y), set); } if (point.y - 1 > 0) { if (grid[point.x][point.y - 1] != set) fillGrid(new Point(point.x, point.y - 1), set); } if (point.y + 1 < grid[point.x].length) { if (grid[point.x][point.y + 1] != set) fillGrid(new Point(point.x, point.y + 1), set); } }

---

Cette grille me sert à avoir un rendu graphique en pixel par pixel, donc voilà un exemple de ce qui est voulu (les pixels noirs sont à true et les autres à false) :
Pièce jointe 167319
(Pour résumer : cette fonction fonctionne mais il faudrait un équivalent non-récursif)

Bonjour,

L'ennui est que même si tu déportes le problème, il te faudra quand même gérer une pile même si ce n'est plus celle du système. Certes, tu pourras toujours faire croître celle-ci avec des allocations successives, mais le problème intrinsèque reste le même : un parcours d'arbre. Enfin, c'est même un parcours de graphe en général puisque les différentes ramifications de ta figure peuvent se rejoindre un peu plus loin.

Par contre, ce n'est vrai qu'à partir du moment où tu considères que la figure initiale est inconnue. Si, en revanche, tu disposes des vertex servant à la tracer, alors tu peux directement calculer sans trop de difficultés quels sont les pixels qui se trouvent à l'intérieur ou à l'extérieur de la forme.

Sinon, tu pourrais le faire en plusieurs "passes" mais ca prendra beaucoup beaucoup plus de temps (surtout si la grille est grande) donc je le déconseillerai mais ca n'utilisera pas de mémoire ou d'empilage sauf qu'il te faudra garder en mémoire les pixels de la forme de base.

- Tu remplis le pixel cliqué puis

- Tu fais un passe sur tout les pixels de la grille et tu regardes si chacun des pixels non remplis est a coté d'un déjà remplis et alors tu le remplis en prenant en compte les pixels de la forme de base pour les esquiver (sinon ca pendra dehors et dans la forme).

- Tu boucles jusqu'à ce que tu n'arrive plus à mettre de pixel dans une passe ce qui signifiera logiquement que tu auras remplis ta zone remplissable.

Une piste : utiliser l'interface Shape et la méthode fill.

1) repérer tous les points en noir et les stocker dans un tableau
3) Créer un chemin GeneralPath
4) Créer la forme en remplissant le chemin avec les points
5) Fermer la forme
6) On rempli la forme avec la méthode fill de Graphics2D

Bonjour,

Je te conseil d'aller faire un petit tour sur l'article de wikipdia sur l'Algorithme de remplissage par diffusion

Celui-ci détail le pseudo-code à utilisé pour l'Algorithmes à pile explicite, qui contourne justement le problème problème de la pile d'appel.

Citation:

---

Envoyé par Wikipédia Pseudo-code

remplissage4(pixel, colcible, colrep)
début
Soit P une pile vide
si couleur(pixel) ≠ colcible alors sortir finsi
Empiler pixel sur P
Tant que P non vide
faire
Dépiler n de P
couleur(n) ← colrep
si couleur(n nord) = colcible alors Empiler n nord sur P finsi
si couleur(n sud) = colcible alors Empiler n sud sur P finsi
si couleur(n est) = colcible alors Empiler n est sur P finsi
si couleur(n ouest)= colcible alors Empiler n ouest sur P finsi
fintantque
fin

---

L'article parle aussi d'autres optimisations possibles, mais je ne pense pas que cela soit nécessaire dans ton cas.

Cordialement,
Patrick Kolodziejczyk.

Source :
http://fr.wikipedia.org/wiki/Algorit..._par_diffusion

Mais en fait, c'est une image dans un JPanel ?

Salut,

Voilà un POC d'une fonction de remplissage de forme dans une grille purement itérative (ma grille n'est pas une grille de booléen, mais c'est facilement adaptable) :

Code:

---

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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504

public class FloodFill {   public static final int SLOW = 10; // utilisé pour ralentir le remplissage, pour le voir progresser   public static final Color FILL_COLOR = Color.RED;   public static void main(String[] args) {   FloodFill test = new FloodFill();   AbsractShape testShape1 = new ShapeTest1(); AbsractShape testShape2 = new ShapeTest2(); AbsractShape testShape3 = new ShapeTest3(); AbsractShape testShape4 = new ShapeTest4(); AbsractShape[] shapes = { testShape1, testShape2, testShape3, testShape4 };   JFrame frame = new JFrame("Démo"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);   JPanel mainPanel = new JPanel(); mainPanel.setLayout(new BorderLayout());     JPanel panel = new JPanel() { protected void paintComponent(java.awt.Graphics g) { super.paintComponent(g); testShape1.draw(g.create(10,10, testShape1.getWidth(), testShape1.getHeight())); testShape2.draw(g.create(120,10, testShape2.getWidth(), testShape2.getHeight())); testShape3.draw(g.create(10,120, testShape3.getWidth(), testShape3.getHeight())); testShape4.draw(g.create(120,120, testShape4.getWidth(), testShape4.getHeight())); } }; mainPanel.add( panel, BorderLayout.CENTER);   JPanel buttonPanel = new JPanel();   JCheckBox speed = new JCheckBox("Ralentir"); speed.addChangeListener((e)-> test.setSpeed( speed.isSelected()?SLOW:0 ));   JButton buttonFillIn = new JButton("Remplir (in)");   JButton buttonFillOut = new JButton("Remplir (out)");   buttonPanel.add( speed ); buttonPanel.add( buttonFillIn ); buttonPanel.add( buttonFillOut ); mainPanel.add( buttonPanel, BorderLayout.SOUTH);   buttonFillIn.addActionListener( e -> fill(test, shapes, buttonFillIn, buttonFillOut, panel, true) );   buttonFillOut.addActionListener( e -> fill(test, shapes, buttonFillIn, buttonFillOut, panel, false) );   frame.getContentPane().add(mainPanel);   frame.setSize(400, 300); frame.setLocationRelativeTo(null); frame.setVisible(true);   }   private static void fill(FloodFill floodFill, AbsractShape[] shapes, JButton buttonFillIn, JButton buttonFillOut, Component panel, boolean paintIn) { buttonFillIn.setEnabled(false); buttonFillOut.setEnabled(false);   new Thread() {   @Override public void run() { for(AbsractShape shape : shapes) { shape.clear(); } panel.repaint(); for(AbsractShape shape : shapes) { floodFill.fill( panel, shape.getGrid(), paintIn?shape.getInPoint():shape.getOutPoint(), FILL_COLOR); }   SwingUtilities.invokeLater(() -> { buttonFillIn.setEnabled(true); buttonFillOut.setEnabled(true); });   }   }.start();   }   private long speed;   public void setSpeed(long speed) { this.speed=speed; }   public void fill(Component component, int[][] grid, Point fillPoint, Color fill) { final int startx = fillPoint.x; final int starty = fillPoint.y; final int height = grid.length; final int width; int maxwidth = 0; for (int y = 0; y < height; y++) { int currentWidth = grid[y].length; if (currentWidth > maxwidth) { maxwidth = currentWidth; } } width = maxwidth;   final int originalColor = grid[starty][startx]; final int fillColor = fill.getRGB(); int minx=width; int maxx=0; int miny=height; int maxy=0; for(int x=0; x<width; x++) { for( int y=0; y<height; y++) { if ( grid[y][x]!=originalColor ) { if ( x<minx) minx=x; if ( x>maxx) maxx=x; if ( y<miny) miny=y; if ( y>maxy) maxy=y; } } }   if ( minx==maxx ) { // cas particulier : ligne verticale if ( startx==minx ) { // draw in for(int y=miny; y<=maxy; y++) { fill(component, grid, startx, y, fillColor); } } else { // draw out for(int y=0; y<height; y++) { for(int x=0; x<width; x++) { if ( x!=minx || y<miny || y>maxy ) { fill(component, grid, x, y, fillColor); } } } } } else if ( miny==maxy ) { // cas particulier : ligne horizontal if ( starty==miny ) { // draw in for(int x=minx; x<=maxx; x++) { fill(component, grid, x, starty, fillColor); } } else { // draw out for(int y=0; y<height; y++) { for(int x=0; x<width; x++) { if ( y!=miny || x<minx || x>maxx ) { fill(component, grid, x, y, fillColor); } } } } } else {   // + 2 pour ajouter des bordures afin de simuler un rectangle autour (pour le remplissage à l'extérieur de la forme) int[][] nbgrid = new int[height+2][width+2]; for(int y=0; y<nbgrid.length; y++) { for(int x=0; x<nbgrid[y].length; x++) { if ( x==0 || y==0 || x==nbgrid[y].length-1 || y==nbgrid.length-1 ) { nbgrid[y][x]=1; } else if ( x>0 && x-1<width && y>0 && y-1<height ) { if ( grid[y-1][x-1]!=originalColor ) { // on copie les points de la bordure nbgrid[y][x]=1; } } } }   Point p = new Point(startx+1, starty+1); int color = -1; while (color < 0) { if ( checkBounds(p.x,p.y,nbgrid) ) { nbgrid[p.y][p.x] = color--; } if (!search(nbgrid, p, 0)) { if ( checkBounds(p.x, p.y, nbgrid) ) { nbgrid[p.y][p.x] = 1; if ( nbgrid[p.y][p.x]==1 ) { fill(component, nbgrid, grid, p, fillColor); } } color += 2; search(nbgrid, p, color); } }   }     }   private void fill(Component component, int[][] nbgrid, int[][] grid, Point p, int fillColor) { if ( nbgrid[p.y][p.x]==1 ) { fill(component, grid, p.x-1, p.y-1, fillColor); } }   private boolean search(int[][] nbgrid, Point p, int color) { if ( checkBounds(p.x-1, p.y, nbgrid) ) { if (nbgrid[p.y][p.x-1] == color) { p.x--; return true; } } else { return false; } if ( checkBounds(p.x+1, p.y, nbgrid) ) { if (nbgrid[p.y][p.x+1] == color) { p.x++; return true; } } else { return false; } if ( checkBounds(p.x, p.y-1, nbgrid) ) { if (nbgrid[p.y-1][p.x] == color) { p.y--; return true; } } else { return false; } if ( checkBounds(p.x, p.y+1, nbgrid) ) { if (nbgrid[p.y+1][p.x] == color) { p.y++; return true; } } else { return false; } return false; }   private boolean checkBounds(int x, int y, int[][] grid) { return checkBounds(y, 0, grid.length) && checkBounds(x, 0, grid[y].length); }   private boolean checkBoundsIncluded(int x, int min, int max) { return x>=min && x<=max; }   private boolean checkBounds(int x, int min, int max) { return x>=min && x<max; }   private void fill(Component component, int[][] grid, int x, int y, int fillColor) { grid[y][x]=fillColor; component.repaint(); slowDown(); }     private void slowDown() { if ( speed>0 ) { try { Thread.sleep(speed); } catch (InterruptedException e) { throw new RuntimeException(e); } } }   private static abstract class AbsractShape {   private final static int BORDER_COLOR = Color.BLACK.getRGB(); // La couleur de bordure   private final int width; private final int height; private final int[][] grid; private final int[][] clearGrid;   public AbsractShape() { grid = createGrid(); height = grid.length; clearGrid = new int[height][]; int maxwidth = 0; for (int y = 0; y < height; y++) { int currentWidth = grid[y].length; clearGrid[y] = Arrays.copyOf(grid[y], currentWidth); if (currentWidth > maxwidth) { maxwidth = currentWidth; } } width = maxwidth; }   public final int[][] getGrid() { return grid; }   /**                  * Le point de départ du remplissage à l'intérieur de la forme                  * @return                  */ public abstract Point getInPoint();   /**                  * Le point de départ du remplissage à l'extérieur de la forme                  * @return                  */ public abstract Point getOutPoint();   public void clear() { for (int y = 0; y < height; y++) { for( int x=0; x<width; x++) { grid[y][x]=clearGrid[y][x]; } } }   public final int getWidth() { return width; }   public final int getHeight() { return height; }   public Dimension getSize() { return new Dimension(width, height); }   protected int[][] createGrid() { BufferedImage image = createImage(); return grabArray(image); }   private int[][] grabArray(BufferedImage image) { final int[][] array = new int[image.getHeight()][image.getWidth()]; for(int y=0; y<array.length; y++) { for(int x=0; x<array[y].length; x++) { int pixel = image.getRGB(x, y); array[y][x] = pixel<0?BORDER_COLOR:0; } } return array; }   /*Doit être une image ARGB, ou les lignes sont en Color.WHITE */ protected abstract BufferedImage createImage();   public final void draw(Graphics graphics) { final BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB); final int[] pixels = ((DataBufferInt) image.getRaster().getDataBuffer()) .getData(); for (int y = 0; y < grid.length; y++) { for (int x = 0; x < grid[y].length; x++) { pixels[y * width + x] = grid[y][x]; } } graphics.drawImage(image, 0, 0, null); }   }   public static class ShapeTest1 extends AbsractShape {   @Override protected BufferedImage createImage() { BufferedImage image = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB); Graphics graphics = image.createGraphics(); try { graphics.setColor(Color.WHITE); final int[] px = new int[]{20, 30, 40, 50, 60, 60, 50, 60, 50, 40, 30, 20, 10,}; final int[] py = new int[]{10, 10, 20, 10, 20, 30, 40, 50, 60, 60, 50, 99, 99}; graphics.drawPolygon( px, py, px.length);   return image; } finally { graphics.dispose(); } }   @Override public Point getInPoint() { return new Point(50,50); }   @Override public Point getOutPoint() { return new Point(5,5); }   }   public static class ShapeTest2 extends AbsractShape {   @Override protected BufferedImage createImage() { BufferedImage image = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB); Graphics graphics = image.createGraphics(); try { graphics.setColor(Color.WHITE); graphics.drawRect(10, 10, 80, 80); graphics.drawRect(30, 30, 20, 20); return image; } finally { graphics.dispose(); } }   @Override public Point getInPoint() { return new Point(20,20); }   @Override public Point getOutPoint() { return new Point(40,40); }     }   public static class ShapeTest3 extends AbsractShape {   @Override protected BufferedImage createImage() { BufferedImage image = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB); Graphics graphics = image.createGraphics(); try { graphics.setColor(Color.WHITE);   graphics.drawLine(10,10, 70, 10);   return image; } finally { graphics.dispose(); } }   @Override public Point getInPoint() { return new Point(20,10); }   @Override public Point getOutPoint() { return new Point(60,60); }   }   public static class ShapeTest4 extends AbsractShape {   @Override protected BufferedImage createImage() { BufferedImage image = new BufferedImage(100, 100, BufferedImage.TYPE_INT_ARGB); Graphics graphics = image.createGraphics(); try { graphics.setColor(Color.WHITE);   Area area = new Area(new Ellipse2D.Double(10,10,80,80));   area.subtract(new Area(new Ellipse2D.Double(30,30,40,40)));   area.subtract(new Area(new Rectangle2D.Double(45,0,10,60)));   ((Graphics2D)graphics).draw(area);   return image; } finally { graphics.dispose(); } }   @Override public Point getInPoint() { return new Point(30,30); }   @Override public Point getOutPoint() { return new Point(50,50); }   }   }

---

Merci Joel, ça marche super bien :) Le seul détail un peu dommage c'est que je ne comprend absolument rien ^^' Mais je m'amuse à remplir en slow-mo au moins =D

@Obsidian : Peut être mais la pile de java est très limitée. J'ai dût résoudre un problème similaire dans le même programme, sauf que c'était simple de passer en non-récursif (c'était une sorte de parcours de liste, donc un while résout tout) et maintenant que ma liste est 100fois + remplie que celle qui plantais en récursif, je n'ai toujours aucun lag/error

@wax78 : Sans connaitre la forme, je pourrais jamais savoir si je suis à coté, dedans ou même sur elle, concrètement je n'ai aucune idée de si la forme ressemble à quelque chose ou pas ^^'

@Népomucène : Je suis pas sûr que le shape apprécie des points qui n'ont aucun lien entre eux, ou alors c'est que j'ai rien compris à sont fonctionnement xD Par contre la convertion en image vas m'être utile pour autre chose sur le même objet :3
Là je demandais le pour le fill mais j'ai aussi un rectangle et un crayons (qui sont fonctionnels ;) ) et comme le crayon colore uniquement le pixel où se trouve le curseur, si on bouge trop vite le curseur ça fait des points éparpillé, donc je fait tracer des traits entre les point, ça devrait bien marcher, merci :)

@kolodz : C'est là que je me rend compte que la conversion était facile xD Merci pour le lien :)

@Népomucène : La grille est dans un objet, le coté graphique est un JLabel qui dessine cet objet avec sa grille

Il est difficile d'expliquer l'algorithme pas à pas, donc j'ai fait un petit programme pour montrer les étapes du remplissage sur une petite grille 10x10. En le faisant, je me suis aperçu qu'on pouvait simplifier l'algorithme (enlever des reliquats de mise au points que je pensais nécessaire au début, mais qui ne le sont pas au final - je précise lesquels dans ce petit programme). En plus, dans l'algorithme de l'autre programme je traite en cas particulier le cas de la lgine horizontale et la ligne verticale : ici, j'ai supprimé cette partie pour simplifier, mais l'algorithme ne fonctionne pas dans ce cas.

En gros :

• Je simplifie l'algorithme de floodfill en me fondant sur le fait qu'il n'y a que 2 couleurs : la couleur de bordure et la couleur de fond (une forme sur un fond). Dans l'autre programme, c'est le même principe mais il suffit que la couleur du point de départ soit d'une couleur différente du reste (la où on va s'arrêter de remplir.
• la pile est remplacée par des valeurs négatives (qui se décrementent plus on avance)
• On parcourt (on se déplace) tant qu'on peut (donc tant qu'on tape pas sur un point de couleur 1 = true, ou tant qu'on sort pas de la grille
• A chaque fois qu'on se déplace sur une case vide 0=false, on y met une valeur négative qui se décrémente donc, ce qui permettra de faire le chemin inverse (en fait, le principe est celui de l'algorithme du petit poucet, utilisé pour résoudre les labyrinthes)
• chaque fois qu'on revient en arrîère on remplit (parce qu'on compare une valeur dans la grille avec la valeur actuelle de color et qu'elles sont égales
• On fait +2 pour revenir lorsqu'on remplit, parce qu'il faut compter le point qu'on remplit, (le point précédent est par exemple -3, la color est à -4, donc il faut faire +2 pour retrouvé -3 pour remonter
• quand color est positif ou 0, alors on est revenu au début, on a tout rempli, donc on s'arrête (concrétisé par le while)
• au début, on commence avec color=-1, on fait color--, donc color==-2 : quand on fait color+2, donc obtient 0, donc l'appel de search cherche une case adjacente non remplie (=0), et s'y déplace dans ce cas. et on recommence à décrémenter, donc ça fait un nouveau chemin
• lorsqu'on revient en arrière on rempli, ce qui créé de plus en plus de cul de sac (voir ci-après)
• Le principe global peut se résumer en (j'ai mis les mêmes commentaires dans le code)
  
  1. je dépose une marque pour pouvoir connaitre le chemin que j'ai emprunté pour arriver jusque là
  2. si je ne trouve pas une case adjacente ==0 (je suis arrivé dans un cul de sac)
     
     1. je rempli
     2. je reviens en arrière
     3. je cherche à revenir sur le chemin que j'ai trouvé
  3. else implicite : si j'ai une case ==0, je me déplace à la recherche d'un cul de sac (une bordure)

On est obligé d'avoir un point de départ, parce qu'une forme a un intérieur, et un extérieur (Et il faut savoir ce qu'on veut remplir). Mais on peut déterminer automatiquement un point qui est à l'intérieur. C'est une autre algorithme: voir, par exemple, cette discussion sur le forum.

Dans le programme, j'affiche les positions avant (avec des parenthèses) et après déplacement (avec des crochets).

Le déroulement du programme permet de mieux comprendre ce qu'il se passe et comment fonctionne l'algorithme :

Code:

---

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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208

public class GridFloodFill {   private final static boolean X = true; // pour remplir plus facilement la grille au départ private final static boolean O = false; // pour remplir plus facilement la grille au départ   /**          *          * @param grid la grille avec la forme          * @param startx le x du point de remplissage          * @param starty le y du point de remplissage          * @return la grille avec la forme remplie          */ public static boolean[][] fill(boolean[][] grid, int startx, int starty) {   int etape = 1; // ça c'est juste pour la démo, pour afficher un numéro d'étape : ça peut être enlevé au final   // le tableau grid doit être un tableau rectangulaire (toutes les lignes font la meêm taille) // les cases à true correspondent aux contours de la forme, qui doit être évidemment fermée   // on convertit la grid en grille d'entier, ou true=1 et false=0 int[][] intgrid = new int[grid.length][grid[0].length]; for(int y=0; y< grid.length; y++) { for(int x=0; x<grid[y].length; x++) { if ( grid[y][x] ) { intgrid[y][x]=1; } } }   // dans l'autre code j'ajoute une bordure pour remplir aussi l'extérieur de la forme si le point de remplissage est extérieur // la bordure fait qu'on est donc toujours dans une forme fermée, quelque soit le point de remplissage // mais c'est un reliquat de mise au point (et j'avais pas le temps de l'enlever) // ici je l'ai enlevé, ça fonctionne sans   // la grille dans laquelle on aura le résultat boolean[][] resultgrid = new boolean[intgrid.length][intgrid[0].length];   // on copie la grille source dedans (on pourrait ne pas le faire pour avoir que le remplisage for(int y=0; y< grid.length; y++) { for(int x=0; x<grid[y].length; x++) { resultgrid[y][x] = grid[y][x]; } }   // on créé un point, ce qui va nous permettre de manipuler plus facilement // les mouvements dans la grille Point p = new Point(startx, starty); // on commence au point de remplissage   // color représente la couleur recherché (à remplacer) int color = -1; // on l'initialise à -1 (les valeurs négatives remplacent en quelque sorte la pile) while (color < 0) {   Point pa = new Point(p); // ça on peut enlever aussi : c'est juste pour tracer la position du point avant déplacement (si déplacement)   if ( checkBounds(p.x,p.y,intgrid) ) { intgrid[p.y][p.x] = color--; // je dépose une marque pour pouvoir connaitre le chemin que j'ai emprunté pour arriver jusque là } if (!search(intgrid, p, 0)) // si je ne trouve pas une case adjacente ==0 (je suis arrivé dans un cul de sac) {   if ( checkBounds(p.x, p.y, intgrid) ) { intgrid[p.y][p.x] = 1; // je rempli resultgrid[p.y][p.x]=true; } color += 2; // je reviens en arrière search(intgrid, p, color); // je cherche à revenir sur le chemin que j'ai trouvé } // else implicite : si j'ai une case ==0, je me déplace à la recherche d'un cul de sac (une bordure) displayTempGrid("Etape "+ etape++, color, pa, p, intgrid, resultgrid); }   return resultgrid;   }   /**          * Cherche le point adjacent à p de valeur color.          * Si un point est trouvé, p est ce point (x ou y est modifié) et la méthode retourne true, sinon false          */ private static boolean search(int[][] intgrid, Point p, int color) { if ( checkBounds(p.x-1, p.y, intgrid) ) { // si le point adjacent à gauche est dans la grille if (intgrid[p.y][p.x-1] == color) { // si le point adjacent à gauche à la "couleur" cherchée p.x--; // on se déplace à gauche return true; // on retourne true } } /* else { // on peut enlever ce test, ça fonctionne aussi (enlève le si tu veux simplifié) * // en fait, c'est un reliquat de mise au point (j'aurais dû l'enlever) return false; }*/ if ( checkBounds(p.x+1, p.y, intgrid) ) { if (intgrid[p.y][p.x+1] == color) { p.x++; return true; } } /*else { return false; }*/ if ( checkBounds(p.x, p.y-1, intgrid) ) { if (intgrid[p.y-1][p.x] == color) { p.y--; return true; } } /*else { return false; }*/ if ( checkBounds(p.x, p.y+1, intgrid) ) { if (intgrid[p.y+1][p.x] == color) { p.y++; return true; } } /*else { return false; }*/ return false; }   /**          *          * @return true si x,y est dans la grille          */ private static boolean checkBounds(int x, int y, int[][] intgrid) { return checkBounds(y, intgrid.length) && checkBounds(x, intgrid[y].length) ; }   private static boolean checkBounds(int v, int max) { return v>=0 && v<max; }   public static void main(String[] args) {   // grille 7x7 avec un simple carré boolean[][] grille = { { O, O, O, O, O, O, O, O, O, O }, { O, X, X, X, O, O, X, X, X, O }, { O, X, O, X, X, X, X, O, X, O }, { O, X, O, O, O, O, O, O, X, O }, { O, O, X, O, O, O, O, X, O, O }, { O, O, O, X, O, O, X, O, O, O }, { O, O, O, X, O, O, X, O, O, O }, { O, O, X, O, O, O, O, X, O, O }, { O, X, O, O, X, X, O, O, X, O }, { O, X, X, X, O, O, X, X, X, O }, { O, O, O, O, O, O, O, O, O, O }, };   displayGrid("Grille au départ",grille);   boolean[][] resultat = fill(grille, 3, 3); // point de départ = milieu //boolean[][] resultat = fill(grille, 0, 0); // point de départ en haut à gauche     displayGrid("Résultat final",resultat);   }   private static void displayGrid(String label, boolean[][] grid) { System.out.println(label); for(int y=0; y<grid.length; y++) { for(int x=0; x<grid[y].length; x++) { if ( grid[y][x] ) { System.out.print("X"); // case pleine (lignes de la forme) } else { System.out.print("."); // cases vide } } System.out.println(); } System.out.println(); }   private static void displayTempGrid(String label, int color, Point pa, Point p, int[][] grid, boolean[][] resultgrid) { System.out.println(label+" color="+color); for(int y=0; y<grid.length; y++) { for(int x=0; x<grid[y].length; x++) { if ( pa.x==x && pa.y==y ) { System.out.print("("); } else if ( p.x==x && p.y==y ) { System.out.print("["); } else { System.out.print(" "); } System.out.printf("%3d", grid[y][x]); if ( pa.x==x && pa.y==y ) { System.out.print(")"); } else if ( p.x==x && p.y==y ) { System.out.print("]"); } else { System.out.print(" "); } } System.out.println(); } System.out.println(); displayGrid("Résultat intermédiare "+label, resultgrid); }   }

---

Voilà, j'espère que c'est plus clair avec ces explications. S'il y a un autre aspect pour lequel tu voudrais des explications, qui ne concerne pas l'algorithme de remplissage, n'hésite pas.

Citation:

---

Envoyé par joel.drigo

Il est difficile d'expliquer l'algorithme pas à pas, donc j'ai fait un petit programme pour montrer les étapes du remplissage sur une petite grille 10x10.

---

Ca reveille la petite explication d'algo de 6h du mat :aie:

Citation:

---

Envoyé par hwoarang

Ca reveille la petite explication d'algo de 6h du mat :aie:

---

En fait, c'était plutôt pour me changer les idées après une nuit blanche à apprendre Javascript/JQuery. Dur en effet de faire une synthèse et de rédiger un truc un peu près compréhensible (c'est déjà pas évident quand je suis frais ;P) Du coup, en me relisant, je vois que j'ai fait plein de fautes :aie:

Hoooo ça me fait penser à Dijkstra :3

Tu sais que l'on a le droit d'étudier le jour ? On est pas obligé de faire une nuit blanche pour apprendre un langage x)

Citation:

---

Envoyé par joel.drigo

Du coup, en me relisant, je vois que j'ai fait plein de fautes :aie:

---

Je ne critiquais pas les fautes (ni meme le fond). J'ai juste trouvé amusant de voir un texte pour le coup plutot bien rédigé posté à 5h05 du mat :mrgreen:
Ca sent l'insomnie tout ca :aie: