问题描述
我一直在寻找一种可行的洪水填充算法。在我尝试过的众多算法中,只有递归行填充算法的行为与应有的表现完全一样,但有一个主要警告,即有时会破坏堆栈。 :(
I've been trying to find a working floodfill algorithm. Of the many algorithms I've tried only the 'recursive line fill' one behaves exactly as it should with the major caveat that it occasionally blows the stack. :(
我尝试了许多非递归实现,它们都异常地温和:要么在陌生的地方留下空白,要么淹没整个区域(应该将它们括起来)。
I have tried many non-recursive implementations I've found and they have all been exceptionally tempermental: either they leave gaps in strange places, or flood the whole area (when they should be enclosed).
任何人都有一个非递归的Floodfill工作源代码,用C语言编写(或OOP不太严重的c ++,我可以很容易地解开纠结
Anyone has a NON-recursive floodfill working sourcecode written in C (or c++ that isn't too heavily OOP and I can disentangle easily enough)?
推荐答案
下面的一些C ++代码可以满足您的要求,它使用队列,并且在插入时更有效
Here's some C++ code that does what you want. It uses a queue, and is more efficient about insertions into the queue.
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;
}
这篇关于用C语言编写的有效非递归泛洪算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!