上次我们谈到如何使用深度优先搜索解决迷宫问题。这次,我们再来看看深度优先搜索的其他应用,来模仿 photoshop 的魔棒功能来填充颜色。使用扫描线填充算法(scan-line fill)会更快,这一节我们先介绍 floodfill 算法。
填充之后的效果图如下,三角形中央原来为红色,经过 floodfill 填充算法,变为青色。
floodfill 算法是在深度优先搜索的基础上稍加改动,floodfill 算法会递归地填充某个方向上的颜色,如果遇到障碍或者已经经过的像素点,就会回退到上一步选择其他方向继续填充颜色。与迷宫问题不同的是,迷宫有明确的起点与终点,深度优先搜索只需找到一条行得通的道路即可。而 floodfill 填充算法则不同,floodfill 算法会把封闭区域内每一个像素点全都填充完毕之后结束。
简单的伪代码如下,floodfill 算法依序向前后左右四个方向尝试填充颜色。如果遇到阻碍就退回上一步,否则填充这个像素点。
def floodfill(direction):
if block:
return
else:
fill(direction)
floodfill(left)
floodfill(right)
floodfill(up)
floodfill(down)
与深度优先搜索相比,floodfill 算法在代码上的改动较小。与深度优先搜索类似,也是继承 Maze 类。Maze 类的介绍,点击链接查看。
可以看到,在代码上与深度优先搜索的区别在于,其一没有结束条件,直到堆栈中没有状态点再停止填充颜色;其二,要向所有经过的点填充颜色。
class FloodFill(Maze):
def _fill(self, pause, plot):
stack = Stack()
initial = self._Node(self._start, None)
marked = {initial.state}
stack.push(initial)
while stack:
parent = stack.pop()
state = parent.state
# 填充颜色
self._grid[state] = Cell.PATH
if plot:
self._draw(pause)
children = self._success(state)
for child in children:
if child not in marked:
marked.add(child)
stack.push(self._Node(child, parent))
def show_path(self, pause = 0.5, *, plot = True):
self._fill(pause, plot=plot)
下一步,我们要使用 opencv 导入 bmp 图像,填充颜色。
import cv2
file = 'D://QQPCMgr/Desktop/test1.bmp'
bmp = cv2.imread(file)[:, :, 0]
d = FloodFill(rows=100, cols=100, start=MazeLocation(145, 145), end=MazeLocation(146, 146), grid=bmp)
d.draw()
d.show_path(plot=False)
d.draw()
将设置 plot 参数为 True,pause 参数为 0.00001,可以观察填充颜色的轨迹 。需要安装 opencv。
需要注意的是,选择的起始点 start 与 结束点 end 必须在密闭区域之内。
import cv2
file = 'D://QQPCMgr/Desktop/test1.bmp'
bmp = cv2.imread(file)[:, :, 0]
d = FloodFill(rows=100, cols=100, start=MazeLocation(145, 145), end=MazeLocation(146, 146), grid=bmp)
# d.draw()
d.show_path(pause=0.00001)
d.draw()