非递归实现Flood Fill算法？ [英] Non-recursive implementation of Flood Fill algorithm?

问题描述

我正在用Java开发一个小型绘图应用程序。我正在尝试通过实施Flood Fill算法来创建桶填充工具。

I'm working on a small drawing application in Java. I'm trying to create a 'bucket-fill' tool by implementing the Flood Fill algorithm.

我尝试使用递归实现，但这是有问题的。无论如何，我在网上搜索了一下，看来为此目的，建议该算法的非递归实现。

I tried using a recursion implementation, but it was problematic. Anyway, I searched around the web and it seems that for this purpose, a non-recursive implementation of this algorithm is recommended.

所以我问你：

你能描述洪水填充算法的 非递归实现吗？一个实际的代码示例，一些伪代码甚至是一般性的解释都将受到欢迎。

Could you describe a non-recursive implementation of the Flood Fill algorithm? An actual code example, some pseudo-code, or even a general explanation will all be welcome.

我正在寻找最简单的或

（不必特定于Java）。

谢谢

推荐答案

我假设您有某种网格，您可以在其中收到

I'm assuming that you have some sort of a grid where you receive the coordinates of the location from where you would like to fill the area.

递归洪水填充算法是DFS。您可以执行BFS将其转换为非递归。

Recursive flood fill algorithm is DFS. You can do a BFS to convert it to nonrecursive.

基本上，两种算法的想法都相似。您有一个袋子，其中存放了尚未看到的节点。您从包中取出一个节点，然后将该节点的有效邻居放回包中。
如果袋子是一堆，您会得到一个DFS。

Basically the idea is similar in both the algorithms. You have a bag in which the nodes that are yet to be seen are kept. You remove a node from the bag and put the valid neighbors of the node back into the bag. If the bag is a stack you get a DFS. If it's a queue you get a BFS.

伪代码大致是这样。

flood_fill(x,y, check_validity)
   //here check_validity is a function that given coordinates of the point tells you whether
   //the point should be colored or not
   Queue q
   q.push((x,y))
   while (q is not empty)
       (x1,y1) = q.pop()
       color(x1,y1)

       if (check_validity(x1+1,y1))
            q.push(x1+1,y1)
       if (check_validity(x1-1,y1))
            q.push(x1-1,y1)
       if (check_validity(x1,y1+1))
            q.push(x1,y1+1)
       if (check_validity(x1,y1-1))
            q.push(x1,y1-1)

注意：请确保check_validity考虑了该点是否已着色。

NOTE: make sure that check_validity takes into account whether the point is already colored or not.

• DFS：深度优先搜索


• BFS：宽度优先搜索

这篇关于非递归实现Flood Fill算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！