用C语言编写的有效非递归泛洪算法？ [英] a working non-recursive floodfill algorithm written in C?

问题描述

我一直在寻找一种可行的洪水填充算法。在我尝试过的众多算法中，只有递归行填充算法的行为与应有的表现完全一样，但有一个主要警告，即有时会破坏堆栈。 ：（

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语言编写的有效非递归泛洪算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！