算法步骤如下：
（1）初始化：构造边表。
（2）对边表进行排序，构造活性边表。
（3）对每条扫描线对应的活性边表中求交点。
（4）判断交点类型，并两两配对。
（5）对符合条件的交点之间用画线方式填充。
（6）下一条扫描线，直至满足扫描结束条件。
1.4.2 区域填充算法
这里的区域指已表示成点阵形式的填充图形，是像素的集合。区域有两种表示形式：内点表示和边界表示，如图1-15所示。内点表示，即区域内的所有像素有相同颜色；边界表示，即区域的边界点有相同颜色。区域填充指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。
区域填充算法要求区域是连通的。区域可分为4向连通区域和8向连通区域，如图1-16所示。4向连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素；8向连通区域指的是从区域内每一像素出发，可通过8个方向，即上、下、左、右、左上、右上、左下、右下这八个方向的移动的组合来到达。
图1-15 区域的内点表示和边界表示图1-16 4连通区域和8连通区域
1．区域填充的递归算法
上面讨论的多边形填充算法是按扫描线顺序进行的。种子填充算法则是假设在多边形内有一像素已知，由此出发利用连通性填充区域内的所有像素。一般采用多次递归方式。2．区域填充的扫描线算法
算法的基本过程如下：给定种子点（x，y），首先填充种子点所在扫描线上给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。
区域填充的扫描线算法可由下列3个步骤实现。
（1）初始化：确定种子点元素（x，y）。
（2）判断种子点（x，y）是否满足非边界、非填充色的条件，若满足条件，以y作为当前扫描线沿当前扫描线向左、右两个方向填充，直到边界。
（3）确定新的种子点：检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则返回步骤（2）进行扫描填充。直至区域所有元素均为填充色，程序结束。
扫描线填充算法提高了区域填充的效率。
程序设计的步骤如下：
（1）创建应用程序框架，以上述单文档程序框架为基础，创建如图1-17所示应用程序界面。
（2）编辑菜单资源。
在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-7中的定义添加编辑菜单资源。此时建好的菜单如图1-18所示。
图1-17 程序界面
表1-7菜单资源表
图1-18 程序主菜单
（3）添加消息处理函数。
利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-8建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。
表1-8菜单项的消息处理函数
（4）添加程序结构代码。
①在“基本图形的生成View.h”适当位置添加以下黑体字部分代码：
typedef struct //建立边表结构
{
int num, ymin,ymax;
float xmin,xmax,dx;
} Edge;
class CMyView : public CView
{
protected: // create from serialization only
public:
Cpoint ptset[7];
Edge edge[7],edge1[7],newedge[1];
}
②在OnDraw()函数中添加如下黑体字部分代码。
void CMyView::OnDraw(CDC* pDC)//绘制要填充的多边形
{
CMyDoc* pDoc = GetDocument();
ASSERT_V ALID(pDoc);
CPen newpen(PS_SOLID,1,RGB(255,0,0));
CPen *old=pDC->SelectObject(&newpen);
pDC->TextOut(20,20,"双击鼠标左键, 出现需填充的多边形, 点击相关功能菜单实现区域填充");
pDC->TextOut(20,50,"进行种子填充, 需用鼠标右键, 单击多边形内一点, 作为开始填充的种子点");
pDC->SelectObject(old);
}
③在菜单项的消息处理函数实体中添加以下黑体字部分代码。
void CMyView::OnScanfill() //扫描线算法进行多边形区域填充，如图1-19所示
{
CDC* pDC=GetDC();
CPen newpen(PS_SOLID,1,RGB(0,255,0));
CPen *old=pDC->SelectObject(&newpen);
int j,k,s=0;
int pmin,pmax;
for(int i=0;i<6;i++)//建立边表
{
edge[i].dx=(float)(spt[i+1].x-spt[i].
x)/(spt[i+1].y-spt[i].y);
图1-19 扫描线算法区域填充if(spt[i].y<=spt[i+1].y){
edge[i].num=i;
edge[i].ymin=spt[i].y;
edge[i].ymax=spt[i+1].y;
edge[i].xmin=(float)spt[i].x;
edge[i].xmax=(float)spt[i+1].x;
pmax=spt[i+1].y;
pmin=spt[i].y;
}
else{
edge[i].num=i;
edge[i].ymin=spt[i+1].y;
edge[i].ymax=spt[i].y;
edge[i].xmax=(float)spt[i].x;
edge[i].xmin=(float)spt[i+1].x;
pmax=spt[i].y;
pmin=spt[i+1].y;
}
}
for(int r=1;r<6;r++) //排序edge(yUpper，xIntersect)
{
for(int q=0;q<6-r;q++)
{
if(edge[q].ymin<edge[q+1].ymin)
{
newedge[0]=edge[q]; edge[q]=edge[q+1];
edge[q+1]=newedge[0];
}
}
}
for(int scan=pmax-1;scan>pmin+1;scan--)
{
int b=0;
k=s;
for(j=k;j<6;j++)
{
if((scan>edge[j].ymin)&&(scan<=edge[j].ymax))//判断与线段相交
{
if(scan==edge[j].ymax)
{
if(spt[edge[j].num+1].y<edge[j].ymax)
{
b++;
p[b]=(int)edge[j].xmax;
}
if(spt[edge[j].num-1].y<edge[j].ymax)
{
b++;
p[b]=(int)edge[j].xmax;
}
}
if((scan>edge[j].ymin)&&(scan<edge[j].ymax))
{
b++;
p[b]=(int)(edge[j].xmax+edge[j].dx*(scan-edge[j]. ymax));
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试计算机图形学画多边形(5)在线全文阅读。
相关推荐：