用C编写的工作非递归填充算法？

我一直在努力找到一个有效的填充算法.在许多算法中,我只尝试过"递归线填充",其中一个行为完全符合它应该的主要警告,它偶尔会打击堆栈.:(

我已经尝试了很多我发现的非递归实现,并且它们都非常温和:要么在奇怪的地方留下空隙,要么泛滥整个区域(当它们应该被封闭时).

任何人都有一个用C语言编写的非递归填充工作源代码(或者c ++不是太大的OOP而且我可以很容易地解开)？

只需实现一堆int对,其中包含一些固定大小的数组(例如,像素的大小或像素的平方根),并使用int跟踪顶部.

以下是一些非递归实现floodfill的C#代码:

private static void Floodfill(byte[,] vals, Point q, byte SEED_COLOR, byte COLOR)
{
    int h = vals.GetLength(0);
    int w = vals.GetLength(1);

    if (q.Y < 0 || q.Y > h - 1 || q.X < 0 || q.X > w - 1)
        return;

    Stack stack = new Stack();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
            continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
            vals[y, x] = COLOR;
            stack.Push(new Point(x + 1, y));
            stack.Push(new Point(x - 1, y));
            stack.Push(new Point(x, y + 1));
            stack.Push(new Point(x, y - 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 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;
}

一个快速的谷歌搜索引出维基百科有关Flood Fill的文章,其中包括非递归的伪代码实现.下面是一些可以帮助您入门的代码,C中的基本队列实现:

typedef struct queue_ { struct queue_ *next; } queue_t;
typedef struct ffnode_ { queue_t node; int x, y; } ffnode_t;

/* returns the new head of the queue after adding node to the queue */
queue_t* enqueue(queue_t *queue, queue_t *node) {
    if (node) {
        node->next = queue;
        return node;
    }
    return NULL;
}

/* returns the head of the queue and modifies queue to be the new head */
queue_t* dequeue(queue_t **queue) {
    if (queue) {
        queue_t *node = (*queue);
        (*queue) = node->next;
        node->next = NULL;
        return node;
    }
    return NULL;
}

ffnode_t* new_ffnode(int x, int y) {
    ffnode_t *node = (ffnode_t*)malloc(sizeof(ffnode_t));
    node->x = x; node->y = y;
    node->node.next = NULL;
    return node;
}

void flood_fill(image_t *image, int startx, int starty, 
                color_t target, color_t replacement) {
    queue_t *head = NULL;
    ffnode_t *node = NULL;

    if (!is_color(image, startx, starty, target)) return;

    node = new_ffnode(startx, starty);
    for ( ; node != NULL; node = (ffnode_t*)dequeue(&head)) {
        if (is_color(image, node->x, node->y, target)) {
            ffnode_t *west = node, *east = node;

            recolor(image, node->x, node->y, replacement);
            /* 1. move w to the west until the color of the node to the west
               no longer matches target */
            ...
        }
    }
}

是不是有证据表明所有递归函数都可以通过使用本地数据模拟堆栈来实现为迭代函数？您可以使用std :: vector来创建算法的类似堆栈的行为,而不会破坏堆栈,因为它将使用堆.

编辑:我注意到你正在使用C,所以你可以通过realloc实现类似的行为,而不是std :: vector,因为你需要在你所使用的任何数据结构的本地"堆栈"中添加更多元素.