Python 中的洪水填充
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19839947/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Flood Fill in Python
提问by Waldema
I'm complitely new to Flood Fill algorithm. I checked it out from Wikipedia (http://en.wikipedia.org/wiki/Flood_fill). But didn't become that much wiser. I'm trying to use it in following situation. I have a matrix:
我完全不熟悉 Flood Fill 算法。我从维基百科 ( http://en.wikipedia.org/wiki/Flood_fill) 中查看了它。但并没有变得那么聪明。我正在尝试在以下情况下使用它。我有一个矩阵：
matrix = [["a", "a", "b", "a", "a", "b"],
["a", "b", "b", "a", "b", "b"],
["b", "a", "b", "a", "a", "b"],
["b", "a", "b", "a", "b", "b"],
["a", "a", "b", "a", "a", "a"],
["a", "b", "b", "a", "a", "b"]]
Then I let user to decide one point from matrix. If in that given point is "b"nothing is done. In the other case if in the given point is "a"I want to change that given point and all surrounding or connected points with "a"to "c" with help of flood fill algorithm.
然后我让用户从矩阵中决定一点。如果在那个给定的点"b"什么都不做。在另一种情况下，如果在给定的点是"a"我想在洪水填充算法的帮助下将该给定点和所有周围或连接的点"a"更改为“c”。
For example let's say user decides matrix[0][0]. Then new matrix would be:
例如，假设用户决定矩阵 [0][0]。那么新矩阵将是：
matrix = [["c", "c", "b", "a", "a", "b"],
["c", "b", "b", "a", "b", "b"],
["b", "a", "b", "a", "a", "b"],
["b", "a", "b", "a", "b", "b"],
["a", "a", "b", "a", "a", "a"],
["a", "b", "b", "a", "a", "b"]]
Let's continue that example and say user decieds new point, matrix[3][1]. Then we would have:
让我们继续这个例子，假设用户决定了新的点，matrix[3][1]。那么我们将有：
matrix = [["c", "c", "b", "a", "a", "b"],
["c", "b", "b", "a", "b", "b"],
["b", "c", "b", "a", "a", "b"],
["b", "c", "b", "a", "b", "b"],
["c", "c", "b", "a", "a", "a"],
["c", "b", "b", "a", "a", "b"]]
I'm trying to build a function floodfill(matrix, x, y) and so far I have come up with this:
我正在尝试构建一个函数 floodfill(matrix, x, y) 到目前为止我已经想出了这个：
def floodfill(matrix, x, y):
if matrix[y][x] == "b":
return matrix
elif matrix[y][x] == ".":
stack = []
Do you have a way to lead me to proceed? Tried to look on flood fill examples on here SOF but they seemed not to fit my situation. At least I wasn't able to apply those examples to my code. Flood fill does not seem to be that popular subject here... But again, help would be highly appreciated!
你有办法引导我继续吗？试图查看 SOF 上的洪水填充示例，但它们似乎不适合我的情况。至少我无法将这些示例应用到我的代码中。洪水填充在这里似乎不是那么受欢迎的主题……但同样，我们将非常感谢您的帮助！
采纳答案by amit
Well, the idea of flood fill is:
那么，洪水填充的想法是：
- Check if the point meet the criteria.
- If it is, change it to "c" (in your case) - and invoke flood fill on all surrounding cells.
- 检查点是否符合条件。
- 如果是，请将其更改为“c”（在您的情况下） - 并在所有周围的单元格上调用洪水填充。
python-like pseudo code:
类似python的伪代码：
def floodfill(matrix, x, y):
#"hidden" stop clause - not reinvoking for "c" or "b", only for "a".
if matrix[x][y] == "a":
matrix[x][y] = "c"
#recursively invoke flood fill on all surrounding cells:
if x > 0:
floodfill(matrix,x-1,y)
if x < len(matrix[y]) - 1:
floodfill(matrix,x+1,y)
if y > 0:
floodfill(matrix,x,y-1)
if y < len(matrix) - 1:
floodfill(matrix,x,y+1)
回答by Zvika
There are several implementations of the flood fill algorithm in image processing libraries for Python. I'm aware of two: skimage.segmentation.floodand OpenCV's floodFill. The former is implemented in Python using an algorithm similar to the one in amit's answer above. The latter is implemented in C++ using a conceptually similar algorithm, but without recursion, making it much more efficient (about 25x for large images).
在 Python 的图像处理库中有几种洪水填充算法的实现。我知道两个：skimage.segmentation.flood和OpenCV 的 floodFill。前者是在 Python 中使用类似于上面 amit 回答中的算法实现的。后者是在 C++ 中使用概念上类似的算法实现的，但没有递归，因此效率更高（大图像约为 25 倍）。
To use OpenCV's floodFill, you'd need to convert your matrix to an np.array of integers, which could be done as follows:
要使用 OpenCV 的 floodFill，您需要将矩阵转换为一个 np.array 整数，这可以按如下方式完成：
import numpy as np
import cv2
matrix_np = np.asarray(matrix)
numeric_matrix = np.where(matrix_np=="a", 255, 0).astype(np.uint8)
mask = np.zeros(np.asarray(numeric_matrix.shape)+2, dtype=np.uint8)
start_pt = (y,x)
if matrix_np[start_pt]:
cv2.floodFill(numeric_matrix, mask, start_pt, 255, flags=4)
mask = mask[1:-1, 1:-1]
matrix_np[mask==1] = "c"
matrix = matrix_np.tolist()
With the example matrix you gave above and x,y=(0,0), this will set matrixto
使用上面给出的示例矩阵和 x,y=(0,0)，这将设置matrix为
[['c', 'c', 'b', 'a', 'a', 'b'],
['c', 'b', 'b', 'a', 'b', 'b'],
['b', 'a', 'b', 'a', 'a', 'b'],
['b', 'a', 'b', 'a', 'b', 'b'],
['a', 'a', 'b', 'a', 'a', 'a'],
['a', 'b', 'b', 'a', 'a', 'b']]
