多边形区域填充算法.docx

13. 设五边形的五个顶点坐标为(10, 10)，(15, 5)，(12, 5)，(8, 2)和(4, 5)，利用多边形区域填充算法，编一程序生成一个实心图。
解：假设以上五个顶点依次对应编号A-B-C-D-E，首先计算得到ET表：
A
E
D
C
B
ymax
x|ymin
1/k
next
…
10
4
6/5
EA
10
15
-1
BA
6-10
5
4
5
8
-4/3
DE
5
8
4/3
DC
3
2
1
0 用于存放AET活动边表
该多边形的AET指针的内容为：
1 AET为空
5
8
-4/3
DE
5
8
4/3
DC
AET
2
DC
DE
AET
5
-4/3
28/3
-4/3
20/3
5
3
DE
-4/3
16/3
5
-4/3
32/3
5
DC
AET
4
6/5
4
10
-4/3
4
5
DC
EA
AET
5
DE
4/3
12
5
-1
15
10
BA
14
10
BA
EA
6/5
26/5
10
AET
-1
6
BA
EA
6/5
32/5
10
AET
-1
13
10
7
EA
6/5
38/5
10
AET
-1
12
10
BA
8
10
AET
-1
11
10
BA
EA
44/5
6/5
9
10
10
BA
EA
6/5
10
10
AET
-1
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) ，主要是边表结点结构体和ET边表类的实现
enum ResultCode{Success, Failure};
template <class T>
struct Enode
{
Enode() {next=NULL;}
Enode(T pymax, float pxi, float pm, Enode *pnext)
{
ymax=pymax; xi=pxi;
m=pm; next=pnext;
}
T ymax, xi; //ymax表示最大的y值，xi表示最底端点的x坐标值
float m; //m表示斜率的倒数
Enode *next;
}; //定义了ET表和AET表中结点的结构体
template <class T>
class ET
{
public:
ET(int mSize);
~ET();
ResultCode Insert(int u, T ymax, float xi, float m);
int n; //覆盖该多边形的扫描线的总数，从0开始计数
Enode<T> **a;
}; //定义了边表类
template <class T>
ET<T>::ET(int mSize)
{
n=mSize;
a=new Enode<T> *[n];
for(int i=0;i<n;i++) a[i]=0;
} //ET边表的初始化
template <class T>
ET<T>::~ET()
{
Enode<T> *p, *q;
delete a[0];
for(int i=1;i<n;i++)
{
p=a[i]; q=p;
while(p)
{
p=p->next;
delete q;
q=p;
}
}
delete []a;