种子填充算法

㈠ 求一个C语言实现的种子填充多边形算法程序

/*如果是用线填充，程序如下。如果是用点填充需要用到堆栈和系统底层库函数或者用画点函数putpixel()。 下面实例是用扫描线填充长方形，开始要输入长方形的左上顶点坐标和右下顶点坐标以及填充扫描线的间距(>=1)，如果间距等于1，就是完全填充(实填充)。 一个完整的c程序如下,程序在win-tc和tc2.0下都调试通过。 */ #include<stdio.h> #include<stdlib.h> #include<conio.h> #include<graphics.h> void draw(int x1,int y1,int x2,int y2,int delta) {int nx1,ny1,nx2,ny2; nx1=x1,ny1=y2-delta,nx2=x1+delta,ny2=y2; while((ny1>=y1)&&(nx2<=x2)) {line(nx1,ny1,nx2,ny2); ny1-=delta; nx2+=delta; } if(nx2>x2) {ny2-=nx2-x2; nx2=x2; while(ny1>y1) {line(nx1,ny1,nx2,ny2); ny1-=delta; ny2-=delta; } nx1+=y1-ny1; ny1=y1; while(nx1<x2) {line(nx1,ny1,nx2,ny2); nx1+=delta; ny2-=delta; } } else {nx1+=y1-ny1; ny1=y1; while(nx2<x2) {line(nx1,ny1,nx2,ny2); nx2+=delta; nx1+=delta; } ny2-=nx2-x2; nx2=x2; while(ny2>y1) {line(nx1,ny1,nx2,ny2); ny2-=delta; nx1+=delta; } } } int main(void) {int x1,y1,y2,x2,delta; int driver=DETECT,mode; printf("Please input lefttop(x1,y1) and rightbottom(x2,y2) of rectangle and delta:\n"); scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&delta); initgraph (&driver,&mode,"C:\\TC"); /*这里*/ rectangle(x1,y1,x2,y2); draw(x1,y1,x2,y2,delta); gotoxy(1,1); printf("Press any key to exit!"); getch(); closegraph(); return 0; } /*说明：将main()函数中的initgraph(&gdriver,&gmode,"");中的""更改为你的TC安装目录,一般tc必须安装在c盘根目录下，所以就是initgraph(&gdriver,&gmode,"C:\\TC");如你的TC安装目录为D盘的Tools目录下的TC目录，那么上述语句改为： initgraph(&gdriver,&gmode,"D:\\Tools\\TC"); 同时保证在D:\\Tools\\TC目录里有文件EGAVGA.BGI,万一不行，将本程序复制到你的TC安装目录下再运行。 */

㈡ 扫描线种子填充算法中，每次压入栈的像素最多有几个

19" 宽屏 16Bits 颜色 1440*900*2 =2M 1M =Screen/2;100M =50Screen
19" 宽屏 24Bits 颜色 1440*900*3 = 3888000=3M 1M =Screen/3;100M =33Screen

19" 宽屏 32Bits 颜色 1440*900*4 = 3888000=4M 1M =Screen/4;100M =25Screen

23" 宽屏 32Bits 颜色 1920*1080*4=8M 1M =Screen/8;100M =12Screen
堆栈不宜过大，64M已经很大了。
图像数据还是放在堆空间吧！

㈢ 种子填充算法的时间复杂度和空间复杂度分析

从涂色的角度讲，区域内的n个点，每一个点只被涂了一次色，没有重复涂，所以可以认为时间复杂度是O(n);空间复杂度也为O(n),虽然有些点重复栈

㈣ 下面是一个4通向的种子填充算法 但是运行时老是堆栈溢出, 小弟急求大神相助啊.

1、参数x、y由double类型改为int型。

2、方法中x、y限定最小值、最大值。

voidseed(intx,inty,Colornow,Colorfill){
Colorcurrentcolor;
currentcolor=bmp->GetPixel(x,y);
if(currentcolor==now){
bmp->SetPixel(x,y,fill);
if(x<MAX_X){
seed(x+1,y,now,fill);
}
if(x>MIN_X){
seed(x-1,y,now,fill);
}
if(x<MAX_Y){
seed(x,y+1,now,fill);
}
if(x>MIN_Y){
seed(x,y-1,now,fill);
}
}
}

㈤ C语言种子填充法填充圆求助

编译能通过，但是执行出问题，或者执行的效果和自己想象的不一样，就需要调试。看看这个：
http://tieba..com/f?kz=779255997
希望对你有帮助。

㈥ 填充算法的种子填充算法

种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。
种子填充算法常用四连通域和八连通域技术进行填充操作。
从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。
从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。
一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2.4a所示的区域的内部，而四向连通填充算法只能完成如图2.4b的部分填充。
图2.4 四向连通填充算法
a) 连通域及其内点 b) 填充四连通域
四向连通填充算法：
a） 种子像素压入栈中；
b） 如果栈为空，则转e)；否则转c)；
c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；
d） 转b）；
e） 结束。
四向连通填充方法可以用递归函数实现如下：
算法2.3 四向连通递归填充算法：
void BoundaryFill4(int x, int y, long FilledColor, long BoundaryColor)
{
long CurrentColor;
CurrentColor = GetPixelColor(x,y);
if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)
{
SetColor(FilledColor);
SetPixel (x,y);
BoundaryFill4(x+1, y, FilledColor, BoundaryColor);
BoundaryFill4(x-1, y, FilledColor, BoundaryColor);
BoundaryFill4(x, y+1, FilledColor, BoundaryColor);
BoundaryFill4(x, y-1, FilledColor, BoundaryColor);
}
}
上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。一个改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。

㈦ 用队列实现种子填充算法的非递归

