我一直在尝试找到一种有效的洪水填充算法。在我尝试过的许多算法中,只有“递归行填充”的行为完全符合其应有的表现,但有一个主要警告,即有时会破坏堆栈。:(
我已经尝试了许多非递归实现,并且它们都非常异常:要么在陌生的地方留下空白,要么淹没整个区域(应将它们封闭)。
任何人都有用C(或不太复杂的OOP且我可以很容易地解开纠结的C ++)编写的,非递归的Floodfill工作源代码吗?
这是一些可以满足您需求的C ++代码。它使用队列,并且在插入队列中效率更高。
connectedRegion(const Point& source, RegionType& region, const Color target) { Color src_color = color_of(source, region); if (region.count(source) == 0 || src_color == target) return; std::queue<Point> analyze_queue; analyze_queue.push(source); while (!analyze_queue.empty()) { if (color_of(analyze_queue.front()) != src_color) { analyze_queue.pop(); continue; } Point leftmost_pt = analyze_queue.front(); leftmost_pt.col -= 1; analyze_queue.pop(); Point rightmost_pt = leftmost_pt; rightmost_pt.col += 2; while (color_of(leftmost_pt, region) == src_color) --leftmost_pt.col; while (color_of(rightmost_pt, region) == src_color) ++rightmost_pt.col; bool check_above = true; bool check_below = true; Point pt = leftmost_pt; ++pt.col; for (; pt.col < rightmost_pt.col; ++pt.col) { set_color(pt, region, target); Point pt_above = pt; --pt_above.row; if (check_above) { if (color_of(pt_above, region) == src_color) { analyze_queue.push(pt_above); check_above = false; } } else // !check_above { check_above = (color_of(pt_above, region) != src_color); } Point pt_below = pt; ++pt_below.row; if (check_below) { if (color_of(pt_below, region) == src_color) { analyze_queue.push(pt_below); check_below = false; } } else // !check_below { check_below = (color_of(pt_below, region) != src_color); } } // for } // while queue not empty return connected; }