Quel est le meilleur algorithme de «remplissage de seau»?

Je suis assez nouveau dans le traitement d'image et je travaille actuellement sur une application semblable à de la peinture qui comportera un remplissage de seau. Cependant, je n'ai aucune idée du meilleur algorithme pour un remplissage de compartiment.

J'ai implémenté un exemple que j'ai trouvé sur ce site , cependant, il a rencontré des problèmes de boucle infinie lorsqu'un utilisateur a essayé de remplir une zone qui avait déjà été remplie avec la même couleur.

Je travaille actuellement autour de ce problème en remplissant gauche, droite, haut et bas; cependant, je l'ai fait pour qu'une fois qu'un pixel a été rempli à gauche, il ne puisse pas se remplir à droite, ce qui signifie des formes telles que:

ne sera pas rempli correctement si l'outil de godet est utilisé au point rouge.

Par conséquent, j'espère que quelqu'un connaît un algorithme ou un lien vers celui qui résoudra tous ces problèmes.

Informations supplémentaires: Cela sera implémenté en utilisant Javascript comme outil de peinture. Il sera utilisé en ligne en utilisant l'élément Canvas.

Il semble que vous recherchiez ce que l'on appelle un algorithme de remplissage d'inondation. C'est peut-être pourquoi vous n'en avez pas trouvé des tonnes d'exemples. Il existe plusieurs méthodes Flood Fill répertoriées sur la page Wikipedia pour l'algorithme . Je recommande fortement l'une des méthodes non récursives et «en file d'attente».

Je fais actuellement la même chose. Cependant, lorsque j'ai rencontré le problème que vous signalez, j'ai opté pour simplement mettre fin à la fonction si l'outil a été cliqué sur une zone de la même couleur que vous essayez de peindre (cela semble également être le comportement de ms-paint) .

La méthode en file d'attente doit être extrêmement intuitive pour toute personne ayant une certaine expérience en programmation.

Si la peinture de la zone entourant un point de la même couleur que votre peinture vous inquiète, vous pouvez:

• vérifiez la couleur d'arrière-plan.
• recherchez le bord du point de même couleur sur lequel vous avez cliqué.
• mettre en file d'attente les points environnants sur place.
• procéder à une exécution normale en utilisant cette (dans ce cas) la file d'attente remplie de points blancs.

Si vous le souhaitez, vous pouvez consulter mon code (assez embarrassant) ici .

C'est loin d'être rapide mais ça marche bien ...