一、种子填充算法（Seed Filling）
如果要填充的区域是以图像元数据方式给出的，通常使用种子填充算法（Seed Filling）进行区域填充。种子填充算法需要给出图像数据的区域，以及区域内的一个点，这种算法比较适合人机交互方式进行的图像填充操作，不适合计算机自动处理和判断填色。根据对图像区域边界定义方式以及对点的颜色修改方式，种子填充又可细分为几类，比如注入填充算法（Flood Fill Algorithm）、边界填充算法（Boundary Fill Algorithm）以及为减少递归和压栈次数而改进的扫描线种子填充算法等等。
所有种子填充算法的核心其实就是一个递归算法，都是从指定的种子点开始，向各个方向上搜索，逐个像素进行处理，直到遇到边界，各种种子填充算法只是在处理颜色和边界的方式上有所不同。在开始介绍种子填充算法之前，首先也介绍两个概念，就是“4-联通算法”和“8-联通算法”。既然是搜索就涉及到搜索的方向问题，从区域内任意一点出发，如果只是通过上、下、左、右四个方向搜索到达区域内的任意像素，则用这种方法填充的区域就称为四连通域，这种填充方法就称为“4-联通算法”。如果从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下全部八个方向到达区域内的任意像素，则这种方法填充的区域就称为八连通域，这种填充方法就称为“8-联通算法”。如图1（a）所示，假设中心的蓝色点是当前处理的点，如果是“4-联通算法”，则只搜索处理周围蓝色标识的四个点，如果是“8-联通算法”则除了处理上、下、左、右四个蓝色标识的点，还搜索处理四个红色标识的点。两种搜索算法的填充效果分别如如图1（b）和图1（c）所示，假如都是从黄色点开始填充，则“4-联通算法”如图1（b）所示只搜索填充左下角的区域，而“8-联通算法”则如图1（c）所示，将左下角和右上角的区域都填充了。

图（1） “4-联通”和“8-联通”填充效果

并不能仅仅因为图1的填充效果就认为“8-联通算法”一定比“4-联通算法”好，应该根据应用环境和实际的需求选择联通搜索方式，在很多情况下，只有“4-联通算法”才能得到正确的结果。
1.1 注入填充算法（Flood Fill Algorithm）
注入填充算法不特别强调区域的边界，它只是从指定位置开始，将所有联通区域内某种指定颜色的点都替换成另一种颜色，从而实现填充效果。注入填充算法能够实现颜色替换之类的功能，这在图像处理软件中都得到了广泛的应用。注入填充算法的实现非常简单，核心就是递归和搜索，以下就是注入填充算法的一个实现：

164 void FloodSeedFill(int x, int y, int old_color, int new_color)
165 {
166 if(GetPixelColor(x, y) == old_color)
167 {
168 SetPixelColor(x, y, new_color);
169 for(int i = 0; i < COUNT_OF(direction_8); i++)
170 {
171 FloodSeedFill(x + direction_8[i].x_offset,
172 y + direction_8[i].y_offset, old_color, new_color);
173 }
174 }
175 }

for循环实现了向8个联通方向的递归搜索，秘密就在direction_8的定义：

15 typedef struct tagDIRECTION
16 {
17 int x_offset;
18 int y_offset;
19 }DIRECTION;

79 DIRECTION direction_8[] = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1},{0, -1}, {-1, -1} };

这个是搜索类算法中常用的技巧，无需做太多说明，其实只要将其替换成如下direction_4的定义，就可以将算法改成4个联通方向填充算法：

80 DIRECTION direction_4[] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

图2就是应用本算法实现的“4-联通”和“8-联通”填充效果：

㈧ 简述边界表示的四连通区域的种子填充算法的基本思想和执行步骤

一、种子填充算法思想：
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
二、种子填充算法步骤：
1、初始化堆栈。
2、种子压入堆栈。
3、While（堆栈非空）从堆栈弹出种子象素。

㈨ 求八向联通的种子填充算法代码，用C/C++

bool pop(int &x, int &y)
{
if(stackPointer > 0)
{
int p = stack[stackPointer];
x = p / h;
y = p % h;
stackPointer--;
return 1;
}
else
{
return 0;
}
}

bool push(int x, int y)
{
if(stackPointer < stackSize - 1)
{
stackPointer++;
stack[stackPointer] = h * x + y;
return 1;
}
else
{
return 0;
}
}
void floodFill8Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();

if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[x][y] = newColor;
if(x + 1 < w && screenBuffer[x + 1][y] == oldColor)
{
if(!push(x + 1, y)) return;
}
if(x - 1 >= 0 && screenBuffer[x - 1][y] == oldColor)
{
if(!push(x - 1, y)) return;
}
if(y + 1 < h && screenBuffer[x][y + 1] == oldColor)
{
if(!push(x, y + 1)) return;
}
if(y - 1 >= 0 && screenBuffer[x][y - 1] == oldColor)
{
if(!push(x, y - 1)) return;
}
if(x + 1 < w && y + 1 < h && screenBuffer[x + 1][y + 1] == oldColor)
{
if(!push(x + 1, y + 1)) return;
}
if(x + 1 < w && y - 1 >= 0 && screenBuffer[x + 1][y - 1] == oldColor)
{
if(!push(x + 1, y - 1)) return;
}
if(x - 1 >= 0 && y + 1 < h && screenBuffer[x - 1][y + 1] == oldColor)
{
if(!push(x - 1, y + 1)) return;
}
if(x - 1 >= 0 && y - 1 >= 0 && screenBuffer[x - 1][y - 1] == oldColor)
{
if(!push(x - 1, y - 1)) return;
}
}
}

或者去下面网址看看
http://hi..com/%B1%FE%CF%E6/blog/item/9014b7c3c8b52f100ff4775c.html