我怎样才能提高我的洪水填充程序的性能？ [英] How can I improve the performance of my flood-fill routine?

问题描述

我实施四通洪水填写我的应用程序，伪code下面给出

I'm implementing the four way flood fill in my application, pseudo code given below

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

这是一种缓慢，有时充满调用堆栈！而我真的无法计算出这种算法的复杂度。

It's kind of slow and sometimes fills the call stack! And I'm really failed to calculate the complexity of this algorithm.

有人提出更好的算法可以实现它，好吗？

Can anyone suggest better algorithm to implement it, please?

推荐答案

目前的国家的最先进的的此时，floodFill算法（自2006年左右）的基础上寻找轮廓（最边界所连接的组件的），轮廓转换成水平像素运行（和检测，并从所连接的组件中除去内部孔），然后填充象素运行。其优点是大大减少了内存的要求（和/或协议栈级别），以及被更快（内部像素，保证一次以读取和写入一次）。然而，该算法是不平凡的。你需要阅读一些研究论文，以实现它。

The current state-of-the-art floodfill algorithm (since 2006 or so) is based on finding the contour (the outermost boundary) of the connected component, converting the contour into horizontal pixel runs (and detecting and removing of internal holes from the connected component), then fill the pixel runs. The benefits are vastly reduced memory requirements (and/or stack level) as well as being faster (interior pixels are guaranteed to be read exactly once and written once). However the algorithm is not trivial. You'll need to read some research papers in order to implement it.

这篇关于我怎样才能提高我的洪水填充程序的性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！