下载文档原格式
计算机图形学的主要内容
1、数值微分法、中点画线法、Bresenham画线法、中点画圆法。
2、有序边表算法、边填充算法、边标志算法、扫描线填充算法。
3、线宽、线型的处理。
4、线段裁剪的Cohen-SutherLand裁剪算法、中点分割算法、参
数化裁剪算法，多边形裁剪。
5、反走样：提高分辨率法、简单区域采样、加权区域采样。
6、参数曲线的代数形式和几何形式，Hermite曲线的调和函数。
7、Bezier曲线及其性质，B样条曲线及其性质。
8、二次三次Bezier曲线、B样条曲线。
9、双三次参数曲面的代数形式与几何形式。
10、Coons曲面，双线性、双二次、双三次Bezier曲面，双线性、
双二次、双三次B样条曲面。
11、图形的几何变换和投影变换。
《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础1.边填充算法对于每一条扫描线和每条多边形的交点（x1,y1），将该扫描线上的交点右方的所有像素取补。
2.种子填充算法利用栈来实现种子填充算法。
种子像素入栈，当栈非空时重复执行如下步骤：将栈顶像素出栈，将出栈像素置成多边形色，按左，上，右，下顺序检查与出栈像素相邻的四个像素，若其中某个像素不再边界且未置成多边形，则把该像素入栈！三、算法设计与分析1、边填充算法void CEdge_mark_fillView::OnDraw(CDC* pDC){CEdge_mark_fillDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);int d[500][500]={0};int inside;int x,y;Bresenham(80,101,100,400,d);Bresenham(100,300,290,400,d);Bresenham(292,400,382,50,d);Bresenham(380,50,202,150,d);Bresenham(200,150,82,101,d);for(y=0;y<500;y++){inside=0;for(x=0;x<500;x++){if(d[x][y]==1)if(d[x+1][y]!=1){inside=!(inside);}if(inside!=0)pDC->SetPixel(x,y,12);}}}2、种子填充int x=299,y=51;COLORREF oldcolor;COLORREF newcolor;oldcolor=RGB(256,256,256);newcolor=RGB(123,123,123);pDC->MoveTo (40,40);pDC->LineTo (80,40);pDC->LineTo (70,80);pDC->LineTo (40,40);FloodFill(51,51,RGB(255,255,255),RGB(0,0,255));pDC->LineTo (40,40);void CMyView::FloodFill(int x,int y,COLORREF oldcolor,COLORREF newcolor) {CDC* pDC;pDC=GetDC();if(pDC->GetPixel(x,y)==oldcolor){pDC->SetPixel(x,y,newcolor);FloodFill(x,y-1,oldcolor,newcolor);FloodFill(x,y+1,oldcolor,newcolor);FloodFill(x-1,y,oldcolor,newcolor);FloodFill(x+1,y,oldcolor,newcolor);}四、程序调试及结果的分析1、2、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。
多边形填充算法-有序边表法（扫描线算法）1.算法的基本思想（扫描线连贯性原理）： 对于⼀个给定的多边形，⽤⼀组⽔平(垂直)的扫描线进⾏扫描，对每⼀条扫描线均可求出与多边形边的交点，这些交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段；并且⼆者相间排列。
于是，将落在多边形内部的线段上的所有象素点赋以给定的⾊彩值。
算法中不需要检验每⼀个象素点，⽽只考虑与多边形边相交的交点分割后的扫描线段。
2.算法求解：对于每⼀条扫描线的处理：1）求交点：⾸先求出扫描线与多边形各边的交点；2）交点排序：将这些交点按X坐标递增顺序排序；3）交点匹配：即从左到右确定落在多边形内部的那些线段；4）区间填充：填充落在多边形内部的线段。
3.求交点的⽅法最简单的办法：将多边形的所有边放在⼀个表中，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。
不使⽤该⽅法的原因：将做⼀些⽆益的求交点动作，因为扫描线并不⼀定与多边形的边相交，扫描线只与部分甚⾄较少的边相交；因此，在进⾏扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。
确定与扫描线相交的边：⽤边表来确定哪些边是下⼀条扫描线求交计算时应该加⼊运算的。
4.边表（ET）：ET的意义在于为扫描线提供待加⼊的新边信息。
建⽴边的分类表ET(Edge Table)，每个结点结构如下：（Ymax ，ΔX ，X Ymin，）Ymax：边的最⼤Y值；ΔX：从当前扫描线到下⼀条扫描线之间的X增量（dX/ dY)；X Ymin：边的下端点的X坐标；next：指针，指向下⼀条边。
边的分类表可以这样建⽴：先按下端点的纵坐标(y值)对所有边作桶分类，再将同⼀组中的边按下端点X坐标递增的顺序进⾏排序, X坐标还相同的按ΔX递增的顺序进⾏排序。
5.活性边表AET把与当前扫描线相交的边称活化边AEL(Active Edge List) 。
组成的表称为活性表AET，其数据域组成如下：Ymax ：存放边的上端点Y坐标；X ：边与当前扫描线交点的X坐标；ΔX ，next指针：同边表。
计算机图形学多边形填充算法计算机图形学中的多边形填充算法是指将给定的多边形区域进行颜色填充，以使其完全填充的过程。
在图形学中，多边形是由一系列连续的线段组成的封闭图形。
填充算法可用于渲染图形、绘制图像等应用场景。
多边形填充算法的目标是根据设计要求和用户输入，给定一个多边形的边界，将多边形的内部区域进行颜色填充。
填充算法的实现涉及到图像的扫描线和区域判定，以确定填充的区域和颜色。
在本文中，我们将介绍常见的多边形填充算法，包括扫描线填充算法、边界填充算法等，并讨论它们的优缺点和适用场景。
扫描线填充算法扫描线填充算法是一种常见且简单的多边形填充算法。
该算法将多边形划分为一条条水平扫描线，并通过判断扫描线与多边形边界的交点，确定填充区域。
具体步骤如下：1.找到多边形边界的最上端和最下端。
2.从最上端开始，逐行进行扫描。
3.在每一行，通过求解扫描线与多边形边界的交点，确定填充区域。
4.对于每个填充区域，根据设计要求进行颜色填充。
扫描线填充算法的优点是简单易懂、实现较为容易。
然而，该算法存在一些缺点。
首先，对于具有复杂形状的多边形，扫描线填充算法可能会产生很多不必要的计算，导致效率降低。
其次，该算法需要处理多边形边界相交的情况，可能出现像素重复填充的问题，需要进行额外的处理。
边界填充算法边界填充算法是另一种常见的多边形填充算法。
与扫描线填充算法不同的是，边界填充算法是从多边形的边界出发，向内部填充颜色。
该算法的基本思想是对多边形的每条边进行填充，最终得到多边形的填充区域。
具体步骤如下：1.遍历多边形的每条边，保存每条边的起点和终点。
2.对于每个边，根据设计要求进行颜色填充。
3.对于多边形内部的区域，根据边界的颜色填充。
边界填充算法的优点是适用于复杂形状的多边形，无需处理边界相交的问题。
然而，该算法的实现相对复杂，需要处理边界的细化以及边缘像素重复填充的问题。
适用场景不同的多边形填充算法在不同场景下有不同的适用性。
![有序边表算法_计算机图形学实用教程（第3版）_[共3页]](https://img.taocdn.com/s1/m/c0624a128bd63186bdebbc7a.png)
65 3.4.3 有序边表算法1．简单的有序边表算法由于3.4.2小节介绍的一般多边形的扫描线填充算法是建立在按扫描顺序对多边形的边与扫描线交点进行排序的基础上的，所以称为有序边表算法。
将简单的有序边表算法描述如下。
（1）数据准备。
① 求出多边形各条边与中心扫描线的交点，并将各交点坐标(x , y +0.5)存入表中。
② 按扫描线以及扫描线上交点x 值的递增顺序对该表中存放的交点进行排序，形成有序边表。
（2）扫描转换。
① 按(x 1, y 1)和(x 2, y 2)成对地取出有序边表中的交点坐标值，表的构造保证有y = y 1 = y 2及 x 1≤ x 2。
② 在扫描线y 上激活那些x 的整数值满足x 1≤ x +0.5≤ x 2关系的像素。
2．简单有序边表算法的效率问题及解决方法简单的有序边表算法存在3个问题：一是需要生成一个很大的交点表，而且需要对整张表排序；二是求交计算中含有乘除法运算，运算复杂；三是交点计算的次数多，这是因为在计算交点时，相当于是把多边形的所有边放在一个表中，按顺序依次取出，计算该边与当前扫描线的交点，而事实上并非所有的边都与当前扫描线有交点，因此增加了许多不必要的求交计算量。
可见，求交和交点排序的计算量大是影响该算法效率的最主要的因素，为了提高算法的效率，应该尽量减少和简化求交计算。
那么如何减少和简化求交计算呢？采用活性边表的有序边表算法可以有效解决这个问题。
采用活性边表的有序边表算法与简单有序边表算法的不同之处在于，它对每条扫描线都建立一个活性边表。
那么什么是活性边和活性边表呢？我们把与当前扫描线有交点的边，称为活性边，而把用于存储活性边的表称为活性边表。
在每一个活性边表中，活性边按与扫描线交点x 坐标递增的顺序存放在一个链表中。
因此，采用活性边表后，不仅节省了求交的时间，而且还节省了交点排序的时间。
下面的问题是，在活性边表中应该存储活性边的哪些信息呢？由于存储活性边的目的是要保证存储的这些信息对计算活性边与扫描线的交点有用。
多边形区域填充算法－－扫描线填充算法（有序边表法）有代码⼆、扫描线算法（Scan-Line Filling）转载 https:///u013044116/article/details/49737585扫描线算法适合对⽮量图形进⾏区域填充，只需要直到多边形区域的⼏何位置，不需要指定种⼦点，适合计算机⾃动进⾏图形处理的场合使⽤，⽐如电脑游戏和三维CAD软件的渲染等等。
对⽮量多边形区域填充，算法核⼼还是求交。
⼀⽂给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利⽤此算法可以判断⼀个点是否在多边形内，也就是是否需要填充，但是实际⼯程中使⽤的填充算法都是只使⽤求交的思想，并不直接使⽤这种求交算法。
究其原因，除了算法效率问题之外，还存在⼀个光栅图形设备和⽮量之间的转换问题。
⽐如某个点位于⾮常靠近边界的临界位置，⽤⽮量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（⽮量点没有⼤⼩概念，光栅图形设备的点有⼤⼩概念），因此，适⽤于⽮量图形的填充算法必须适应光栅图形设备。
2.1扫描线算法的基本思想扫描线填充算法的基本思想是：⽤⽔平扫描线从上到下（或从下到上）扫描由多条⾸尾相连的线段构成的多边形，每根扫描线与多边形的某些边产⽣⼀系列交点。
将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜⾊画⽔平直线。
多边形被扫描完毕后，颜⾊填充也就完成了。
扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第2步得到的交点按照x值从⼩到⼤进⾏排序；（3）颜⾊填充，对排序后的交点两两组成⼀个⽔平线段，以画线段的⽅式进⾏颜⾊填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；整个算法的关键是第1步，需要⽤尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显⽰。
第一章：计算机图形学：怎样用计算机生成、处理和显示图像的学科。
图形：能够在人们视觉系统中形成视觉印象的对象称为图形，包括自然景物和人工绘图。
数字图像处理：针对图像进行各种加工以改善图像的效果,为图像分析做准备。
位图：显示屏幕上的矩形阵列的0,1表示。
图形：计算机图形学的研究对象，能在人的视觉系统中产生视觉印象的客观对象，包括自然景物、拍摄到的图片、用数学方法描述的图形等等像素：构成屏幕（图像）的最小元素。
分辨率：阴极射线管在水平或垂直方向单位长度上能识别的最大像素个数。
颜色查找表：是一维线性表、其每一项的内容对应一种颜色，其长度由帧缓存单元的位数决定。
作用：在帧缓存单元位数不增加的情况下，具有大范围内挑选颜色的能力；对颜色进行索引光栅扫描式图形显示器（画点设备）：帧缓存（数字设备）+寄存器+DAC（数模转换）+电子枪+光栅显示器（模拟设备）具有N个位面的帧缓存，颜色查找表至少有N位字宽（实际为W，W>N），有2n项，可同时显示2n个颜色（灰度级），总共可以有2w个。
（全色光栅扫描图形显示器/全色帧缓存：三种原色电子枪，每种原色的电子枪有8个位面，组合成224种颜色，帧缓存至少为24位，每组原色配一个颜色查找表）显卡作用：根据CPU提供的指令和有关数据将程序运行过程和结果进行相应处理、并转换成显示器能够接受的文字和图形显示信号，通过屏幕显示出来。
虚拟现实系统：由计算机生成的一个实时的三维空间。
虚拟现实系统的3I特性：沉浸（immersion）、交互（interaction）、想象（imagination）第二章：图形标准：图形系统及其相关应用系统中各界面之间进行数据传送和通信的接口标准，以及供图形应用程序调用的子程序功能及其格式标准。
前者称为数据及文件格式标准，后者称为子程序界面标准。
（计算机图形接口（CGI）、计算机图元文件（CGM）、图形核心系统（GKS）、程序员层次交互式图形系统（PHIGS）、基本图形转换规范（IGES）、产品数据模型转换标准（STEP）、计算机图形参考模型（CGRM））图形系统标准的作用：方便不同系统间的数据交换；方便程序移植；硬件隔离，实现图形系统的硬件无关性。
复习题1.以计算机中所记录的形状参数与属性参数来表示图形的一种方法叫做______，一般把它描述的图形叫做______；而用具有灰度或颜色信息的点阵来表示图形的一种方法是______，它强调图形由哪些点组成，并具有什么灰度或色彩，一般把它描述的图形叫做______。
A ．参数法、图形、点阵法、图像C ．参数法、图像、点阵法、图形下列设备中属于图形输出设备的是______。
B ．点阵法、图像、参数法、图形D ．点阵法、图形、参数法、图像2.①鼠标②LCD ③键盘④LED ⑤打印机⑥扫描仪⑦绘图仪⑧触摸屏A ．○1○3○6○8B ．○2○4○5○7C ．○2○5○6○7D ．○4○6○7○83.计算机显示器设备一般使用什么颜色模型______。
A ．RGB B ．CMYK C ．HSV D ．HLS 4.灰度等级为256，分辨率为1024*1024的显示器，至少需要的帧缓存容量为______。
A ．512KB B ．1MB C ．2MB D ．3MB 5.多边形填充算法中，错误的描述是______。
A ．有序边表算法对每个象素只访问一次，主要缺点是对各种表的维持和排序的耗费较大。
B ．边填充算法基本思想是对于每一条扫描线与多边形的交点，将其右方象素取补。
C ．边填充算法较适合于帧缓冲存储器的图形系统。
D ．边标志算法也不能解决象素被重复访问的缺点。
在多边形的逐边裁剪法中，对于某条多边形的边（方向为从端点S 到端点P ）与某条裁剪线（窗口的某一边）的比较结果共有以下四种情况，分别需输出一些顶点。
请问哪种情况下输出的顶点是错误的______。
A ．S 和P 均在可见的一侧，则输出S 和P B ．S 和P 均在不可见的一侧，则输出0个顶点C ．S 在可见一侧，P 在不可见一侧，则输出线段SP 与裁剪线的交点D ．S 在不可见的一侧，P 在可见的一侧，则输出线段SP 与裁剪线的交点和P 下面关于反走样的论述哪个是错误的______。
实验报告一、实验目的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; /* 边所交的最高扫描线号 */float x; /*当前扫描线与边的交点的x值 */ float dx; /*从当前扫描线到下一条扫描线之间的x增量*/ struct tEdge *next;}Edge;typedef struct point{int x,y;}POINT;/*将结点插入边表的主体函数*/void InsertEdge(Edge *list,Edge *edge)/*活性边edge插入活性边表list中*/ {Edge *p,*q=list;p=q->next; /*记住q原来所指之结点*/ while(p!=NULL) /*按x值非递减顺序增加边表*/ {if(edge->x<p->x) /*要插入的边的x较大不应该在当前插入*/p=NULL;else /*要插入的边的x较小应该在当前插入*/{q=p;p=p->next;}}edge->next=q->next; /*使欲插入之结点edge指向q原来所指之结点*/ q->next=edge; /*使q指向插入之结点*/ }int yNext(int k,int cnt,POINT *pts)/*对于多边形中的某个顶点序号k(0,1...6)，返回下一顶点的纵坐标,如果这2个顶点所在边是水平的，则顺延，即返回第(k+2)个顶点的纵坐标),cnt是顶点个数+1,pts指向多边形顶点结构体的指针*/{int j;if((k+1)>(cnt-1))/*当前顶点为最后一个顶点，则下一个顶点为第0个顶点 */ j=0;elsej=k+1; /*当前顶点不是最后一个顶点，下一个顶点为数组下标加一*/ while(pts[k].y==pts[j].y)/*扫描线扫过平行顶点，需分情况找到当前顶点下下个顶点*/if((j+1)>(cnt-1))j=0;elsej++;return(pts[j].y); /*返回下一个顶点的y值 */ }/* 计算增量，修改AET*//*生成边表结点，并插入到边表中的主体函数*/void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge *edge,Edge*edges[])/*把边结点edge,放到lower.y扫描线所在的边结点指针数组edges[]中 */{edge->dx=(float)(upper.x-lower.x)/(upper.y-lower.y);edge->x=lower.x;if(upper.y<yComp) /*遵循“下闭上开”原则*/ edge->ymax=upper.y-1; /*缩短上层顶点*//*奇点，应该把这点当作两个点而分开，所以把y的最大值减一，向下移动*/elseedge->ymax=upper.y; /*不是奇点，不需改变y值 */ insertEdge(edges[lower.y],edge); /*插入一个边缘扫描线，插入到列表 */ }/*创建边表的主体函数*/void BuildEdgeList(int cnt,POINT *pts,Edge *edges[])/*建立新边表,cnt:多边形顶点个数+1,edges[]:指向活性边结点的指针数组*/{Edge *edge;POINT v1,v2;int i,yPrev=pts[cnt-2].y;/*当前顶点的前一个顶点的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));edge=(Edge*)malloc(sizeof(Edge));if(v1.y<v2.y)/*当前顶点不是奇点，建立边表时使用下一个顶点的y值即yNext*/ MakeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);/*确定v1,v2边较高端点的开闭*/ elseMakeEdgeRec(v2,v1,yPrev,edge,edges); /*当前顶点是奇点*/ }yPrev=v1.y;v1=v2;}}/*建立活性边表的主体函数：建立第scan条扫描线的活性边表*/void BuildActiveList(int scan,Edge *active,Edge *edges[])/*建立扫描线scan的活性边表,把活性边结点放入扫描线scan的结点指针数组edges[scan]中*/{Edge *p,*q;p=edges[scan]->next; /*查找当前扫描线对应的y桶*/while(p) /*y桶不空*/ {q=p->next; /*找到最后一个边结点，插入*/InsertEdge(active,p); /*把更新后的边表重新插入边表中保存*/p=q;}}/*填充一对交点的主体函数*/void FillScan(int scan,Edge *active,int color)/*填充扫描线:填充扫描线上,且在下一结点到再下一结点之间的点*/{Edge *p1,*p2;int i;p1=active->next;while(p1){p2=p1->next;for(i=p1->x;i<p2->x;i++)putpixel((int)i,scan,color); /*画出图形内部的点*/ p1=p2->next; /*活性表的下一条边表 */}}void DeleteAfter(Edge *q)/*删除链表中结点,删除边结点q的后续结点p*/ {Edge *p=q->next;q->next=p->next; /*删除结点*/free(p);}/* 删除 y=ymax 的边 *//*填充完后，更新活动边表的主体函数*/void UpdateActiveList(int scan,Edge *active)/*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/ {Edge *q=active,*p=active->next;while(p)if(scan>=p->ymax) /*扫描线超过边的最大y值，此条边的节点应该删掉*/{p=p->next;deleteAfter(q);}else /*扫描线未超过边的最大y值，相应的x值增加*/{p->x=p->x+p->dx;q=p;p=p->next;}}/*对活性边表结点重新排序的主体函数*/void ResortActiveList(Edge *active)/*活性边表active中的结点按x域从小到大重新排序*/{Edge *q,*p=active->next;active->next=NULL;while(p){q=p->next;InsertEdge(active,p); /*把更新后的边表重新插入边表中保存 */p=q;}}/*多边形填充的主体程序*/void ScanFill(int cnt,POINT *pts,int color)/*填充函数,输入:多边形顶点个数+1=cnt, 指向多边形顶点的指针数组pts*/ {Edge *edges[WINDOW_HEIGHT],*active;int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;for(i=0;i<cnt-1;i++) /*求扫描线的最大值最小值*/ {if(scanmax<pts[i].y)scanmax=pts[i].y;if(scanmin>pts[i].y)scanmin=pts[i].y;}for(scan=scanmin;scan<=scanmax;scan++) /*初始化每条扫面线的边链表*/ {edges[scan]=(Edge *)malloc(sizeof(Edge)); /*建“桶”*/edges[scan]->next=NULL;}BuildEdgeList(cnt,pts,edges); /*建立有序边表*/ active=(Edge *)malloc(sizeof(Edge));active->next=NULL;for(scan=scanmin;scan<=scanmax;scan++) /*扫描每条扫描线，求活性表*/ {BuildActiveList(scan,active,edges); /*建立活性边表*/if(active->next) /*活性边表不为空*/{ FillScan(scan,active,color); /*填充当前扫描线*/ UpdateActiveList(scan,active); /*更新活化边表*/ ResortActiveList(active); /*重排活化边表*/ }}}/*开始菜单*/void main(){POINT pts[7]; /*保存数组*/int gdrive=DETECT,gmode;pts[0].x=100;pts[0].y=40; /*多边形顶点x、y坐标*/pts[1].x=220;pts[1].y=140;pts[2].x=280;pts[2].y=80;pts[3].x=350;pts[3].y=300;pts[4].x=200;pts[4].y=380;pts[5].x=50;pts[5].y=280;pts[6].x=100;pts[6].y=40; /*合并桶中的新边，按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,"C:\\TC3.0\\BGI"); /*设置graphic模式*/ ScanFill(7,pts,2);getch();}四、实验结果图1 用有序边表算法生成的多边形五、总结与体会实验步骤1)分析多边形区域扫描线填充算法的原理，确定算法流程①初始化：构造边表，AET表置空②将第一个不空的ET表中的边插入AET表③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色④y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。
