下载文档原格式
扫描线多边形填充算法扫描线多边形填充算法（Scanline Polygon Fill Algorithm）是一种计算机图形学中广泛使用的算法，用于将一个封闭的多边形形状涂色填充。
它通过扫描线的方式，从上到下将多边形内的像素按照预设的填充颜色来进行填充。
本文将详细介绍扫描线多边形填充算法的原理、流程和实现细节。
1.算法原理：扫描线多边形填充算法基于扫描线的思想，在水平方向上扫描每一行像素，并检测多边形边界与扫描线的交点。
通过将扫描线从上到下扫过整个多边形，对于每一行像素，找出与多边形边界交点的水平线段，然后根据填充颜色将像素点进行填充。
2.算法流程：-找出多边形的最小和最大Y坐标，确定扫描线的范围。
-从最小Y坐标开始，到最大Y坐标结束，逐行进行扫描。
-对于每一行，找出与多边形边界交点的水平线段。
-根据填充颜色，为每个水平线段上的像素点进行填充。
3.算法实现：-首先，需要根据给定的多边形描述边界的顶点坐标，计算出每条边的斜率、最小和最大Y值以及每条边的X坐标交点。
-然后，对于每一扫描线，找出与多边形边界交点的水平线段，即找出交点的X坐标范围。
-最后，根据填充颜色，将该范围内的像素点进行填充。
4.算法优化：- 针对复杂多边形，可以使用活性边表（AET，Active Edge Table）来管理边界信息，加快查找交点的速度。
-可以使用桶排序来排序边界事件点，提高扫描速度。
-根据多边形边的特征，对算法进行优化，减少不必要的计算和内存消耗。
5.算法应用：-扫描线多边形填充算法广泛应用于计算机图形学中的图形渲染、图像处理等领域。
-在游戏开发、CAD绘图、虚拟现实等应用中，扫描线多边形填充算法被用于快速绘制和渲染复杂多边形。
总结：扫描线多边形填充算法是一种经典的计算机图形学算法，通过扫描线的方式对多边形进行填充。
它可以高效地处理各种形状的多边形，包括凸多边形和凹多边形。
算法虽然简单，但在实际应用中具有广泛的用途。
扫描线种子填充算法扫描线种子填充算法的基本过程如下：当给定种子点(x, y)时，首先分别向左和向右两个方向填充种子点所在扫描线上的位于给定区域的一个区段，同时记下这个区段的范围[xLeft, xRight]，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。
反复这个过程，直到填充结束。
扫描线种子填充算法可由下列四个步骤实现：(1) 初始化一个空的栈用于存放种子点，将种子点(x, y)入栈；(2) 判断栈是否为空，如果栈为空则结束算法，否则取出栈顶元素作为当前扫描线的种子点(x, y)，y是当前的扫描线；(3) 从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。
分别标记区段的左、右端点坐标为xLeft和xRight；(4) 分别检查与当前扫描线相邻的y - 1和y + 1两条扫描线在区间[xLeft, xRight]中的像素，从xLeft开始向xRight方向搜索，若存在非边界且未填充的像素点，则找出这些相邻的像素点中最右边的一个，并将其作为种子点压入栈中，然后返回第（2）步；这个算法中最关键的是第（4）步，就是从当前扫描线的上一条扫描线和下一条扫描线中寻找新的种子点。
如果新扫描线上实际点的区间比当前扫描线的[xLeft, xRight]区间大，而且是连续的情况下，算法的第（3）步就处理了这种情况。
如图所示：新扫描线区间增大且连续的情况假设当前处理的扫描线是黄色点所在的第7行，则经过第3步处理后可以得到一个区间[6,10]。
然后第4步操作，从相邻的第6行和第8行两条扫描线的第6列开始向右搜索，确定红色的两个点分别是第6行和第8行的种子点，于是按照顺序将（6, 10）和（8, 10）两个种子点入栈。
接下来的循环会处理（8, 10）这个种子点，根据算法第3步说明，会从（8, 10）开始向左和向右填充，由于中间没有边界点，因此填充会直到遇到边界为止，所以尽管第8行实际区域比第7行的区间[6,10]大，但是仍然得到了正确的填充。
实验二有效边表填充算法实验题目：有效边表填充算法学号：姓名：班级：指导老师：完成日期：1.实验目的：设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法2.实验描述：下图1 所示多边形覆盖了12 条扫描线，共有7 个顶点和7 条边。
7 个顶点分别为：P0（7，8），P1（3，12），P2（1，7），P3（3，1）, P4（6，5）, P5（8，1）, P6（12，9）。
在1024×768 的显示分辩率下，将多边形顶点放大为P0（500,400），P1（350，600），P2（250，350），P3（350，50）, P4（500，250）, P5（600，50）, P6（800，450）。
图1示例多边形图2屏幕显示多边形3.算法设计：多边形的有效边表填充算法的基本原理是按照扫描线从小到大的移动顺序，计算当前扫描线与多边形各边的交点，然后把这些交点按x值递增的顺序进行排序、配对，以确定填充区间，然后用指定颜色点亮填充区间的所有像素，即完成填充工作。
有效边表填充算法通过访问多边形覆盖区间内的每个像素，可以填充凸、凹多边形和环，已成为目前最为有效的多边形填充算法。
4.源程序：1）//AET.h和AET..cppclass AET{public:AET();virtual ~AET();double x;int yMax;double k; //代替1/kAET *next;}2）//Bucket.h和Bucket.cppclass Bucket{public:Bucket();virtual ~Bucket();int ScanLine;AET *p;//桶上的边表指针Bucket *next;}3) // TestView.h#include "AET.h"//包含有效边表类#include "Bucket.h"//包含桶类#define Number 7//N为闭合多边形顶点数，顶点存放在整型二维数组Point[N]中class CTestView : public CView{。
区域填充的扫描线算法区域填充是一种常见的计算机图形学算法，用于将一个封闭区域内的所有像素点填充为指定的颜色。
扫描线算法是区域填充的一种常用方法，本文将介绍扫描线算法的基本原理、实现步骤和一些优化技巧。
扫描线算法的基本原理是利用扫描线从图像的上边界向下扫描，检测每个扫描线与区域的交点。
当遇到一个交点时，根据该交点的左右两侧的交点情况，确定将该交点连接到哪个交点上。
通过不断地扫描和连接交点，最终将整个区域填充为指定的颜色。
下面是扫描线算法的具体实现步骤：1.首先需要确定区域的边界，可以由用户提供或通过其他算法生成。
边界可以用一系列的线段、多边形或曲线表示。
2. 创建一个数据结构来存储每个扫描线与区域的交点。
常用的数据结构是活性边表（Active Edge Table，AET）和扫描线填充表（Scanline Fill Table，SFT）。
AET用于存储当前扫描线与区域边界的交点，SFT用于存储所有扫描线的交点。
3.初始化扫描线的起始位置为图像的上边界，并创建一个空的AET。
4.开始扫描线的循环，直到扫描线到达图像的下边界。
每次循环都进行以下操作：-将扫描线与区域边界进行相交，找出所有与区域相交的线段，并将它们的交点加入到AET中。
-对AET按照交点的x坐标进行排序。
-从AET中取出相邻的两个交点，根据这两个交点之间的像素点是否在区域内来决定是否填充这些像素点。
5.当扫描线到达图像的下边界时，完成填充。
扫描线算法的实现可能会遇到一些边界情况和优化需求。
下面是一些常见的优化技巧：1.边界处理：在AET中存储的交点需要进行边界处理，确保交点处于图像范围内。
2.垂直线段处理：对于垂直线段，可以进行特殊处理，避免在AET中重复存储相同的交点。
3.区域内部边界处理：当区域内部有不连续的边界时，需要对交点进行合并，避免出现多余的像素点填充。
4.使用扫描线填充算法优化：对于大尺寸的区域填充，可以使用扫描线填充算法进行优化。
有效边表填充算法基本思想：⽤⽔平扫描线从上到下（或从下到上）扫描由多条⾸尾相连的线段构成的多边形，每根扫描线与多边形的某些边产⽣⼀系列的交点。
将这些交点按照x坐标排序，将排序后的点两两配对，作为线段的两个端点，以所填的颜⾊画⽔平直线。
步骤1.求交，计算扫描线与多边形的交点。
2.交点排序，对第1步得到的交点按照x从⼩到⼤排序3.颜⾊填充，对排序后的交点两两组成⼀个⽔平线段，以画线段的⽅式进⾏颜⾊填充。
4.完成多边形扫描，就结束算法，否则，继续1有效边多边形与当前扫描线相交的边成为有效边(active edge)。
在处理⼀条扫描线时仅对有效边进⾏求交运算，避免与多边形所有边求交，提⾼效率。
x y max1/k next桶表与边表有效边给出了扫描线与有效边交点的计算⽅法，但没有给出新边出现的位置坐标。
为了确定在哪条扫描线上加⼊了新边，就需要构造⼀个边表（edge table ET),⽤以存放扫描线上多边形各条边出现的信息。
⽔平边本⾝就是扫描线在建⽴边表时可以不予考虑。
桶表与边表的表⽰法桶表是按照扫描线顺序管理边出现的⼀个数据结构。
⾸先，构造⼀个纵向扫描线链表，链表的长度为多边形所占有的最⼤扫描线数，链表的每个节点称为桶(bucket）,对应多边形覆盖的每⼀条扫描线。
将每条边的信息链加⼊该边最⼩y坐标对应的桶处。
对每⼀条扫描线，如果新增多条边，按照x|y min 坐标递增的顺序存放在⼀个链表中，若x|y min 相等，则按照1/k递增，就形成边表。
x|ymin ymax1/k next。
实验题目: 实验二有效边表填充算法1.实验目的:设计有效边表结点和边表结点数据结构设计有效边表填充算法编程实现有效边表填充算法2.实验描述:下图 1 所示多边形覆盖了12 条扫描线, 共有7 个顶点和7 条边。
7 个顶点分别为：P0（7, 8）, P1（3, 12）, P2（1, 7）, P3（3, 1）, P4（6, 5）, P5（8, 1）, P6（12, 9）。
在1024×768 的显示分辩率下, 将多边形顶点放大为P0（500,400）, P1（350, 600）, P2（250, 350）, P3（350, 50）, P4（500, 250）, P5（600, 50）, P6（800, 450）。
请使用有效边表算法填充该多边形。
图1示例多边形图2 屏幕显示多边形3.算法设计:（1）建立AET和BUCKET类；（2）初始化桶, 并在建立桶结点时为其表示的扫描线初始化为带头结点的链表；（3）对每个桶结点进行循环, 将桶内每个结点的边表合并为有效边表, 并进行有效边表循环；（4）按照扫描线从小到大的移动顺序, 计算当前扫描线与多边形各边的交点, 然后把这些交点按X值递增的顺序进行排序, 配对, 以确定填充区间；（5）用指定颜色点亮填充区间内的所有像素, 即完成填充工作。
4.源程序:1)//AET.hclass AET{public:AET();virtual ~AET();double x;int yMax;double k;//代替1/kAET *next;};//AET..cppAET::AET(){}AET::~AET(){}2) //Bucket.h#include "AET.h"class Bucket{public:Bucket();virtual ~Bucket();int ScanLine;AET *p;//桶上的边表指针Bucket *next;};// Bucket.cppBucket::Bucket(){}Bucket::~Bucket(){}3)//TestView.h#include "AET.h"//包含有效边表类#include "Bucket.h"//包含桶类#define Number 7//N为闭合多边形顶点数, 顶点存放在整型二维数组Point[N]中class CTestView : public CView{。
实验六扫描线填充算法一、实验目的编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。
二、实验任务（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”下添加实现不同功能的成员函数。
代码：
draw.cpp
//using OpenGL
#include "opengl.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unistd.h>
#define PN 6
int
point[N][2]={{40,5},{75,40},{60,70},{35,50},{25,80},{5,30 }};
//AE
struct AE{
AE(float _x,float _dx,int
_ymax){x=_x;dx=_dx;ymax=_ymax;}
float x;
float dx;
int ymax;
void operator++(int){
x+=dx;
}
};
//AET
//which eage is on the right
bool fill_comp(const AE& ae1,const AE& ae2){
if(ae1.x<ae2.x){
return true;
}
if(ae1.x==ae2.x&&ae1.dx<ae2.dx){
return true;
}
return false;
}
void fillline(int y,int x1,int x2){
for(int i=x1;i<=x2;i++) drawpoint(i,y);
flush();
}
void fill(){
//make k=(x2-x1)/(y2-y1)
float k[PN]={0.0};for(int
i=0;i!=PN;i++){k[i]=((float)(point[(i+1)%PN][0]-point[i][ 0])/(float)(point[(i+1)%PN][1]-point[i][1]));}
//find min and max with selection sort.
int min=point[0][1],max=min;for(int
i=0;i!=PN;i++){if(point[i][1]>max){max=point[i][1];};;if( point[i][1]<min){max=point[i][1];}}
//make scanning line list
std::vector<AE>*ET =new std::vector<AE>[max-min+1];
//make ET
//
for(int i =0; i<PN;++i){
//get ymin, ymax
int yminn=point[i][1]<point[(i+1)%PN][1]? i :
(i+1)%PN;
int ymaxn=point[i][1]>=point[(i+1)%PN][1]? i :
(i+1)%PN;
AE *tmp =new
AE(point[yminn][0],k[i],point[ymaxn][1]);
//insert node
ET[point[yminn][1]-min].push_back(*tmp);
}
//init AET
std::vector<AE> AET;
for(int i=0;i!=max-min+1;i++){
//insert node from ET to AET
for(int ii=0;ii!=ET[i].size();ii++){
//sort with selection sort.
AET.insert(std::upper_bound(AET.begin(),
AET.end(),ET[i][ii],fill_comp),ET[i][ii]);
}
//delete y=ymax,"下闭上开"
for(int
ii=0;ii!=AET.size();){if(i+min==AET[ii].ymax)
{AET.erase(AET.begin()+ii);}else{ii++;}}
//draw
{
bool flag=false;
for(int ii=0;ii!=AET.size();ii++){
if(flag)
fillline(i+min,(int)(AET[ii-1].x+0.5),(int)(AET[ii].x+0.5 ));
//if(flag)
std::cout<<i+min<<'\t'<<(int)(AET[ii].x+0.5)<<','<<(int)( AET[ii-1].x+0.5)<<'\n';
flag=!flag;
}}
for(int ii=0;ii!=AET.size();ii++){AET[ii]++;} }
delete[](ET);
}
void draw(){
drawgrid(0.8,0.8,0.8);
setcolor(1,0.5,0.5);
fill();
draweage(point,PN);
}
int main(int n,char*avg[]){
init(n,avg,"L2");
reinit(draw);
loop();
return0;
}
opengl.h
#include <GL/glut.h>
#define N 100
#define GRIDSIZE 5
int size=N*GRIDSIZE;
void init(int argc,char** argv,char*title){
//init openGL
size = N * GRIDSIZE;
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
glutInitWindowPosition(10,10);
glutInitWindowSize(size, size);
glutCreateWindow(title);
glClearColor(1.0, 1.0, 1.0, 1.0);//white
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0.0,0.0,0.0);//black
gluOrtho2D(0, size,0, size);
}
void reinit(void(*p)()){
glutDisplayFunc(p);
}
void flush(){
glFlush();
}
void loop(){
glutMainLoop();
}
void clear(){
glClearColor(1.0, 1.0, 1.0, 1.0);//white
glClear(GL_COLOR_BUFFER_BIT);
}
void setcolor(double r,double g,double b){
glColor3f(r, g, b);
}
void drawline(int x1,int y1,int x2,int y2){
glBegin(GL_LINES);
glVertex2i(x1, y1);
glVertex2i(x2, y2);
glEnd();
flush();
}
void drawgrid(double r,double g,double b){
int i =0;
glColor3f(r, g, b);
for(i =0;i !=N *GRIDSIZE;i +=GRIDSIZE){drawline(i, 0, i, size);}
for(i =0;i !=N *GRIDSIZE;i +=GRIDSIZE){drawline(0, i, size, i);}
flush();
}
void drawpoint(int x,int y){
glPointSize((double)GRIDSIZE);
glBegin(GL_POINTS);
glVertex2i(x * GRIDSIZE, y * GRIDSIZE);
glEnd();
flush();
}
void draweage(int p[][2],int pn){
if(pn<2)return;
setcolor(0,0.8,0.8);
for(int i=0;i!=pn-1;i++){
drawline(p[i][0]*GRIDSIZE,p[i][1]*GRIDSIZE,p[i+1][0]*GRID SIZE,p[i+1][1]*GRIDSIZE);
}
drawline(p[pn-1][0]*GRIDSIZE,p[pn-1][1]*GRIDSIZE,p[0][0]* GRIDSIZE,p[0][1]*GRIDSIZE);
}
运行环境：ubuntu 13.10 + g++ 运行结果：。
