多边形填充算法
❶ 填充算法的种子填充算法
种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。
种子填充算法常用四连通域和八连通域技术进行填充操作。
从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。
从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。
一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图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);
}
}
上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。一个改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。
❷ 求助：谁有C++的多边形扫描线填充算法的源代码！
typedef struct tEdge
{ int yUpper;
float xIntersect,dxPerScan;
struct tEdge *next;
}Edge;
void insertEdge(Edge *list Edge *edge)//将结点插入边表
{
Edge *p,*q=list;
p=q->next;
while (p!=NULL)
{ if (edge->xIntersect<p->xIntersect) p=NULL;
else { q=p; p=p->next;}
}
edge->next=q->next;
q->next=edge;
}
int yNext(int k,int cnt, dcPt *pts)//求奇异点
{
int j;
if ((k+1)>(cnt-1)) j=0;
else j=k+1;
while (pts[k].y==pts[j].y)
if((j+1)>(cnt-1)) j=0;
else j++;
return (pts[j].y);
}
void makeEdgeRec(dcPt lower,dcPt upper,int yComp, Edge *edge, Edge *edges[]) //生成边表结点，并插入到边表中
{
edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);
edge->xIntersect=lower.x;
if (upper.y<yComp)
edge->yUpper=upper.y-1;
else
edge->yUpper=upper.y;
insertEdge(edges[lower.y],edge);
}
void buildEdgeList(int cnt,dcPt *pts, Edge *edges[])//创建边表的主体函数
{
Edge *edge;
dcPt v1,v2;
int i,yPrev=pts[cnt-2].y;
v1.x=pts[cnt-1].x; v1.y=pts[cnt-1].y;
for (i=0;i<cnt;i++)
{ v2=pts[i];
if (v1.y!=v2.y)
{ edge=(Edge *)malloc(sizeof(Edge));
if (v1.y<v2.y)
makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
else makeEdgeRec(v2,v1,yPrev,edge,edges);
}
yPrev=v1.y;
v1=v2;
}
}
void buildActiveList(int scan,Edge * active,Edge *edges[])//建立活动边表的主题函数
{ Edge *p,*q;
p=edges[scan]->next;
while (p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}
void fillScan(int scan,Edge *active)//填充一对交点
{
Edge *p1,*p2;
int i
p1=active->next;
while(p1)
{
p2=p1->next;
for (i=p1->xIntersect;i<p2->xIntersect;i++)
setPixel((int)i,scan);
p1=p2->next;
}
}
void delectAfter(Edge *q)//删除链表中结点
{
Edge *p=q->next;
q->next=p->next;
free(p);
}
void updateActiveList(int scan,Edge *active)//填充完后，更新活动边表
{
Edge *q=active,*p=active->next;
while (p)
if (scan>=p->yUpper)
{
p=p->next;
deleteAfter(q);
}
else
{ p->xIntersect=p->xIntersect+p->dxPerScan;
q=p;
p=p->next;
}
}
void resortActiveList(Edge *active)//对活动边表结点重新排序
{
Edge *q,*p=active->next;
active->next=NULL;
while(p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}
void scanFill(int cnt,dcPt *pts)//多边形填充主体程序
{
Edge *edge[WINDOW_HEIGHT],*active;
int i,scan;
for (i=0;i<WINDOW_HEIGHT;i++)
{
edges[i]=(Edge *)malloc(sizeof(Edge));
edges[i]->next=NULL;
}
buildEdgeList(cnt,pts,edges);
active=(Edge *)malloc (sizeof(Edge));
active->next=NULL;
for(scan=0;scan<WINDOW_HEIGHT;scan++)
{
buildActiveList(scan,active,edges);
if (active->next)
{fillScan(sacn,active);<br/> updateActiveList(scan,active);<br/> resortActiveList(active);<br/>}
}
}
}
}
}
❸ C语言实现多边形填充
/*直角三角形，输入行数，输出*/
#include <stdio.h>
void main()/*如果TC编译不通过，则去掉void*/
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
for (int j = 0;j < i;j++)
printf("*");
printf("\n");
}
}
/*等腰三角形，输入行数，输出*/
#include <stdio.h>
void main()/*如果TC编译不通过，则去掉void*/
{
int n;
scanf("%d",&n);
for (int i = 1;i <= n;i++)
{
for (int k = 1;k <= n-i;k++)
printf(" ");
for (int j = 0;j < 2*i-1;j++)
printf("*");
printf("\n");
}
}
以上在VS2005上编译通过
❹ 边缘填充算法属于()算法一种。
边缘填充算法属于A 多边形扫描转换
❺ 用VC在mfc下编写多边形边缘填充算法，要求自动判别多边形再填充颜色，谢谢啦。
你是指把颜色填充整个多边形吗？我原来设计过一个算法可以检测所有闭合区域内的所有点，不局限于多边形，不过比较费时。需要就说
❻ 简单扫描线性填充和与边相关扫描线填充算法的区别
1. 对多边形的每一条边进行扫描转换，即对 多边形边界所经过的象素作一个边界标志。 2.填充。对每条与多边形相交的扫描线，按 从左到右的顺序，逐个访问该扫描线上的象 素。 取一个布尔变量inside来指示当前点的状态， 若点在多边形内，则inside为真。若点在多 边形外，则inside为假。 Inside 的初始值为假，每当当前访问象素为 被打上标志的点，就把inside取反。对未打 标志的点，inside不变。
❼ 求一个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安装目录下再运行。 */
❽ 简述边界表示的四连通区域的种子填充算法的基本思想和执行步骤
一、种子填充算法思想：
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
二、种子填充算法步骤：
1、初始化堆栈。
2、种子压入堆栈。
3、While（堆栈非空）从堆栈弹出种子象素。
❾ Qt4如何对闭合多边形进行填充
http://www.kuqin.com/qtdocument/qpainter.html#drawPolygon
void QPainter::drawPolygon ( const QPointArray & a, bool winding = FALSE, int index = 0, int npoints = -1 )
绘制a中，从a[index]开始（index默认为0）的npoints个点确定的多边形。
如果npoints为－1（默认），直到数组的最后的所有点都被使用（也就是说a.size()-index条线确定的多边形）。
第一个点总是被连接到最后一个点上。
多边形被当前brush()填充。如果winding为真，多边形会被使用缠绕填充算法（winding fill algorithm）填充。如果winding为假，多边形会被使用奇偶（交错）填充算法（even-odd (alternative) fill algorithm）填充。
请参考drawLineSegments()、drawPolyline()和QPen。
实例：desktop/desktop.cpp和picture/picture.cpp。