J'utilise l'algorithme de remplissage de l'inondation récursif en Java pour remplir certaines zones d'une image. Avec de très petites images, cela fonctionne bien, mais quand de l'image devient plus grande, le JVM me donne une pile sur une erreur de flux.
C'est la raison pour laquelle je dois réilembler la méthode à l'aide d'un remplissage d'inondation avec ma propre pile. (J'ai lu que c'est la meilleure façon de le faire dans ce genre de cas)
Quelqu'un peut-il m'expliquer comment le coder? (Si vous n'avez pas le code à la main, le pseudo-code de l'algorithme ira bien)
J'ai lu beaucoup sur Internet, mais je n'ai pas très bien compris.
EDIT: J'ai ajouté mon code récursif merci!
4 Réponses :
Vous pouvez utiliser la file d'attente pour éliminer la récursive de l'algorithme de l'inondation. Voici quelques idées de base:
Le code ci-dessous est mon code Java pour résoudre un problème similaire mais différent de la détection de blob entrée de test: 
Mmmm je vois ... mais comment puis-je adapter votre code? J'ai besoin de peinture vert certaines zones, par exemple: toutes les zones noires de l'image. Merci pour tout!
Dans l'échantillon de code, le programme incrémente la valeur de la variable pixelcount . Peut-être que vous voulez setrgb à ce point à la place? En outre, il scanne toute la zone de l'image pour chaque blob. Vous voudrez peut-être remplir un seul blob, commencer à remplir à certains points.
Oui! Je comprends! Sans votre aide ne serait pas possible !! Juste je dois changer la ligne "pixelcount ++" par "img.setrgb (p.x, p.y, couleur.green.getrgb ());" et c'est tout! Je suis très reconnaissant!! Merci beaucoup!
Beau, je ne sais pas comment je n'avais pas pensé à cette solution. Travaillé parfaitement dans mon code!
Vous devriez renvoyer la dernière déclaration de l'inondation, la transformant en appel de la queue. Cela vous sauvera votre espace de pile.
La récursion de la queue peut toujours être traduite à un format itératif. Cela permettrait d'économiser encore plus d'espace de pile.
Un point important du remplissage des inondations est si vous traitez la profondeur de points d'abord ou d'une largeur d'abord. Profondeur Tout d'abord est la solution d'origine que vous regardiez à l'aide d'une pile, d'abord d'abord sont des algorithmes présentés ci-dessous à l'aide d'une file d'attente pour stocker le point. La différence est substantielle lors de la remplissage de grands espaces convexes. Une première méthode de largeur stocke sur une zone parfaitement convexe à peu près le bord du cercle (ou le bord de remplissage). Si vous utilisez une première méthode de profondeur, vous pouvez dans le pire des cas de magasin chaque pixel dans la zone Conxex, cela signifie que dans le pire des cas, une inondation d'images 1000x1000 remplie peut nécessiter 1000000 de cadres de pile.
Pour clarifier (CMIIW), une structure de données basée sur une pile (file d'attente FILO) serait d'abord - d'abord, remplissant d'un bord convexe intestin , Wheras Stack-basé sur la récursion serait la profondeur - premier. Une file d'attente FIFO , par comparaison, fonctionnerait de l'origine vers l'extérieur, chaque point étant traité dans l'ordre dans lequel elle est soumise. Les files d'attente FIFO ont tendance à avoir plus de frais généraux, si vous ne pouvez pas développer une tampon d'anneau avec la copie
Voici ma base de mise en œuvre sur les infos de cette page et d'autres recueillies sur le Web (testé et fonctionnant)
amusement; -)
Wikipedia: algorithme de remplissage d'inondation
Si vous deviez montrer votre code existant (ou un résumé de haut niveau de celui-ci), une personne pourrait être capable de vous dire comment l'écrire d'une manière qui n'est pas récursive, si c'est ce que vous êtes après.
Je suggère de choisir l'un des algorithmes basés sur la file d'attente présentés là-bas, ils sont plus faciles à mettre en œuvre qu'une solution basée sur la pile à mon avis.
Merci pour la réponse, j'ai essayé de mettre en œuvre avec l'explication de Wikipedia, mais je ne savais pas comment. C'est la raison pour laquelle je fais une question ici. Si quelqu'un pouvait me l'expliquer avec d'autres mots, je serai très reconnaissant.