三、改进的扫描线填充算法
扫描线填充算法的原理和实现都很简单,但是因为要同时维护“活动边表(AET)”和“新边表(NET)”,对存储空间的要求比较高。这两张表的部分内容是重复的,而且“新边表”在很多情况下都是一张稀疏表,如果能对其进行改进,避免出现两张表,就可以节省存储空间,同时省去从“边表”生成“新边表”的开销,同时也省去了用“新边表”维护“活动边表”的开销,基于这个原则可以对原始扫描线算法进行改进。
3.1重新设计“活动边表”
改进的算法仍然使用了“活动边表”的概念,但是不再构造独立的“活动边表”,而是直接在“边表”中划定一部分区间作为“活动边区间”,也就是说,把多边形的边分成两个子集,一个是与扫描线有交点的边的集合,另一个是与扫描线没有交点的边的集合。要达到这个目的,只需要对“活动边表”按照每条边的顶点ymax坐标排序即可。这个排序与原始扫描线算法中对“活动边表”的维护原理是一样的,因为只有边的ymax坐标区间内与扫描线有交点的边才可能是“活动边”。为了避免重复扫描整个“活动边表”,需要用一个first指针和一个last指针用于标识“活动边区间”。first指针之前的边都是已经处理过的边,同样,last指针之后的边都是还没有处理的边。每处理完一条扫描线,都要更新first和last指针位置,调整last指针的位置将ymax大于当前扫描线的边纳入到“活动边区间”,同时调整first指针将处理完成的边排除在“活动边区间”之外。
如果调整last指针的依据是边的ymax是否大于当前扫描线,那么调整first指针的依据是什么?也就是如何判断一条边已经处理完了?方法是在边(EDGE)定义中增加一个dy(Δy)属性,这个属性被初始化成这条边在y方向上的长度,每处理完一条扫描线,dy都要做减一处理,当dy=0时,就说明这条边已经不与扫描线相交了,可以被排除在活动边区间之外。改进的扫描线算法的“边”的完整定义如下:
7typedef struct tagEDGE2
8{
9 double xi;
10 double dx;
11 int ymax;
12 int dy;
17}EDGE2;
|
EDGE2定义中xi、dx和ymax的含义和原始算法中EDGE的定义相同,只是多了一个dy属性。
每当处理一条扫描线时,除了“活动边区间”的first指针和last指针需要调整之外,还要将first指针和last指针之间的“活动边”按照xi从小到大的顺序排序,以保证填充算法能够用正确的交点线段序列画线填充。因此,每次调整“活动边区间”的first指针和last指针之后,都要对“活动边区间”重新排序,也就是说“活动边区间”内的各边的位置并不固定,会随着扫描线的变化而相应地变化。
仍以图(6)所示的多边形为例,处理扫描线10时的“活动边表”状态如图(11-a)所示,而处理扫描线8时的“活动边表”状态则如图(11-b)所示。可以看出,当处理扫描线8时,“活动边区间”内的边的顺序有了调整,因为新加入的P6P1和P1P2两条边与扫描线的交点坐标xi比P5P6与扫描线的交点坐标xi小,因此排在P5P6前面。
图(11)改进的活动边表结构
3.2新“活动边表”的构造与调整
改进的扫描线算法的重点是“活动边表”的构造和调整。“活动边表”的构造方法如下:
(1) 首先剔除多边形各边的水平边,然后将剩下的边按照ymax的值从大到小顺序存入一个线性表中,表中第一个元素ymax值最大的表,最后一个元素是ymax值最小的边。对于各边中左、右顶点的情况需要和原始算法一样做调整,以免出现交点个数不正确的异常。这里对调整的策略再强调一下,调整都是针对边的终点进行的,对于图(10-a)所示的左顶点,需要先将P2点的坐标调整为(x2 – dx, y2 - 1),然后再求边的ymax、xi和dy。对于图(10-b)所示的右顶点,需要将P2点的坐标调整为(x2 + dx, y2 + 1),然后再求边的ymax、xi和dy。
(2) 加入first指针和last指针,构成“活动边区间”。first指针和last指针之间的边都是和当前扫描线有交点的边或已经处理过的边,已经处理过的边的dy是0,因此,对“活动边”扫描时需要忽略其中dy已经是0的边。这些已经处理过的边会加载在正常的边中,直到调整first指针时被剔除出“活动边区间”。
“活动边表”的调整指的是在处理完每根扫描线之后,更新“活动边表”中“活动边区间”内的各边的相关属性的值,比如递减dy的值,调整交点xi坐标的值等等。根据EDGE2的定义,每根扫描线处理完之后需要对“活动边区间”内的边做如下调整:
(1)调整“活动边区间”中参与求交计算的各边的属性值,这些调整算法是:
dy = dy – 1;
xi = xi – dx;
(2)调整“活动边区间”的first指针和last指针,使符合条件的新边加入到“活动边区间”,同时将处理完的边从“活动边区间”剔除。这些调整算法是:
if(first所指边的Δy为0)
first=first+1;
if(last所指的下一条边的ymax大于下一扫描线的y值)
last=last+1
3.3改进的扫描线填充算法实现
首先定义“活动边表”,这是一个线性表,每个元素是一条边的全部属性,同时还要包含first指针和last指针,其数据结构定义如下:
19typedef struct tagSP_EDGES_TABLE
20{
21 std::vector<EDGE2> slEdges;
22 int first;
23 int last;
24}SP_EDGES_TABLE;
|
改进的扫描线填充算法重点仍然是新“活动边表”的构造,这里给出构造新“活动边表”的算法实现:
36void InitScanLineEdgesTable(SP_EDGES_TABLE& spET, const Polygon& py)
37{
38 EDGE2 e;
39 for(int i = 0; i < py.GetPolyCount(); i++)
40 {
41 const Point& ps = py.pts[i];
42 const Point& pe = py.pts[(i + 1) % py.GetPolyCount()];
43 const Point& pee = py.pts[(i + 2) % py.GetPolyCount()];
44
51 if(pe.y != ps.y) //不处理水平线
52 {
53 e.dx = double(pe.x - ps.x) / double(pe.y - ps.y);
54 if(pe.y > ps.y)
55 {
56 if(pe.y < pee.y) //左顶点
57 {
58 e.xi = pe.x - e.dx;
59 e.ymax = pe.y - 1;
60 e.dy = e.ymax - ps.y + 1;
61 }
62 else
63 {
64 e.xi = pe.x;
65 e.ymax = pe.y;
66 e.dy = pe.y - ps.y + 1;
67 }
68 }
69 else //(pe.y < ps.y)
70 {
71 if(pe.y > pee.y) //右顶点
72 {
73 e.xi = ps.x;
74 e.ymax = ps.y;
75 e.dy = ps.y - (pe.y + 1) + 1;
76 }
77 else
78 {
79 e.xi = ps.x;
80 e.ymax = ps.y;
81 e.dy = ps.y - pe.y + 1;
82 }
83 }
84
85 InsertEdgeToEdgesTable(e, spET.slEdges);
86 }
87 }
88 spET.first = spET.last = 0;
89}
|
Polygon定义了一个多边形,其pts数组按照顺序存放了多边形的各个顶点,InitScanLineEdgesTable()函数从Polygon中依次取出三个顶点,前两个顶点构成当前处理的边,后一个顶点用于辅助判断是否是左、右顶点的情况,如果是左、右顶点的情况,就要对边的终点的坐标做调整(调整的方法在3.2小节已经描述)。调整完线段终点坐标后构造边e,然后由InsertEdgeToEdgesTable()函数将e插入到线性表中,插入操作满足线性表按照ymax从大到小有序,这个是插入排序的基本算法,这里就不再列出代码。
算法的另一个终点就是处理每条扫描线和“活动边表”的关系,计算出每条扫描线需要填充的区间。一下就是ProcessScanLineFill2()函数的实现:
189void ScanLinePolygonFill2(const Polygon& py, int color)
190{
191 assert(py.IsValid());
192
193 int ymin = 0;
194 int ymax = 0;
195 GetPolygonMinMax(py, ymin, ymax);
196 SP_EDGES_TABLE spET;
197 InitScanLineEdgesTable(spET, py);
198 HorizonEdgeFill(py, color); //水'cb?平'c6?边'b1?直'd6?接'bd?画'bb?线'cf?填'cc?充'b3?
199 ProcessScanLineFill2(spET, ymin, ymax, color);
200}
|
ProcessScanLineFill2()函数依次处理每条扫描线,根据3.2节的算法描述,UpdateEdgesTableActiveRange()函数和SortActiveRangeByX()函数更新“活动边区间”并对区间内的边排序,FillActiveRangeScanLine函数从“活动边区间”内依次取出两个交点组成填充区间,调用前面介绍的DrawHorizontalLine()函数完成画线填充,UpdateActiveRangeIntersection()函数则根据3.2节的算法描述更新参与求交计算的各边的属性值。这四个函数的实现都很简单,结合3.2节的算法描述很容易理解,此处仅列出代码,不做过多解释。
91void UpdateEdgesTableActiveRange(SP_EDGES_TABLE& spET, int yScan)
92{
93 std::vector<EDGE2>& slET = spET.slEdges;
94 int edgesCount = static_cast<int>(slET.size());
95 while((spET.last < (edgesCount - 1)) && (slET[spET.last + 1].ymax >= yScan))
96 {
97 spET.last++;
98 }
99
100 while(slET[spET.first].dy == 0)
101 {
102 spET.first++;
103 }
104}
|
125void FillActiveRangeScanLine(SP_EDGES_TABLE& spET, int yScan, int color)
126{
127 std::vector<EDGE2>& slET = spET.slEdges;
128 int pos = spET.first;
129
130 do
131 {
132 pos = GetIntersectionInActiveRange(spET, pos);
133 if(pos != -1)
134 {
135 int x1 = ROUND_INT(slET[pos].xi);
136 pos = GetIntersectionInActiveRange(spET, pos + 1);
137 if(pos != -1)
138 {
139 int x2 = ROUND_INT(slET[pos].xi);
140 pos++;
141 DrawHorizontalLine(x1, x2, yScan, color);
142 }
143 else
144 {
145 assert(false);
146 }
147 }
148 }while(pos != -1);
149}
150
151bool EdgeXiComparator2(EDGE2& e1, EDGE2& e2)
152{
153 return (e1.xi < e2.xi);
154}
155
156void SortActiveRangeByX(SP_EDGES_TABLE& spET)
157{
158 std::vector<EDGE2>& slET = spET.slEdges;
159
160 sort(slET.begin() + spET.first,
161 slET.begin() + spET.last + 1,
162 EdgeXiComparator2);
163}
164
165void UpdateActiveRangeIntersection(SP_EDGES_TABLE& spET)
166{
167 for(int pos = spET.first; pos <= spET.last; pos++)
168 {
169 if(spET.slEdges[pos].dy > 0)
170 {
171 spET.slEdges[pos].dy--;
172 spET.slEdges[pos].xi -= spET.slEdges[pos].dx;
173 }
174 }
175}
176
177void ProcessScanLineFill2(SP_EDGES_TABLE& spET,
178 int ymin, int ymax, int color)
179{
180 for (int yScan = ymax; yScan >= ymin; yScan--)
181 {
182 UpdateEdgesTableActiveRange(spET, yScan);
183 SortActiveRangeByX(spET);
184 FillActiveRangeScanLine(spET, yScan, color);
185 UpdateActiveRangeIntersection(spET);
186 }
187}
|
<下一篇:边标志填充算法>
分享到:
相关推荐
vs2008下 opengl实现,多边形扫描线填充算法。 用到glut库 鼠标左右键实现选点和填充
多边形扫描填充算法,填充图案为自己的学号
用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。 实验步骤 1. 复习有关算法,明确实验目的和要求; 2. 依据算法思想,绘制程序流程图(指定填充多边形); 3. 设计程序界面,要求操作方便...
多边形扫描线填充算法 未橡皮筋实现 类实现的算法 为多边形扫描线算法 未用橡皮筋多边形扫描线填充源代码实现 整个算法由类实现 包含详细的算法描述 开放源代码
python实现扫描线填充算法,使用matplotlib模块将绘制的图形保存并画出来,可以画凹多边形
编写C++MFC程序,要求在MFC的视图中利用鼠标画多边形,并按要求利用横线或竖线进行填充。利用对话框控制线的数量或密度,以及横线或竖线,并可以重复画线或填充。
使用java编程 多边形画法:先选择画图中的多边形,然后在面板里单击鼠标左键,画点...扫描线种子填充的算法适合于任意图形,不会出现部分区域填补上的现象。 程序没有任何问题~ 有不明白的可以联系我~ qq:815366795~
实现了图形学中,多边形区域的扫描线填充、扫描线种子填充算法实现,用MFC
在MFC中实现多边形填充算法,输入时只要输入多边形的顶点。
题目:用种子填充算法(或扫描线填充算法)填充任一多边形域 基本要求: (1)数据输入项为:多边形的顶点数、各顶点x,y坐标。 对于种子填充算法要输入种子象素的x,y坐标。 对于扫描线填充算法要输入扫描线间距。 ...
多边形填充的扫描线算法实现 多边形填充的扫描线算法实现
使用VS 2017实现多边形填充中的种子填充算法,此资源包括完整的项目文件,可以直接使用。此代码仅供学习交流使用。
2.通过C++语言编程实现多边形扫描转换的扫描线填充算法 多边形分类:可分为凸多边形、凹多边形、含内环多边形。 (1)凸多边形:任意两顶点间的连线均在多边形内。 (2)凹多边形:任意两顶点间的连线有不在多边形...
计算机图形学 扫描线种子填充算法实现 1、初始化堆栈。 2、种子压入堆栈。 3、while(堆栈非空) { (1)从堆栈弹出种子象素。 (2)如果种子象素尚未填充,则: a.求出种子区段:xleft、xright; b.填充...
适用于图形学的课程设计类代码,实用性较高,对广大同学有帮助的
扫描线法填充多边形,头一次写图形学相关的习题。代码有点啰嗦,而且完全没注意效率。没什么注释。但是保证可以运行。环境:QT5.0
多边形扫描线填充,opengl源程序,vc++。
基于扫描线的任意多边形填充算法
实现用扫描线算法 和种子算法对多边形进行填充 还可以画线和多边形