我一直在试图找到一个有效的洪水填充算法。在我尝试过的许多算法中，只有“递归行填充”的一种行为完全符合其应有的行为，主要的警告是它偶尔会破坏堆栈。:(
我已经尝试了许多我发现的非递归实现，它们都异常喜怒无常：它们要么在奇怪的地方留下空隙，要么淹没整个区域（当它们应该被封闭时）。
任何人都有一个用 C （或不太严重的 OOP 并且我可以很容易地解开）编写的非递归洪水填充工作源代码？
问问题
23266 次
12 回答
26
只需为堆栈实现一个具有一些固定大小（例如，图像的大小以像素或平方根为单位）的数组的 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<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));
}
}
}
于 2009-08-10T21:01:58.423 回答
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;
}
于 2009-08-10T21:06:07.557 回答
9
快速搜索一下Wikipedia 上关于 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 */
...
}
}
}
于 2009-08-10T20:52:37.320 回答
7
是否有证据表明所有递归函数都可以通过使用本地数据来模拟堆栈来实现为迭代函数？您可能可以使用 std::vector 来创建算法的类似堆栈的行为，而不会破坏堆栈，因为它将使用堆。
编辑：我注意到您使用的是 C，因此您可以通过 realloc 实现类似的行为，而不是 std::vector，因为您需要将更多元素添加到您将使用的任何数据结构的本地“堆栈”中。
于 2009-08-10T20:49:57.200 回答
4
我不知道我的回答是否与您提出的问题完全相关，但此后我提出了我的 C 版本的 Flood-Fill 算法，它不使用递归调用。
2017 年 1 月 11 日：新版本；使用两个位图成功测试。
它仅使用新点的偏移量队列，它适用于窗口：双缓冲区的 WinnOffs-(WinDimX,WinDimY)：*VBuffer（屏幕或图像的副本），并且可选地，它写入一个掩码洪水填充的结果 (*ExtraVBuff)。ExtraVBuff 必须在调用前用 0 填充（如果不需要掩码，可以设置 ExtraVBuff= NULL）；通话后使用它，您可以进行渐变填充或其他绘画效果。NewFloodFill 适用于每像素 32 位，它是一个 C 函数。我在 1991 年重新发明了这个算法（我用 Pascal 编写了他的算法），但现在它在 C 中工作，每像素 32 位；也不使用任何函数调用，只在队列中的每个“pop”之后进行除法，并且永远不会溢出队列，如果它的大小以正确的方式（大约是图像像素的 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）：
由所示的测试程序填充，如下（ffill2.bmp）：
使用“掩码”而不是 NULL，输出位图是（ffill3.bmp）：
于 2017-10-13T17:39:21.947 回答
3
您可以通过创建显式堆栈或队列并将工作加载到其中/将其拉出，将任何递归算法转换为迭代。
您所需要的只是选择一个漂亮、紧凑的表示要完成的工作。最坏的情况：创建一个struct持有你通常会传递给递归版本的参数......
于 2009-08-10T20:52:19.083 回答
2
我们注意到我们在 3d 体积上的洪水填充实现消耗了大量内存；所以我们通过以下方式修改了代码（有很大的改进）：
在起点周围创建一个半径 = 10 个体素的球体，并将该半径内的所有体素标记为“待访问”
如果当前体素 > 阈值，则插入 1。
转到邻居[+1, -1, 0]（还要检查一个没有重新访问任何体素），如果neighbor.getVoxVal = 0（目标体积的初始化值），那么它落在边界球体，将坐标插入不同的堆栈中。（这将是我们下一个领域的起点）
半径 = 半径 + 10（体素）
因此，有一次，我们的 Floodfill 正在处理同心球体并填充东西，这是整个体积的一部分，正如我所说，这大大减少了内存消耗，但我仍在寻找实现/想法那会更好。
于 2010-07-15T16:34:56.400 回答
1
我有一个非递归洪水填充，但我不会发布它，因为它是家庭作业的解决方案。但这里有一个提示：深度优先搜索，这是一种自然算法，比广度优先搜索使用更多的辅助空间。这是我当时写的（适当删减）：
我不敢尝试通过简单的递归进行深度优先搜索；递归的深度仅受 REDACTED 的限制，我的实验表明问题 REDACTED 可能需要超过一百万的堆栈深度。所以我把堆栈放在一个辅助数据结构中。使用显式堆栈实际上也可以很容易地尝试广度优先搜索，事实证明，广度优先搜索可以使用比深度优先搜索少 40 倍的空间。
对于我的数据结构，我使用了Seq_TDave Hanson 的C Interfaces and Implementations；从深度优先更改为广度优先只需要更改一个函数调用。
于 2009-08-11T02:18:49.727 回答
1
您可以快速将递归洪水填充转换为超高性能的伪递归......不要编辑行，只需添加新行：将递归函数放在 XY 循环中以添加结构。将找到的邻居记录到“找到的邻居数组”而不是内存中，因此您将开始将递归的 4-16-64 样式树打包到 XY 数组中。内存使用量从 1 吉字节到 2 兆字节。还使用一个称为“填充邻居数组”的二维数组...中止在“填充邻居数组”中标记为填充的任何像素的函数，这对每个重复项使用 2 条指令，每个填充操作使用 20 条指令，并且它迭代地填充像多米诺骨牌一样向左和向上，速度非常快。
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
和代码。
如果能够保持组织性，递归将是最快的。
如果您通过数据（图像）网格进行递归，您也可以以网格格式存储递归处理，因为处理的步骤代表网格中的像素，而不是将结果分解为树格式。
于 2018-08-08T06:41:35.183 回答
0
下面是我针对洪水填充问题的基于 BFS 的迭代 c++ 方法：
// M is the input matrix, with every entry(pixel) have a color
// represented with an integer value.
// (x, y) row and column of seed point respectively
// k: The new color to fill the seed and its adjacent pixels
void floodFill(vector<vector<int>> &M, int x, int y, int k) {
queue<pair<int, int>> nodeQ;
nodeQ.push({x, y});
int oldCol = M[x][y];
while(!nodeQ.empty()) {
pair<int, int> currNode = nodeQ.front();
nodeQ.pop();
if(M[currNode.first][currNode.second] == oldCol) {
M[currNode.first][currNode.second] = k;
if(currNode.first > 0) nodeQ.push({currNode.first-1, currNode.second});
if(currNode.first < (M.size()-1)) nodeQ.push({currNode.first+1, currNode.second});
if(currNode.second > 0) nodeQ.push({currNode.first, currNode.second-1});
if(currNode.second < (M[0].size()-1)) nodeQ.push({currNode.first, currNode.second+1});
}
}
}
于 2017-05-16T01:50:02.760 回答
0
这是每秒完成 1000 万像素的非递归例程的指南：它被称为 marching-floodfills，如果您将先前的递归例程在 XY 循环中向前行进会发生什么。
编写你自己的内存，一个 2D 数组来记录已验证的空间，另一个数组记录完整的填充图像，并使用这个循环系统读取和写入它们......它平均每个像素 20 条指令。我使用上述视频逻辑以每秒 500 万体素的速度处理了 20 亿个体素图。
于 2020-04-21T14:34:27.430 回答
0
我发现 Paul Heckbert 的这个填充是最简单的非递归 C 实现：
/*
* A Seed Fill Algorithm
* by Paul Heckbert
* from "Graphics Gems", Academic Press, 1990
*
* user provides pixelread() and pixelwrite() routines
*/
/*
* fill.c : simple seed fill program
* Calls pixelread() to read pixels, pixelwrite() to write pixels.
*
* Paul Heckbert 13 Sept 1982, 28 Jan 1987
*/
typedef struct { /* window: a discrete 2-D rectangle */
int x0, y0; /* xmin and ymin */
int x1, y1; /* xmax and ymax (inclusive) */
} Window;
typedef int Pixel; /* 1-channel frame buffer assumed */
Pixel pixelread(int x, int y);
void pixelwrite(int x, int y, Pixel p);
typedef struct {short y, xl, xr, dy;} Segment;
/*
* Filled horizontal segment of scanline y for xl<=x<=xr.
* Parent segment was on line y-dy. dy=1 or -1
*/
#define MAX 10000 /* max depth of stack */
#define PUSH(Y, XL, XR, DY) /* push new segment on stack */ \
if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \
{sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}
#define POP(Y, XL, XR, DY) /* pop segment off stack */ \
{sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}
/*
* fill: set the pixel at (x,y) and all of its 4-connected neighbors
* with the same pixel value to the new pixel value nv.
* A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
*/
void fill(x, y, win, nv)
int x, y; /* seed point */
Window *win; /* screen window */
Pixel nv; /* new pixel value */
{
int l, x1, x2, dy;
Pixel ov; /* old pixel value */
Segment stack[MAX], *sp = stack; /* stack of filled segments */
ov = pixelread(x, y); /* read pv at seed point */
if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) return;
PUSH(y, x, x, 1); /* needed in some cases */
PUSH(y+1, x, x, -1); /* seed segment (popped 1st) */
while (sp>stack) {
/* pop segment off stack and fill a neighboring scan line */
POP(y, x1, x2, dy);
/*
* segment of scan line y-dy for x1<=x<=x2 was previously filled,
* now explore adjacent pixels in scan line y
*/
for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--)
pixelwrite(x, y, nv);
if (x>=x1) goto skip;
l = x+1;
if (l<x1) PUSH(y, l, x1-1, -dy); /* leak on left? */
x = x1+1;
do {
for (; x<=win->x1 && pixelread(x, y)==ov; x++)
pixelwrite(x, y, nv);
PUSH(y, l, x-1, dy);
if (x>x2+1) PUSH(y, x2+1, x-1, -dy); /* leak on right? */
skip: for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
l = x;
} while (x<=x2);
}
}
来源：https ://github.com/erich666/GraphicsGems/blob/master/gems/SeedFill.c
于 2020-08-20T14:11:07.723 回答