如何提高我的泛洪填充例程的性能？

Question

我在我的应用程序中实现了四路泛洪填充，伪代码如下

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return

它有点慢，有时会填满调用堆栈！我真的没能计算出这个算法的复杂度。

有没有人能提出更好的算法来实现它呢？

Answer 1

当前最先进的泛洪填充算法(从2006年左右开始)是基于找到连接组件的轮廓(最外边界)，将轮廓转换为水平像素游程(以及检测和移除连接组件中的内部孔洞)，然后填充像素游程。这样做的好处是大大减少了内存需求(和/或堆栈级)，而且速度更快(内部像素保证只读一次，写一次)。然而，这个算法并不简单。你需要阅读一些研究论文才能实现它。

Answer 2

我不能帮助你处理C#，因为我只在Delphi语言中做过，但是我可以帮助你解决调用堆栈的问题。诀窍是不要使用递归算法。相反，通过维护需要检查的点的堆栈，使用基于堆栈的方法。

基本上，您将“起始点”添加到堆栈(并更改其颜色)。然后，当堆栈不为空时，去掉堆栈中的最后一个点(即Pop it)。对所有4个方向(左、右、上、下)进行比较。如果任何相邻像素需要翻转到新颜色，则执行翻转，然后将该邻接点添加到堆栈中。在你的下一次循环中，堆栈上应该有更多的点。继续循环，直到堆栈为空。

Answer 3

它认为您处理的是一个图形，根据我的理解，您应该更改每个节点的颜色，并仅当目标颜色匹配时才用另一个节点替换它。

用Big O表示的这个算法的复杂度是O( 4^n )，所以我建议你尝试实现一个BFS算法，这样你就可以避免在没有changind的情况下离开未连接的节点，也可以避免在任何顶点上多次传递。这样，您应该能够在O( |E| + |V| )中执行，其中|E|是边的数量，|V|是顶点的数量。

这里是一个到wikipedia explanation的链接，而且它很简单，所以看看这个！

附言:如果你需要一个关于算法的had，我将非常乐意帮助你！