我一直在寻找一个可行的泛洪填充算法。我尝试了许多算法，只有“递归线性填充”算法表现得完全符合预期，但它有一个严重的缺点，即有时会导致堆栈溢出。 :(
我已经尝试了许多非递归实现，但它们都非常难以处理：要么留下奇怪的空洞，要么将整个区域填满（当它们应该被包围时）。
请问是否有任何非递归的泛洪填充源代码，使用C编写（或者是不太OOP，容易解开的C++）？
用C语言编写的可行的非递归泛洪算法是什么？
19
- horseyguy
5
3只是挑刺一下：算法是用伪代码（和/或图片）表示的，您实际上正在要求用C语言实现。 - H H
4我曾经在一个编程面试中收到过这个问题，我猜您之所以这么急切是因为您也收到了类似的问题。 - andy
其实，安迪，这不是为了面试，而是我正在编写一个图形库 :) - horseyguy
回答这个问题：是的，我有一个非递归的泛洪填充实现。它使用了一个待办列表（和一个已完成列表，如果我没记错的话）。 - wildplasser
这里有一个视频，演示了“搜索式泛洪填充”算法在X-Y循环中前进的过程：youtube.com/watch?v=LvacRISl99Y。通过编写自己的内存，使用2D数组记录已验证空间和记录完整填充图像的另一个数组，并使用此循环系统进行读写...平均每个像素20个指令。我使用上述视频逻辑处理了每秒5百万体素图形的20亿个体素。 - bandybabboon
13个回答
27
可以使用一个固定大小的 int 对数组来实现 int 对栈的堆栈 (例如像素图像的大小或其平方根)，并使用 int 来跟踪顶部。
这是一些实现非递归泛洪填充的 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<Point> stack = new Stack<Point>();
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));
}
}
}
- Jared Updike
6
1我已经向一些朋友推荐了这段代码。现在有三个ROM修改者，包括我自己，正在使用你的代码。 - Kawa
非常好，这是最接近递归的实现方式，而不会出现实际溢出问题。 - Gerard
1@Gerard: 无稽之谈；它只是用另一个堆栈溢出问题代替了一个堆栈溢出问题。 - Brendan
@Brendan：实际上，如果堆栈在堆上实现，那么它就不是一个堆栈问题了。在C++中，Stack<T>可能是基于堆栈的，但在C#中，它很可能是基于堆的。此外，您可以在堆上实现自己的Stack<T>以确保它是堆栈。 （必须承认，它可以以更节省内存的方式进行簿记。这是读者的练习题。） - Jared Updike
1@JaredUpdike：栈溢出是一种栈问题（由于超出资源限制而引起的问题），无论栈如何实现或从哪里获取资源。 - Brendan
12
这里有一些 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;
}
- rlbond
2
1嗨，Banister，你能把上面的代码转换成Objective C吗？我也遇到了同样的情况，不确定是否能将上述代码转换成Objective C，如果你能给我一点头绪就好了。 - RVN
你可以将Objective-C文件的扩展名(.m)更改为Objective-C++(.mm)，然后在同一个文件中混合使用Obj-C和C++。(你不必将整个项目都用C++编写。) - Jared Updike
10
快速搜索可以找到 洪水填充算法的维基百科文章，其中包括非递归的伪代码实现。以下是一些基础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 */
...
}
}
}
- user7116
1
1很遗憾，没有人实现维基百科上关于泛洪填充的固定内存算法。那将是很酷的事情。 :) - user427415
7
是否有证明所有递归函数都可以通过使用本地数据来模拟堆栈的迭代函数实现的证据？您可以使用std::vector创建类似算法的堆栈行为，而不会使堆栈溢出，因为它将使用堆。
编辑：我注意到您正在使用C语言，因此您可以通过realloc实现类似的行为，因为您需要向您将使用的任何数据结构的本地“堆栈”添加更多元素。
- Jim Buck
6
4好的，他不会在C中使用std::vector。 - dmckee --- ex-moderator kitten
好的，我已经更新了答案，并提供了std::vector替代建议。 - Jim Buck
虽然可以将其转换为具有显式堆栈的迭代函数，但我担心它可能会成为一个非常大的堆栈 - 最大长度受到洪水填充区域形成的（相当密集的）平面图中最长无环路径的限制。使用广度优先搜索策略可能需要更少的内存。 - bdonlan
2“难道没有证明表明所有递归函数都可以通过使用本地数据模拟堆栈来实现迭代函数吗？”是的，有。它是这样的：所有递归算法都是通过为每个递归调用在调用堆栈上推送新帧来运行的。您可以通过自己显式地执行而不是通过函数调用隐式执行来完成。证毕。 ;) - Joren
@Joren 实际上，在具有尾调用优化的语言中，递归是通过替换堆栈上的参数而不是推送堆栈帧来实现的，使用固定数量的内存。 https://dev59.com/5HVD5IYBdhLWcg3wRpaX#33930 - Jared Updike
@JaredUpdike 没错。我想我本可以说“可以运行”而不是“正在运行”，但关键点还是成立的。 - Joren
7
我不知道我的答案是否完全与你提出的问题相关，但接下来我提供我的Flood-Fill算法的C语言版本，它不使用递归调用。
2017年1月11日：新版本；已成功测试两个位图。
它只使用一个新点偏移量队列，作用于双缓冲区的窗口：WinnOffs-(WinDimX,WinDimY) 的 *VBuffer（屏幕或图像的副本），并且可选地写入洪水填充结果的掩码（*ExtraVBuff）。在调用之前必须使用0填充ExtraVBuff（如果您不需要掩码，则可以将ExtraVBuff设置为NULL）；在调用之后使用它，您可以进行渐变洪水填充或其他绘画效果。NewFloodFill使用每像素32位，并且是一个C函数。我在1991年重新发明了这个算法（我用Pascal写过它），但现在它使用每像素32位的C语言编写；也不使用任何函数调用，仅在从队列中“弹出”后执行除法，并且永远不会溢出队列，如果它的大小正确（大约为图像像素的1/4），则始终允许正确地填充任何区域；我先展示c函数（FFILL.C），然后是测试程序（TEST.C）：
#define IMAGE_WIDTH 1024
#define IMAGE_HEIGHT 768
#define IMAGE_SIZE IMAGE_WIDTH*IMAGE_HEIGHT
#define QUEUE_MAX IMAGE_SIZE/4
typedef int T_Queue[QUEUE_MAX];
typedef int T_Image[IMAGE_SIZE];
void NewFloodFill(int X,
int Y,
int Color,
int BuffDimX,
int WinOffS,
int WinDimX,
int WinDimY,
T_Image VBuffer,
T_Image ExtraVBuff,
T_Queue MyQueue)
/* Replaces all pixels adjacent to the first pixel and equal to this; */
/* if ExtraVBuff == NULL writes to *VBuffer (eg BUFFER of 786432 Pixel),*/
/* otherwise prepare a mask by writing on *ExtraVBuff (such BUFFER must */
/* always have the same size as *VBuffer (it must be initialized to 0)).*/
/* X,Y: Point coordinates' of origin of the flood-fill. */
/* WinOffS: Writing start offset on *VBuffer and *ExtraVBuff. */
/* BuffDimX: Width, in number of Pixel (int), of each buffer. */
/* WinDimX: Width, in number of Pixel (int), of the window. */
/* Color: New color that replace all_Pixel == origin's_point. */
/* WinDimY: Height, in number of Pixel (int), of the window. */
/* VBuffer: Pointer to the primary buffer. */
/* ExtraVBuff: Pointer to the mask buffer (can be = NULL). */
/* MyQueue: Pointer to the queue, containing the new-points' offsets*/
{
int VBuffCurrOffs=WinOffS+X+Y*BuffDimX;
int PixelIn=VBuffer[VBuffCurrOffs];
int QueuePnt=0;
int *TempAddr=((ExtraVBuff) ? ExtraVBuff : VBuffer);
int TempOffs1;
int TempX1;
int TempX2;
char FLAG;
if (0<=X && X<WinDimX && 0<=Y && Y<WinDimY) do
{
/* Fill to left the current line */
TempX2=X;
while (X>=0 && PixelIn==VBuffer[VBuffCurrOffs])
{
TempAddr[VBuffCurrOffs--]=Color;
--X;
}
TempOffs1=VBuffCurrOffs+1;
TempX1=X+1;
/* Fill to right the current line */
VBuffCurrOffs+=TempX2-X;
X=TempX2;
while (X+1<WinDimX && PixelIn==VBuffer[VBuffCurrOffs+1])
{
++X;
TempAddr[++VBuffCurrOffs]=Color;
}
TempX2=X;
/* Backward scan of the previous line; puts new points offset in Queue[] */
if (Y>0)
{
FLAG=1;
VBuffCurrOffs-=BuffDimX;
while (X-->=TempX1)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
--VBuffCurrOffs;
}
}
/* Forward scan of the next line; puts new points offset in Queue[] */
if (Y<WinDimY-1)
{
FLAG=1;
VBuffCurrOffs=TempOffs1+BuffDimX;
X=TempX1;
while (X++<=TempX2)
{
if (PixelIn!=VBuffer[VBuffCurrOffs] ||
ExtraVBuff && Color==ExtraVBuff[VBuffCurrOffs])
FLAG=1;
else
if (FLAG)
{
FLAG=0;
if (QueuePnt<QUEUE_MAX)
MyQueue[QueuePnt++]=VBuffCurrOffs;
}
++VBuffCurrOffs;
}
}
/* Gets a new point offset from Queue[] */
if (--QueuePnt>=0)
{
VBuffCurrOffs=MyQueue[QueuePnt];
TempOffs1=VBuffCurrOffs-WinOffS;
X=TempOffs1%BuffDimX;
Y=TempOffs1/BuffDimX;
}
/* Repeat the main cycle until the Queue[] is not empty */
} while (QueuePnt>=0);
}
这里有一个测试程序：
#include <stdio.h>
#include <malloc.h>
#include "ffill.c"
#define RED_COL 0xFFFF0000
#define WIN_LEFT 52
#define WIN_TOP 48
#define WIN_WIDTH 920
#define WIN_HEIGHT 672
#define START_LEFT 0
#define START_TOP 671
#define BMP_HEADER_SIZE 54
typedef char T_Image_Header[BMP_HEADER_SIZE];
void main(void)
{
T_Image_Header bmpheader;
T_Image *image;
T_Image *mask;
T_Queue *MyQueue;
FILE *stream;
char *filename1="ffill1.bmp";
char *filename2="ffill2.bmp";
char *filename3="ffill3.bmp";
int bwritten;
int bread;
image=malloc(sizeof(*image));
mask=malloc(sizeof(*mask));
MyQueue=malloc(sizeof(*MyQueue));
stream=fopen(filename1,"rb");
bread=fread(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bread=fread((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
memset(mask,0,IMAGE_SIZE<<2);
NewFloodFill(START_LEFT,
START_TOP,
RED_COL,
IMAGE_WIDTH,
IMAGE_WIDTH*WIN_TOP+WIN_LEFT,
WIN_WIDTH,
WIN_HEIGHT,
*image,
NULL,
*MyQueue);
stream=fopen(filename2,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)image, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
stream=fopen(filename3,"wb+");
bwritten=fwrite(&bmpheader, 1, BMP_HEADER_SIZE, stream);
bwritten=fwrite((char *)mask, 1, IMAGE_SIZE<<2, stream);
fclose(stream);
free(MyQueue);
free(mask);
free(image);
}
我使用了下面这张未压缩的Windows .BMP图像(ffill1.bmp)作为测试程序的输入：
- Paolo Fassin
3
你可以通过创建显式堆栈或队列并将工作加载到其中/从中取出来，将任何递归算法转换为迭代算法。
你只需要选择一个好的、紧凑的工作表示方式。最坏情况下：创建一个结构体来保存通常传递给递归版本的参数...
你只需要选择一个好的、紧凑的工作表示方式。最坏情况下：创建一个结构体来保存通常传递给递归版本的参数...
- dmckee --- ex-moderator kitten
2
我们注意到我们的三维体积泛洪实现会消耗大量内存，因此我们按以下方式修改了代码（改进很大）：
创建半径为10个体素的球围绕起始点，并将该半径内的所有体素标记为“待访问”
如果当前体素 > 阈值，则插入1。
前往邻居[+1，-1，0]（还要检查是否不重新访问任何体素），如果neighbor.getVoxVal = 0（目标体积的初始化值），则它落在球的边界上，在不同的堆栈中插入坐标。（这将是我们下一个球的起始点）
半径=半径+10（体素）
- Sayan
1
我在C语言中进行了一个简单的实现。
在我的例子中的背景：
#define EMPTY ' '
#define REVEALED '-'
#define GRID_SET(P, X) (grid[W * (P).y + (P).x] = (X))
typedef struct {
int x, y;
} vec2_t;
char grid[H * W] = "##########"
"##########"
"## #####"
"## ####"
"# ###"
"# #"
"# ##"
"## ###"
"##########"
"##########";
static bool is_empty(vec2_t p) {
return p.x >= 0 && p.x < W && p.y >= 0 && p.y < H &&
grid[W * p.y + p.x] == EMPTY;
}
队列功能：
static vec2_t queue_pop_front(vec2_t* q, int* top) {
vec2_t ret = q[0];
/* Shift. Note that `top` is not the last pushed value, but the next one */
*top -= 1;
for (int i = 0; i < *top; i++)
q[i] = q[i + 1];
return ret;
}
static void queue_push(vec2_t* q, int* top, vec2_t x) {
q[*top] = x;
*top += 1;
}
泛洪填充：
static void flood_fill(vec2_t p) {
/* First in, first out */
vec2_t* queue = malloc(W * H * sizeof(vec2_t));
int queue_pos = 0;
/* Push parameter and reveal it */
queue_push(queue, &queue_pos, p);
GRID_SET(p, REVEALED);
/* Queue is not empty */
while (queue_pos > 0) {
const vec2_t cur = queue_pop_front(queue, &queue_pos);
vec2_t up = { cur.x, cur.y - 1 };
if (is_empty(up)) {
queue_push(queue, &queue_pos, up);
GRID_SET(up, REVEALED);
}
vec2_t down = { cur.x, cur.y + 1 };
if (is_empty(down)) {
queue_push(queue, &queue_pos, down);
GRID_SET(down, REVEALED);
}
vec2_t left = { cur.x - 1, cur.y };
if (is_empty(left)) {
queue_push(queue, &queue_pos, left);
GRID_SET(left, REVEALED);
}
vec2_t right = { cur.x + 1, cur.y };
if (is_empty(right)) {
queue_push(queue, &queue_pos, right);
GRID_SET(right, REVEALED);
}
}
free(queue);
}
- trxgnyp1
1
你可以快速将递归泛洪填充转换为超高效的伪递归...不要编辑这些行，只需添加新行：
将递归函数放置在XY循环中以增加结构。
将找到的邻居记录到“找到的邻居数组”中，而不是内存，因此您将开始将递归的4-16-64样式树打包成XY数组。内存使用量从1 gygabyte降至2兆字节。
还要使用名为“填充邻居数组”的二维数组...对于在“填充邻居数组”中标记为已填充的任何像素，中止函数，这使用了每个重复项的2个指令，每个泛洪填充操作的20个指令，并且它迭代地向左和向上填充，就像多米诺骨牌一样，非常快速。
1024x1024大约使用100万*20个指令，即单核心0.1秒。
我用这种方式在i7上实现了每秒900万个填充像素，我有一个视频作为证明，以及一个带有代码和理论解释的博客页面：
1024x1024大约使用100万*20个指令，即单核心0.1秒。
我用这种方式在i7上实现了每秒900万个填充像素，我有一个视频作为证明，以及一个带有代码和理论解释的博客页面：
www.youtube.com/watch?v=4hQ1wA4Sl4c
这里有一个页面，我试图解释它的工作原理。 http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1
还有代码。
如果递归能够保持有序，那么递归将是最快的。
如果你通过数据网格（图像）进行递归，你也可以以网格格式存储递归的处理，因为处理步骤代表来自网格的像素，而不是将结果展开成树形格式。
- bandybabboon
1
我有一个非递归的泛洪填充算法，但是我不会发布它，因为这是一个作业的解决方案。但是这里有一个提示：深度优先搜索，这是自然算法，使用的辅助空间比广度优先搜索要多。当时我写下了以下内容（经过适当修改）：
对于我的数据结构，我使用了Dave Hanson的C语言接口与实现中的我不敢用简单递归尝试深度优先搜索；递归的深度仅受限于REDACTED，我的实验表明，即使是PROBLEM REDACTED也可能需要超过一百万的堆栈深度。因此，我将堆栈放在一个辅助数据结构中。使用明确的堆栈实际上使尝试广度优先搜索变得容易，并且事实证明，广度优先搜索可以使用比深度优先搜索少四十倍的空间。
Seq_T ;从深度优先到广度优先的更改只需要更改一个函数调用。- Norman Ramsey
1
错误，你需要修正第二个句子，该句子比较了相同算法的辅助空间。 :-) - Zan Lynx
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接