用C语言编写的有效非递归泛洪算法?
问题内容:
我一直在尝试找到一种有效的洪水填充算法。在我尝试过的许多算法中,只有“递归行填充”的行为完全符合其应有的表现,但有一个主要警告,即有时会破坏堆栈。:(
我已经尝试了许多非递归实现,并且它们都非常异常:要么在陌生的地方留下空白,要么淹没整个区域(应将它们封闭)。
任何人都有用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;
}