扫描线算法（S c a n-L i n e F i l l i n g）
扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指
定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。
对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》
一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以
判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是
只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还
存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就
有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，
适用于矢量图形的填充算法必须适应光栅图形设备。
2.1扫描线算法的基本思想
扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相
连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照
x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。
多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点
（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；
（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；
（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步
继续处理；
整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的
特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。
对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效
率底下，如图（6）所示：
图（6）多边形与扫描线示意图
观察多边形与扫描线的交点情况，可以得到以下两个特点：
（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；
（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线的斜
率有关；
第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动边”组成的表，称为“活动边表（AET）”。例如扫描线4的“活动边表”由P1P2和P3P4两条边组成，而扫
描线7的“活动边表”由P1P2、P6P1、P5P6和P4P5四条边组成。
第二个特点可以进一步证明，假设当前扫描线与多边形的某一条边的交点已经通过直线段
求交算法计算出来，得到交点的坐标为（x, y），则下一条扫描线与这条边的交点不需要再
求交计算，通过步进关系可以直接得到新交点坐标为（x + △x, y + 1）。前面提到过，步进关系△x是个常量，与直线的斜率有关，下面就来推导这个△x。
假设多边形某条边所在的直线方程是：ax + by + c = 0，扫描线y i和下一条扫描线y i+1与该
边的两个交点分别是（x i，y i）和（x i+1，y i+1），则可得到以下两个等式：
ax i + by i + c = 0 (等式 1)
ax i+1 + by i+1 + c = 0 (等式 2)
由等式1可以得到等式3：
x i = -(by i + c) / a (等式 3)
同样，由等式2可以得到等式4：
x i+1 = -(by i+1 + c) / a (等式 4)
由等式 4 –等式3可得到
x i+1– x i = -b (y i+1 - y i) / a
由于扫描线存在y i+1 = y i + 1的关系，将代入上式即可得到：
x i+1– x i = -b / a
即△x = -b / a，是个常量（直线斜率的倒数）。
“活动边表”是扫描线填充算法的核心，整个算法都是围绕者这张表进行处理的。要完整的定义“活动边表”，需要先定义边的数据结构。每条边都和扫描线有个交点，扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时，根据△x直接计算出新扫描线与边的交点x 坐标，可以避免复杂的求交计算。一条边不会一直待在“活动边表”中，当扫描线与之没有交点时，要将其从“活动边表”中删除，判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐标值，为此，需要记录边的y坐标的最大值。根据以上分析，边的数据结构可以定义如下：
65typedef struct tagEDGE
66{
67double xi;
68double dx;
69int ymax;
74}EDGE;
根据EDGE的定义，扫描线4和扫描线7的“活动边表”就分别如图（7）和图(8)所示：
图（7）扫描线4的活动边表
图（8）扫描线7的活动边表
前面提到过，扫描线算法的核心就是围绕“活动边表（AET）”展开的，为了方便活性边表的建立与更新，我们为每一条扫描线建立一个“新边表（NET）”，存放该扫描线第一次出现的边。当算法处理到某条扫描线时，就将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。“新边表”通常在算法开始时建立，建立“新边表”的规则就是：如果某条边的较低端点（y坐标较小的那个点）的y坐标与扫描线y相等，则该边就是扫描线y的新边，应该加入扫描线y的“新边表”。上例中各扫描线的“新边表”如下图所示：
图（9）各扫描线的新边表
讨论完“活动边表（AET）”和“新边表（NET）”，就可以开始算法的具体实现了，但是在进一步详细介绍实现算法之前，还有以下几个关键的细节问题需要明确：
（1）多边形顶点处理
在对多边形的边进行求交的过程中，在两条边相连的顶点处会出现一些特殊情况，因为此时两条边会和扫描线各求的一个交点，也就是说，在顶点位置会出现两个交点。当出现这种情况的时候，会对填充产生影响，因为填充的过程是成对选择交点的过程，错误的计算交点个数，会造成填充异常。
假设多边形按照顶点P1、P2和P3的顺序产生两条相邻的边，P2就是所说的顶点。多边
形的顶点一般有四种情况，如图（10）所展示的那样，分别被称为左顶点、右顶点、上顶
点和下顶点：
图（10）多边形顶点的四种类型
左顶点――P1、P2和P3的y坐标满足条件：y1 < y2 < y3；
右顶点――P1、P2和P3的y坐标满足条件：y1 > y2 > y3；
上顶点――P1、P2和P3的y坐标满足条件：y2 > y1 && y2 > y3；
下顶点――P1、P2和P3的y坐标满足条件：y2 < y1 && y2 < y3；
对于左顶点和右顶点的情况，如果不做特殊处理会导致奇偶奇数错误，常采用的修正方法
是修改以顶点为终点的那条边的区间，将顶点排除在区间之外，也就是删除这条边的终点，这样在计算交点时，就可以少计算一个交点，平衡和交点奇偶个数。结合前文定义的“边”数据结构：EDGE，只要将该边的ymax修改为ymax – 1就可以了。
对于上顶点和下顶点，一种处理方法是将交点计算做0个，也就是修正两条边的区间，将
交点从两条边中排除；另一种处理方法是不做特殊处理，就计算2个交点，这样也能保证
交点奇偶个数平衡。
（2）水平边的处理
水平边与扫描线重合，会产生很多交点，通常的做法是将水平边直接画出（填充），然后
在后面的处理中就忽略水平边，不对其进行求交计算。
（3）如何避免填充越过边界线
边界像素的取舍问题也需要特别注意。多边形的边界与扫描线会产生两个交点，填充时如
果对两个交点以及之间的区域都填充，容易造成填充范围扩大，影响最终光栅图形化显示
的填充效果。为此，人们提出了“左闭右开”的原则，简单解释就是，如果扫描线交点是1
和9，则实际填充的区间是[1,9），即不包括x坐标是9的那个点。
2.2扫描线算法实现
扫描线算法的整个过程都是围绕“活动边表（AET）”展开的，为了正确初始化“活动边表”，
需要初始化每条扫描线的“新边表（NET）”，首先定义“新边表”的数据结构。定义“新边表”
为一个数组，数组的每个元素存放对应扫描线的所有“新边”。因此定义“新边表”如下：
510 std::vector< std::list
ymax和ymin是多边形所有顶点中y坐标的最大值和最小值，用于界定扫描线的范围。slNet 中的第一个元素对应的是ymin所在的扫描线，以此类推，最后一个元素是ymax所在的扫描线。在开始对每条扫描线处理之前，需要先计算出多边形的ymax和ymin并初始化“新边表”：
503void ScanLinePolygonFill(const Polygon& py,int color)
504{
505 assert(py.IsValid());
506
507int ymin =0;
508int ymax =0;
509 GetPolygonMinMax(py, ymin, ymax);
510 std::vector< std::list
511 InitScanLineNewEdgeTable(slNet, py, ymin, ymax);
512//PrintNewEdgeTable(slNet);
513 HorizonEdgeFill(py, color);//水平边直接画线填充
514 ProcessScanLineFill(slNet, ymin, ymax, color);
515}
InitScanLineNewEdgeTable()函数根据多边形的顶点和边的情况初始化“新边表”，实现过程中体现了对左顶点和右顶点的区间修正原则：
315void InitScanLineNewEdgeTable(std::vector< std::list
316const Polygon& py,int ymin,int ymax)
317{
318 EDGE e;
319for(int i =0; i < py.GetPolyCount(); i++)
320{
321const Point& ps = py.pts[i];
322const Point& pe = py.pts[(i +1)% py.GetPolyCount()];
323const Point& pss = py.pts[(i -1+ py.GetPolyCount())%
py.GetPolyCount()];
324const Point& pee = py.pts[(i +2)% py.GetPolyCount()];
325
332if(pe.y != ps.y)//不处理水平线
333{
334 e.dx =double(pe.x - ps.x)/double(pe.y - ps.y);
335if(pe.y > ps.y)
336{
337 e.xi = ps.x;
338if(pee.y >= pe.y)
339 e.ymax = pe.y -1;
340else
341 e.ymax = pe.y;
342
343 slNet[ps.y - ymin].push_front(e);
344}
345else
346{
348if(pss.y >= ps.y)
349 e.ymax = ps.y -1;
350else
351 e.ymax = ps.y;
352 slNet[pe.y - ymin].push_front(e);
353}
354}
355}
356}
多边形的定义Polygon和本系列第一篇《计算几何与图形学有关的几种常用算法》一文中
的定义一致，此处就不再重复说明。算法通过遍历所有的顶点获得边的信息，然后根据与
此边有关的前后两个顶点的情况确定此边的ymax是否需要-1修正。ps和pe分别是当前
处理边的起点和终点，pss是起点的前一个相邻点，pee是终点的后一个相邻点，pss和
pee用于辅助判断ps和pe两个点是否是左顶点或右顶点，然后根据判断结果对此边的ymax进行-1修正，算法实现非常简单，注意与扫描线平行的边是不处理的，因为水平边
直接在HorizonEdgeFill()函数中填充了。
ProcessScanLineFill()函数开始对每条扫描线进行处理，对每条扫描线的处理有四个操作，如下代码所示，四个操作分别被封装到四个函数中：
467void ProcessScanLineFill(std::vector< std::list
468int ymin,int ymax,int color)
469{
470 std::list
471
472for(int y = ymin; y <= ymax; y++)
473{
474 InsertNetListToAet(slNet[y - ymin], aet);
475 FillAetScanLine(aet, y, color);
476//删除非活动边
477 RemoveNonActiveEdgeFromAet(aet, y);
478//更新活动边表中每项的xi值，并根据xi重新排序
479 UpdateAndResortAet(aet);
480}
481}
InsertNetListToAet()函数负责将扫描线对应的所有新边插入到aet中，插入操作到保证aet
还是有序表，应用了插入排序的思想，实现简单，此处不多解释。FillAetScanLine()函数执行具体的填充动作，它将aet中的边交点成对取出组成填充区间，然后根据“左闭右开”的原
则对每个区间填充，实现也很简单，此处不多解释。RemoveNonActiveEdgeFromAet()函
数负责将对下一条扫描线来说已经不是“活动边”的边从aet中删除，删除的条件就是当前扫
描线y与边的ymax相等，如果有多条边满足这个条件，则一并全部删除：
439bool IsEdgeOutOfActive(EDGE e,int y)
440{
442}
443
444void RemoveNonActiveEdgeFromAet(std::list
445{
446 aet.remove_if(std::bind2nd(std::ptr_fun(IsEdgeOutOfActive), y));
447}
UpdateAndResortAet()函数更新边表中每项的xi值，就是根据扫描线的连贯性用dx对其进行修正，并且根据xi从小到大的原则对更新后的aet表重新排序：
449void UpdateAetEdgeInfo(EDGE& e)
450{
451 e.xi += e.dx;
452}
453
454bool EdgeXiComparator(EDGE& e1, EDGE& e2)
455{
456return(e1.xi <= e2.xi);
457}
458
459void UpdateAndResortAet(std::list
460{
461//更新xi
462 for_each(aet.begin(), aet.end(), UpdateAetEdgeInfo);
463//根据xi从小到大重新排序
464 aet.sort(EdgeXiComparator);
465}
其实更新完xi后对aet表的重新排序是可以避免的，只要在维护aet时，除了保证xi从小到大的排序外，在xi相同的情况下如果能保证修正量dx也是从小到大有序，就可以避免每次对aet进行重新排序。算法实现也很简单，只需要对InsertNetListToAet()函数稍作修改即可，有兴趣的朋友可以自行修改。
至此，扫描线算法就介绍完了，算法的思想看似复杂，实际上并不难，从具体算法的实现就可以看出来，整个算法实现不足百行代码。
第二种讲解
下面这个程序能对任意多边形填充，用鼠标画一个封闭多边形，画回到起始点说明画图完毕！然后点右键填充！我用的是扫描线算法，不过在对边界点的填充上有点问题，希望高手帮忙！！！
#include
#include
#include
#define FALSE 0
#define TRUE 1
#define NULL 0
union REGS regs; /* 鼠标的变量 */
int X_max,Y_max; /* 鼠标活动范围最大值 */
int x_Origin, y_Origin,x_Old,y_Old,x_New,y_New;/* 鼠标点击的初始点,前一点和当前点的坐标 */
int PointNum=0; /* 判断鼠标是否是第一次按下 */
int LineDrawFlag=FALSE; /* 随鼠标画线标志 */
int AddFlag=TRUE; /* 边是否加入边表标志 */
int y_Now; /* 扫描线y的当前值 */
int y_Start,y_Over; /* 扫描线的起点与终点 */
typedef struct Etable /* 边表数据结构 */
{
int Ymax; /* 一条边中Y值较大点的Y值 */
float x; /* 一条边中Y值较小点的X值 */
int y; /* 一条边中Y值较小点的Y值 */
float dx; /* 一条边的斜率的倒数 */
struct Etable *next; /* 指向下一条相临边的指针 */
}ETable;
typedef struct AEtable /* 活动边表数据结构 */
{
int Ymax;
float x;
float dx;
struct AEtable *next;
}AETable;
/* 交换结点数据时用的临时指针,这个指针我放在相应函数中定义编译时会有警告并 */ AETable *temp; /* 会在程序退出时报错,不清楚原因!! */
void Initgr() /* 初始化图形模式 */
{
int gdriver=DETECT,gmode;
registerbgidriver(EGAVGA_driver);
initgraph(&gdriver,&gmode,"");
X_max=getmaxx();
Y_max=getmaxy(); /* 鼠标活动范围最大值 */
}
ETable *AddtoEtable(int x_Old,int y_Old,int x_New,int y_New,ETable *head) /* 将边加入边表 */
{ ETable *p,*q1;
p=head;
while(p->next!=NULL) /* 转到边表最后一个结点处 */
p=p->next;
q1=(ETable *)malloc(sizeof(ETable)); /* 临时建立一个结点来加入新边的信息 */
if(y_New>y_Old) /* 如果当前点比前一点高,就把当前点的Y值赋予边的Ymax */
{ q1->Ymax = y_New;
q1->x=x_Old;
q1->y=y_Old;
}
else /* 如果当然点比前一点低,就把前一点的Y值赋予边的Ymax */
{
q1->Ymax = y_Old;
q1->x=x_New;
q1->y=y_New;
}
q1->dx=(float)(x_New-x_Old)/(y_New-y_Old);
if(head->Ymax < q1->Ymax) /* 将边表中Ymax的最大值存入边表头结点,以确定扫描线的终点 */
head->Ymax=q1->Ymax;
if(head->y > q1->y) /* 将边表中 Y(它是一条边中X值较小的点的Y值) 的最大值存入边表头结点, */
head->y=q1->y; /* 以确定扫描线的起点 */
q1->next=p->next;
p->next=q1;
if(x_New==x_Origin && y_New==y_Origin) /* 如果画回到初始点,说明多边形绘制完成,停止加入边表的工作 */
AddFlag=FALSE; /* 将加入边表的标志置为假 */
return head; /* 返回边表的头指针 */
}
ETable *SortEtable(ETable *head) /* 把边表中的奇异点消除 */
(0)
?回复
?1楼
?2007-04-26 15:11
?举报 |
?bravejun20
{
ETable *p,*q;
p=head->next;
q=p->next;
while(q!=NULL) /* 如果一条边的Ymax (y)与下一条边的 y (Ymax)相等,Ymax减一,以达到消除奇异点的目的 */
{
if(p->y==q->Ymax)
q->Ymax--;
if(p->Ymax==q->y)
p->Ymax--;
if(q->y==head->next->Ymax) /* 处理最后一条边与加入的第一条边的情况 */ head->next->Ymax--;
if(q->Ymax==head->next->y)
q->Ymax--;
}
p=p->next;
q=q->next;
}
p=head->next;
q=p->next;
return head; /* 返回边表头指针 */
}
AETable *SortAEtable(AETable *head) /* 对活动边表中的边按x从小到大排序 */ { AETable *p,*q;
p=head->next;
q=p->next;
while(q!=NULL) /* 对活动边表中的边按X从小到大排序 */
{
if( p->x > q->x)
{
temp->Ymax=q->Ymax;
temp->x=q->x;
temp->dx=q->dx;
q->Ymax=p->Ymax;
q->x=p->x;
q->dx=p->dx;
p->Ymax=temp->Ymax;
p->x=temp->x;
p->dx=temp->dx;
q=q->next;
p=p->next;
}
return head; /* 返回活动边表的头指针 */
}
void AET_Fill(AETable *head,int color) /* 填充活动边表中的奇数边到偶数边间的像素 */
{
AETable *p,*q;
p=head->next;
q=p->next;
setcolor(color);
while(q!=NULL) /* 如果活动边表中有边要填充 */
{
line(p->x,y_Now+1,q->x,y_Now+1);
delay(1000);
q=q->next;
p=p->next;
if(q!=NULL) /* 如果活动边表仍不为空 */
{q=q->next;
p=p->next;
}
}
}
AETable *DeleteAETable(int Ymax,AETable *head) /* 删除活动边表中Ymax大于扫描线y的边 */
{
AETable *p,*q,*m;
p=head;
q=head->next;
while(q!=NULL)
{
if(q->Ymax==Ymax) /* 删除活动边表中边的Ymax值与当前扫描线Y值相等的所有边 */ {
p->next=q->next;
free(q);
q=head->next;
p=head;
}
else
{
q=q->next;
p=p->next;
}
}
return head;
}
void PolygonFill(ETable *head1,AETable *head2) /* 填充多边形 */
{ ETable *p1,*q1;
AETable *p2,*q2;
y_Over=head1->Ymax; /* 从边表的头结点获取扫描线的起始值 */
y_Start=head1->y; /* 从边表的头结点获取扫描线的终结值 */
head1=SortEtable(head1); /* 对边表按Y值从小到大排序 */
for( y_Now=y_Start; y_Now { p1=head1; q1=p1->next; while(q1!=NULL) /* 如果边表不为空 */ { 回复 ?2007-04-26 15:11 ?举报 | ?bravejun20 if(y_Now==q1->y) /* 如果边表中有与扫描线Y值相等的Y值,则将这些边加入活动边表 * / { p2=head2; while(p2->next!=NULL) p2=p2->next; q2=(AETable *)malloc(sizeof(AETable)); q2->Ymax = q1->Ymax; q2->x = q1->x; q2->dx = q1->dx; q2->next=p2->next; p2->next=q2; p1->next=q1->next; free(q1); /* 将边表中已经加入活动边表的边删除 */ p1=head1; q1=p1->next; } else { q1=q1->next;p1=p1->next; } } head2=SortAEtable(head2); /* 对活动边表中的边按X从小到大排序 */ AET_Fill(head2,RED); /* 填充活动边表中从奇数边到偶数边间的像素点 */ head2=DeleteAETable(y_Now,head2); /* 删除活动边表中已经填充完毕了的边 */ p2=head2->next; while(p2!=NULL) p2->x = (float)(p2->x + p2->dx); /* 将活动边表中的边的X值增加dx,即:x = x + dx; */ p2=p2->next; } } } int MouseInit(int Xp0,int Xp1,int Yp0,int Yp1) /* 初始化鼠标 */ { /* 这里的参数是鼠标活动范围的左上角坐标和右下角坐标 */ int retcode; int86(0x33,?s,?s); if(retcode==0) return 0; int86(0x33,?s,?s); int86(0x33,?s,?s); return retcode; } int MouseState(int *m_x,int *m_y,int *mstate) /* 获取鼠标状态和位置 */ { static int x0=10,y0=10,state=0; int xnew,ynew,ch; if(kbhit()) { ch=getch(); if(ch==13) { *mstate=1; return -1; } else return ch; } int86(0x33,?s,?s); }while(xnew==x0&&ynew==y0&&*mstate==state); state=*mstate; x0=xnew; y0=ynew; *m_x=xnew; *m_y=ynew; return -1; } void DrawCursor(int x,int y) /* 在鼠标当前位置画鼠标指针和跟随鼠标移动的直线*/ { int color; char str[50]; line(x-6,y,x-2,y); line(x,y-6,x,y-3); line(x+2,y,x+6,y); line(x,y+3,x,y+6); if(LineDrawFlag==TRUE) { line(x_New,y_New,x,y); color=getcolor(); setcolor(getbkcolor()); outtextxy(10,20,str); sprintf(str,"(%d,%d)",x,y); /* 显示鼠标当前的坐标值 */ setcolor(WHITE); outtextxy(10,20,str); setcolor(color); } main() { int X,Y,m_state,y,a,b,i,j; AETable *head2; ETable *head1; head1=(ETable *)malloc(sizeof(ETable)); /* 开辟边表的一个头结点来保存扫描线的起始和终结值 */ head1->Ymax=0; /* 初始化Ymax为零,以便比较得到最大的Ymax */ head1->y=10000; /* 初始化Y为10000,以便比较得到最小的Y */ head1->next=NULL; head2=(AETable *)malloc(sizeof(AETable)); /* 开辟活动边表的一个头结点,以便加入符合条件的新边 */ head2->next=NULL; 回复 ?3楼 ?2007-04-26 15:11 ?举报 | ?bravejun20 Initgr(); /* BGI初始化 */ setcolor(WHITE); setwritemode(XOR_PUT); /* 设定输入模式为异或模式 */ a=X_max;b=Y_max; m_state=0; /* 初始化鼠标状态为移动状态 */ DrawCursor(a,b); while(m_state!=2) /* 如果没有点击右键 */ { MouseState(&X,&Y,&m_state); /* 获取鼠标当前状态与坐标值 */ DrawCursor(a,b); /* 通过异或输入模式删除之前的鼠标指针 */ if(m_state==1) /* 如果鼠标左键点击 */ { LineDrawFlag=TRUE; /* 将跟随鼠标画线标志置为真 */ if(0==PointNum) /* 如果是第一次点击左键 */ { x_Origin=a;y_Origin=b; x_Old=a;y_Old=b; x_New=a;y_New=b; } else /* 如果不是第一次点击鼠标左键 */ { x_Old=x_New; y_Old=y_New; x_New=a; y_New=b; } PointNum++; /* 记录鼠标左键点击次数,以便确定是否要跟随鼠标画线 */ if((x_Origin-x_New) > -10 && (x_Origin-x_New) < 10 && (y_Origin-y_New) > -10 && (y_Origin-y_New) < 10 && ((x_Origin-x_New)!=0 || (y_Origin-y_New)!=0)) { /* 如果线画到离初始点足够近的地方 */ LineDrawFlag=FALSE; /* 将跟随鼠标画线标志置为假 */ PointNum=0; /* 鼠标点击次数清零 */ x_New=x_Origin; y_New=y_Origin; /* 将初始点的坐标值赋给当前点 */ } line(x_Old,y_Old,x_New,y_New); /* 从前一点到当前点画线 */ if( y_New!=y_Old && AddFlag==TRUE) /* 如果当前点与前一点不是同一个点并且加入边 head1=AddtoEtable(x_Old,y_Old,x_New,y_New,head1); /* 执行加入边表动作 */ } DrawCursor(X,Y); /* 在当前位置画鼠标指针 */ a=X; b=Y; } PolygonFill(head1,head2); /* 如果右键点击,刚对所画多边形进行填充,退出图形模式!!! */ DrawCursor(X,Y); getch(); closegraph(); } 13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。 解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表： 6-10 5 4 3 2 1 该多边形的AET指针的内容为： 1 AET为空 2 3 4 1 2 3 4 5 6 7 8 9 10 01234567891011121314 1516 5 6 7 8 9 10 具体编程实现如下： 第1步：(1) 根据输入的五个顶点坐标找到y 值最小的点(例如点D ，此时y=2)，并找到与D 有边关系的两个顶点(此时为E 和C)，在y=2处建立ET 边表记录(ymax 、xi 和m 值均可通过顶点坐标间的计算得到，例如DE 边的建立，特别注意：当D 点和E 点y 坐标值相同时，也即是DE 与x 轴平行，该边不能计入ET 边表)，之后标记D 点被访问过；(2) 排除访问过的点以及和该点相关联的边，重复(1)直至将ET 表建立完善。 [注]边关系的建立可通过邻接矩阵的数据结构实现，权值可以为该矩阵行编号对应点的y 坐标值，ET 边表采用邻接表的数据结构 第2步：根据ET 表构建AET 表，并逐行完成多边形填充，具体的C++代码如下： (1) 建立头文件base_class.h ，主要是边表结点结构体和ET 边表类的实现 enum ResultCode{Success, Failure}; template 扫描线算法（S c a n-L i n e F i l l i n g） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指 定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》 一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此算法可以 判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是 只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还 存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就 有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此， 适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相 连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照 x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。 多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步 继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端点的 特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。 对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而且效 率底下，如图（6）所示： 图（6）多边形与扫描线示意图 一、填空题（每空0.5分，共 1 0 分） 1、 计算机图形学中的图形是指由点、线、面、体等 和明暗、灰度（亮度）、色 彩等 构成的，从现实世界中抽象出来的带有灰度、色彩及形状的图或形。 2、 一个计算机图形系统至少应具有 、 、输入、输出、 等 基本功能。 3、 常用的字符描述方法有：点阵式、 和 。 4、 字符串剪裁的策略包括 、 和笔划/像素精确度 。 5、 所谓齐次坐标就是用 维向量表示一个n 维向量。 6、 投影变换的要素有：投影对象、 、 、投影线和投影。 7、 输入设备在逻辑上分成定位设备、描画设备、定值设备、 、拾取设备 和 。 8、 人机交互是指用户与计算机系统之间的通信，它是人与计算机之间各种符号和动作 的 。 9、 按照光的方向不同，光源分类为： ， ， 。 10、从视觉的角度看，颜色包含3个要素：即 、 和亮度。 二、单项选择题（每题 2分，共 30 分。请将正确答案的序号填在 题后的括号内） 1、在CRT 显示器系统中，（ ）是控制电子束在屏幕上的运动轨迹。 A. 阴极 B. 加速系统 C. 聚焦系统 D. 偏转系统 2、分辨率为1024×1024的显示器需要多少字节位平面数为16的帧缓存？（ ） A. 512KB B. 1MB C. 2MB D. 3MB 3、计算机图形显示器一般使用什么颜色模型？（ ） A. RGB B. CMY C. HSV D. HLS 4、下面哪个不属于图形输入设备？（ ） A. 键盘 B. 绘图仪 C. 光笔 D. 数据手套 5、多边形填充算法中，错误的描述是（ ）。 A. 扫描线算法对每个象素只访问一次，主要缺点是对各种表的维持和排序的耗费较大 B. 边填充算法基本思想是对于每一条扫描线与多边形的交点，将其右方象素取补 C. 边填充算法较适合于帧缓冲存储器的图形系统 实验四区域填充算法的实现 一、实验目的和要求： 1、掌握区域填充算法基本知识 2、理解区域的表示和类型，能正确区分四连通和八连通的区域 3、了解区域填充的实现原理，利用Microsoft Visual C++ 6.0（及EasyX_2011版） 实现区域种子填充的递归算法。 二、实验内容： 1、编程完成区域填色 2、利用画线函数，在屏幕上定义一个封闭区域。 3、利用以下两种种子填充算法，填充上述步骤中定义的区域 (1)边界表示的四连通区域种子填充的实现 (2)内点表示的四连通区域种子填充的实现 4、将上述算法作部分改动应用于八连通区域，构成八连通区域种子填充算法， 并编程实现。 三、实验结果分析 1、以上各种算法相应代码及运行结果如下： 程序代码： #include /种子填充算法 void CZhztchView::boundaryfill4(int x, int y, int boundarycolor, int newcolor) { int color; CClientDC dc(this); //获取客户区设备描述表 color=dc.GetPixel(x,y); if(color!=newcolor&&color!=boundarycolor) { dc.SetPixel(x,y,newcolor); boundaryfill4(x,y+1,boundarycolor,newcolor); boundaryfill4(x,y-1,boundarycolor,newcolor); boundaryfill4(x-1,y,boundarycolor,newcolor); boundaryfill4(x+1,y,boundarycolor,newcolor); } } ///////////////////////////////////////////////////////////////// /////////////// //扫描线填充算法 void CZhztchView::OnScanfill() { RedrawWindow(); CDC* pDC=GetDC(); CPen newpen(PS_SOLID,3,RGB(255,0,0)); CPen *old=pDC->SelectObject(&newpen); spt[0]=CPoint(100,100); //绘制多边形区域 spt[1]=CPoint(300,100); spt[2]=CPoint(250,250); spt[3]=CPoint(100,250); spt[4]=CPoint(150,200); spt[5]=CPoint(90,180); spt[6]=CPoint(150,150); spt[7]=CPoint(100,100); pDC->Polyline(spt,8); //pDC->SelectObject(old); //ReleaseDC(pDC); // TODO: Add your command handler code here //CDC* pDC=GetDC(); CPen newpen2(PS_SOLID,1,RGB(0,255,0)); CPen *old2=pDC->SelectObject(&newpen2); int j,k,s = 0; 任意封闭多边形的扫描线填充算法类收藏 这个代码不是我写的，但是我肯定这代码是一个牛人写的，放在这里供大家学习和使用啦！感谢原作者！ 我在这里做了些改进： 1 去除了绘制多边形的函数，使其成为了一个纯的填充算法模块 2 改进了其成员变量，使其更容易让大多数人所使用 3 改进了填充，使其“看”（代码上）起来更像用扫描线在填充 改进后的扫描线算法类如下： //扫描线填充算法类 class CPFill { public: CPoint *Point; //指向点坐标的指针 int Count; //多边形点的个数 public: CPFill(int,int[],int[]);//构造函数 bool FillPolygon(CDC*);//填充多边形 bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);//判断两条线段是否相交 int GetAi(int);//获取下一个点的索引号 int GetBi(int);//获取前一个点的索引号 bool Sort(int*,int);//冒泡排序 ~CPFill();//析构函数 }; //构造函数（模块入口，koradji 注，合理的设计这个地方，就可以完全不用改动其他的地方就可以使用这个类） CPFill::CPFill(){ } //获取前一个点的索引号 int CPFill::GetBi(int i) { return (i==0)? Count-1:i-1; } //获取下一个点的索引号 int CPFill::GetAi(int i) { return (i==Count-1)?0:i+1; } //在指定的pDC设备中，填充多边形 bool CPFill::FillPolygon(CDC* pDC) { //获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围 int minX=Point[0].x , minY=Point[0].y; int maxX=Point[0].x , maxY=Point[0].y; for(int i=1;i 计算机图形学四连通区域种子填充算法实 验 《计算机图形学实验》报告 任课教师：钱文华 2016年春季学期 实验:四连通区域种子填充算法 实验时间：2016年12月8日 实验地点：信息学院2204 实验目的：掌握种子填充算法的原理，并会用种子填充算法和opengl并结合使用c++语言编写程序绘制多边形。 实验原理：种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。内点的检测条件： if(interiorColor!=borderColor&&interiorColor!=fillColor)。 种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。 四向连通填充算法： a）种子像素压入栈中； b）如果栈为空，则转e)；否则转c)； c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈； d）转b）； e）结束。 四连通填充算法利用到了递归的思想。 本实验只包括四连通填充算法 程序代码：#include 计算机图形学课程设计设计题目改进的有效边表算法对多边形的填充学院名称信息科学与技术学院 专业名称计算机科学与技术 学生姓名刘柯 学生学号201213030112 任课教师梅占勇 设计（论文）成绩 教务处制 2015年9 月28 日 目录 一、设计内容与要求 (3) 1.1设计题目 (3) 1.2 设计内容 (3) 1.3 设计目标 (3) 二、总体设计 (3) 2.1 多边形的表示 (3) 2.2 x-扫描线算法 (4) 2.3 改进的有效边表算法 (4) 2.3.1 改进的有效边表算法 (4) 2.3.2 有效边表 (5) 2.3.3 边表 (6) 三、详细设计 (8) 3.1 改进的有效边表算法的实现 (8) 3.2 有效边表算法程序流程图 (9) 四、测试结果 (9) 五、总结 (15) 六、源代码 (15) 参考文献 (26) 一、设计内容与要求 1.1设计题目 用改进的有效边表算法实现多边形的填充 1.2 设计内容 使用OpenGL实现用改进的有效边表算法填充多边形 1.3 设计目标 参照课本上改进的有效边表算法的思想，实现该算法的C语言代码，并用该算法搭配OpenGL以像素点的方式绘制出给定顶点坐标的多边形。 二、总体设计 2.1 多边形的表示 在计算机图形学中，多边形有2种重要的表示方法：顶点表示和点阵表示。 顶点表示用多边形的顶点序列来刻画多边形，这种方法直观、几何意义强，占用内存少，应用普遍，但它没有明确指出哪些像素在多边形内，故不能直接用于面着色。 点阵表示用位于多边形内的像素的集合来刻画多边形。这种表示法虽然失去了许多重要的几何信息，但便于运用帧缓存表示图形，是面着色所需要的图形表示形式。 大多数图形应用系统采用顶点序列表示多边形，而顶点表示又不能直接用于显示，那么就必须有从多边形的顶点表示到点阵表示的转换，这种转换称为多边形的扫描转 课程设计报告 课程名称计算机图形学 课题名称多边形裁剪与填充 专业计算机科学与技术 班级计算机0902 学号 姓名 指导教师刘长松曹燚 2012年10 月9 日 湖南工程学院 课程设计任务书 课程名称计算机图形学课题多边形裁剪与填充 专业班级计算机0902 学生姓名 学号 指导老师刘长松曹燚 审批 任务书下达日期2012年9月15 日 任务完成日期2012 年10月9 日 一、设计内容与设计要求 1．设计内容： 交互式地实现多边形的裁剪和填充。。 2．设计要求： 1）窗口功能设计。 2）实现鼠标画多边形与数据存储功能。 3）实现鼠标剪裁窗口选择功能。 4）实现多边形裁剪和填充功能。 3.算法提示： 多边形裁剪算法分析： 基本思想是一次用窗口的一条边裁剪多边形，窗口的一条边以及延长线构成裁剪线，该线把平面分成两个部分：可见一侧，不可见一侧。用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入点。 对于每一条裁剪边，只是判断点在窗口的哪一测以及求线段与裁剪边的交点算法应随之改变。 多边形填充算法分析： 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin 和ymax），从y=ymin 到 y=ymax, 每次用一条扫描进行填充。对一条扫描线填充的过程可分为四个步骤: a.求交b.排序c.交点配对d.区间填色。 二、进度安排 第 3 周星期一8：00——12：00 星期二8：00——12：00 星期三8：00——12：00 星期四8：00——12：00 星期五8：00——12：00 第 4 周星期一8：00——12：00 附： 课程设计报告装订顺序：封面、任务书、目录、正文、附件（A4大小的图纸及程序清单）、评分。正文的格式：一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序原代码）。 扫描线算法（Scan-Line F illing） 扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏 和三维CAD软件的渲染等等。 对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种 常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断 算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但 是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交 算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢量之 间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这 个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能 是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。 2.1扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由 多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列 交点。将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个 端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下4个步骤： （1）求交，计算扫描线与多边形的交点 （2）交点排序，对第2步得到的交点按照x值从小到大进行排序； （3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进 行颜色填充； （4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然 后转第1步继续处理； 整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是 线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出 显示。 计算机图形学 ——区域填充的扫描线算法 NORTHWESTUNIVER SITY 一、实验目的 1.通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理 2.掌握多边形区域填充算法的基本过程 3.掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。 4.利用TC2.0编写区域填充的扫描线算法。 二、实验内容 算法基本思想：首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 算法描述：扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用合适的数据结构又可以简化操作、提高算法的效率。本论文由于采用链表结构记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。 扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）填色：把相交区间内的象素置成多边形颜色; 三、实验原理 扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点(x,y)入栈。 (2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。 (3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。 (4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条 实验报告 一、实验目的 1、掌握有序边表算法填充多边形区域； 2、理解多边形填充算法的意义； 3、增强C语言编程能力。 二、算法原理介绍 根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内，对于一条扫描线，多边形的扫描转换过程可以分为四个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序； （3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间; （4）着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。 p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。 为了提高效率，在处理一条扫描线时，仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中，称此链表为活性边表(AET)。 对每一条扫描线都建立一个与它相交的多边形的活性边表（AET）。每个AET的一个节点代表一条活性边，它包含三项内容 1.x -当前扫描线与这条边交点的x坐标； 2.Δx -该边与当前扫描线交点到下一条扫描线交点的x增量； 3.ymax -该边最高顶点相交的扫描线号。 每条扫描线的活性边表中的活性边节点按照各活性边与扫描线交点的x值递增排序连接在一起。 当扫描线y移动到下一条扫描线y = y+1时，活性边表需要更新，即删去不与新扫描线相交的多边形边，同时增加与新扫描线相交的多边形边，并根据增量法重新计算扫描线与各边的交点x。 当多边形新边表ET构成后，按下列步骤进行： ①对每一条扫描线i，初始化ET表的表头指针ET[i]； ②将ymax = i的边放入ET[i]中； ③使y =多边形最低的扫描线号； ④初始化活性边表AET为空； ⑤循环，直到AET和ET为空。 ●将新边表ET中对应y值的新边节点插入到AET表。 ●遍历AET表，将两两配对的交点之间填充给定颜色值。 ●遍历AET表，将 ymax= y的边节点从AET表中删除，并将ymax> y的各边节点 的x值递增Δx；并重新排序。 ●y增加1。 三、程序源代码 #include "graphics.h" #define WINDOW_HEIGHT 480 #define NULL 0 #include "alloc.h" #include "stdio.h" #include "dos.h" #include "conio.h" typedef struct tEdge /*typedef是将结构定义成数据类型*/ { int ymax; /* 边所交的最高扫描线号 */ 实验三多边形的有效边表填充算法 一、实验目的与要求 1、理解多边形的扫描转换原理、方法； 2、掌握有效边表填充算法； 3、掌握链表的建立、添加结点、删除节点的基本方法； 3、掌握基于链表的排序操作。 二、实验内容 在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类 CMyGL 中。 1、C++实现有效边表算法进行多边形扫描转换 2、利用1进行多边形扫描转换和区域填充的实现； 三、实验原理 请同学们根据教材及上课的PPT独立完成。 四、实验步骤（程序实现）。 1、建立并选择工程项目。打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。单文档。 2、新建一个图形类。选择菜单Insert New class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。 3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。 void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC) 添加其他成员函数： CreatBucket(); CreatET(); AddEdge(); EdgeOrder(); 4、成员函数的实现。实现有效边表填充算法。这一部分需要同学们去实现。 参考实现： 多边形的有效边表填充算法的基本过程为： 1、定义多边形： 2、初始化桶 3、建立边表 4、多边形填充 1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE. 2)对临时AET表排序，按照x递增的顺序存放。 3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline 4)扫描AET表，填充扫描线和多边形相交的区间。 实验六扫描线填充算法 一、实验目的 编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。 二、实验任务（2学时） 编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。 三、实验内容 1、算法 对一条扫描线的填充一般分为以下4个步骤： （1）求交：计算扫描线与多边形各边的交点； （2）排序：把扫描线上所有交点按递增顺序进行排序； （3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。 （4）着色：把区间内的像素置为填充色。 2、成员函数的关系 主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共c ount个）的x和y坐标。它调用8个子程序，彼此之间的调用关系图1所示为： 图1 fill_area的程序结构 3、算法的程序设计 步骤1：创建“S_L_Fill”工程文件； 步骤2：创建类class：“EACH_ENTRY”。 在工作区“S_L_Fill classes”单击右键-→“new class”-→选择类型“Generic Class”名称为“EACH_ENTRY”，添加成员变量（添加至“class EACH_ENTRY { public:”之内）：int y_top; float x_int; int delta_y; float x_change_per_scan; 步骤3：包含头文件，同时初始化定义多边形顶点数目。在“class CS_L_FillView : public Cview……”之前添加代码“#include EACH_ENTRY.h”及“#define MAX_POINT 9”。 #define MAX_POINT 9 #include "EACH_ENTRY.h" 步骤4：在类“class CS_L_FillView”中添加成员变量（鼠标双击工作区“CS_L_FillView”，代码添加至“class CS_L_FillView : public Cview {protected: ……public:之后”）：EACH_ENTRY sides[MAX_POINT]; int x[MAX_POINT],y[MAX_POINT]; int side_count,first_s,last_s,scan,bottomscan,x_int_count; 步骤5：利用构造函数“CS_L_FillView::CS_L_FillView()”初始化顶点坐标（鼠标双击工作区“CS_L_FillView”，代码添加至“CS_L_FillView（）之内”）： x[0]=200;y[0]=100; x[1]=240;y[1]=160; x[2]=220;y[2]=340; x[3]=330;y[3]=100; x[4]=400;y[4]=180; x[5]=300;y[5]=400; x[6]=170;y[6]=380; x[7]=120;y[7]=440; x[8]=100;y[8]=220; 步骤6：在“class CS_L_FillView”下添加实现不同功能的成员函数。在工作区“CS_L_FillView”上单击鼠标右键，选择“Add Member Function”，分别完成以下成员函数的添加： （1）void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y) 函数说明：put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，y值较大者，排在活性边表的靠前位置。 void put_in_sides_list(int entry,int x1,int y1,int x2,int y2,int next_y)// entry为剔除水平边之后的第entry条边，x1, y1,为起点，x2, y2为终点，next_y为终点相邻的下一个顶点y坐标{ int maxy; float x2_temp,x_change_temp; x_change_temp=(float)(x2-x1)/(float)(y2-y1);//计算1/k x2_temp=float(x2); if((y2>y1)&&(y2 实验三区域填充种子算法实现 实验目的： 1、熟练在Visual C＋＋中程序实现及调试的能力。 2、通过程序的设计熟练区域填充种子算法过程； 3、掌握堆栈在数据结构中的应用 实验内容： 1、visual c＋＋中菜单的修改，点的输入及鼠标函数的控制； 2、复习数据结构中堆栈的建立，入栈，出栈等函数； 3、实现整个多边形的区域填充种子算法，与扫描转换算法进行区分； 实验步骤： 预处理：多边形点列的输入，存储于数组中P[100]，种子点的输入，确定为point（x，y） 确定多边形的边界色（旧画笔色），初始色（背景色），填充色（新画笔色）； 数据结构的建立：建立堆栈，包括数组stack[100],及一个指标top，用来指向当前堆栈的最外面的栈口的元素。 步骤：1、堆栈置为空，top=0; 2、将初始的种子点point进栈，push(x,y); 3、填色堆栈非空即top>0时，一直循环下列步骤 取栈顶的元素，出栈pop(x,y)，savex=x; 从当前点开始沿当前扫描线往右检验，若有未填新色的，则填色。 然后同样往左检验。 当前扫描线俩个方向都检查完后，检验上一条扫描线y=y+1; 若有未填新色的，则把所有未填新色区间的右端点压入堆栈。 同理检验下一条扫描线y=y-2; 实验指导： 一、 在实验二的基础上进行编程 ； （1） 引入实验二代码 scanline.dsw 二、 编辑菜单资源 选中窗口左边栏的“ResourceView ”，其中的“Menu ”，双击“IDR_MAINFRAME ”，右边即为菜单，在菜单上空处双击，出项如图所示窗口，其中弹出不选中； 如上，同样创建其余菜单项。(如下表)； 三、 添加消息处理函数 由菜单的“查看”，“建立类向导”，打开ClassWizard （也可CTRL+W ）为应用程序添加与菜单项相关的消息处理函数，ClassName 栏选中CScanLineView 类，根据表建立。 输入菜单项名称，（如显示多边形） 双击，出现如下窗口 扫描线Z-Buffer算法作业说明 学号20821055 姓名邹松 联系方式zousong@https://www.doczj.com/doc/0b1607816.html, 1、SRC目录 src目录为算法源代码，编译环境为microsoft visual c++ 2005 express edition，源码中有主要步骤的注释说明。绘制时用到了OpenGL的glDrawPixels函数，需用到OpenGL库文件和头文件及glut库 2、BIN目录 bin目录为编译好的可执行程序，批处理运行程序，多个测试obj文件。 各个obj文件说明： cube.obj 为立方体模型，8个点，12个面，36条边。 cone.obj为圆台模型，146个点，288个多边形，864条边； sphere.obj为球模型，482个点，960个多边形，2880条边; teapot.obj为茶壶模型，530个点，992个多边形，2976条边; torus.obj为圆环模型，288个点，576个多边形，1728条边; torusknot.obj为环形结模型，1440个点，2880个多边形，8640条边; venusm.obj 为维纳斯像模型，19755个点，43357个多边形，130071个条边。 test.obj为我自己手工建立的obj文件，包含一个五角星和两个三角形，主要测试(凹)多边形(上面几个模型都只有三角形)，及多边形互相贯穿的情况。 可执行程序运行方式: SL_Z_buffer [file] 参数分别为obj文件名 默认分别为test.obj 直接运行run.bat文件即可对以上obj文件分别绘制出对应的图像。 使用的可执行程序为每个面片产生随机颜色 运行SL_Z_buffer可绘制test.obj 对应的图像 计算机图形学——区域填充的扫描线算法 一．实验名称： 区域填充的扫描线算法 二．实验目的： 1、理解区域填充扫描线算法的原理； 2、实现区域填充的扫描线算法并测试； 三．算法原理： 算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 借助于栈结构，区域填充的扫描线算法之步骤如下： Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈； Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点； Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。分别以xl 和xr 表示该填充区段两端点的横坐标； Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条 扫描线上位于区段[xl, xr] 内的区域内的区段。若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。 四．原程序代码： /*****************************************/ /*4-ScanLineFill 区域填充的扫描线算法实现*/ /*****************************************/ #include [最新]扫描线算法代码 #include /* Inserts edge into list in order of increasing xIntersect field. */ 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; } /* For an index, return y-coordinate of next nonhorizontal line */ 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)多边形区域填充算法
扫描线填充算法讲解
《计算机图形学》试卷及答案
区域填充算法的实现
图形学种子填充算法
扫描线填充算法
计算机图形学四连通区域种子填充算法实验上课讲义
计算机图形学课程设计-有效边表填充算法的实现
计算机图形学 多边形裁剪与填充 计算机图形学课程设计
扫描线填充算法讲解
区域填充的扫描线算法
《计算机图形学》有序边表填充算法
多边形的有效边表填充算法-
实验六 扫描线填充算法
区域填充种子算法实现
扫描线Z-Buffer算法作业说明-Read
计算机图形学-区域填充的扫描线算法
[最新]扫描线算法代码
相关主题
文本预览