一尘不染

用C语言编写的有效非递归泛洪算法?

algorithm

我一直在尝试找到一种有效的洪水填充算法。在我尝试过的许多算法中,只有“递归行填充”的行为完全符合其应有的表现,但有一个主要警告,即有时会破坏堆栈。:(

我已经尝试了许多非递归实现,并且它们都非常异常:要么在陌生的地方留下空白,要么淹没整个区域(应将它们封闭)。

任何人都有用C(或不太复杂的OOP且我可以很容易地解开纠结的C ++)编写的,非递归的Floodfill工作源代码吗?


阅读 250

收藏
2020-07-28

共1个答案

一尘不染

这是一些可以满足您需求的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;
}
2020-07-28