算法系列之十二：多边形区域填充算法－－改进的扫描线填充算法
source link: https://blog.csdn.net/orbit/article/details/7393022
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法系列之十二：多边形区域填充算法－－改进的扫描线填充算法
三、改进的扫描线填充算法
扫描线填充算法的原理和实现都很简单，但是因为要同时维护“活动边表（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时，就说明这条边已经不与扫描线相交了，可以被排除在活动边区间之外。改进的扫描线算法的“边”的完整定义如下：
7 typedef struct tagEDGE2
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指针，其数据结构定义如下：
19 typedef struct tagSP_EDGES_TABLE
21 std::vector<EDGE2> slEdges;
22 int first;
23 int last;
24 }SP_EDGES_TABLE;
改进的扫描线填充算法重点仍然是新“活动边表”的构造，这里给出构造新“活动边表”的算法实现：
36 void InitScanLineEdgesTable(SP_EDGES_TABLE& spET, const Polygon& py)
38 EDGE2 e;
39 for(int i = 0; i < py.GetPolyCount(); i++)
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()];
51 if(pe.y != ps.y) //不处理水平线
53 e.dx = double(pe.x - ps.x) / double(pe.y - ps.y);
54 if(pe.y > ps.y)
56 if(pe.y < pee.y) //左顶点
58 e.xi = pe.x - e.dx;
59 e.ymax = pe.y - 1;
60 e.dy = e.ymax - ps.y + 1;
62 else
64 e.xi = pe.x;
65 e.ymax = pe.y;
66 e.dy = pe.y - ps.y + 1;
69 else //(pe.y < ps.y)
71 if(pe.y > pee.y) //右顶点
73 e.xi = ps.x;
74 e.ymax = ps.y;
75 e.dy = ps.y - (pe.y + 1) + 1;
77 else
79 e.xi = ps.x;
80 e.ymax = ps.y;
81 e.dy = ps.y - pe.y + 1;
85 InsertEdgeToEdgesTable(e, spET.slEdges);
88 spET.first = spET.last = 0;
Polygon定义了一个多边形，其pts数组按照顺序存放了多边形的各个顶点，InitScanLineEdgesTable()函数从Polygon中依次取出三个顶点，前两个顶点构成当前处理的边，后一个顶点用于辅助判断是否是左、右顶点的情况，如果是左、右顶点的情况，就要对边的终点的坐标做调整（调整的方法在3.2小节已经描述）。调整完线段终点坐标后构造边e，然后由InsertEdgeToEdgesTable()函数将e插入到线性表中，插入操作满足线性表按照ymax从大到小有序，这个是插入排序的基本算法，这里就不再列出代码。
算法的另一个终点就是处理每条扫描线和“活动边表”的关系，计算出每条扫描线需要填充的区间。一下就是ProcessScanLineFill2()函数的实现：
189 void ScanLinePolygonFill2(const Polygon& py, int color)
191 assert(py.IsValid());
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);
ProcessScanLineFill2()函数依次处理每条扫描线，根据3.2节的算法描述，UpdateEdgesTableActiveRange()函数和SortActiveRangeByX()函数更新“活动边区间”并对区间内的边排序，FillActiveRangeScanLine函数从“活动边区间”内依次取出两个交点组成填充区间，调用前面介绍的DrawHorizontalLine()函数完成画线填充，UpdateActiveRangeIntersection()函数则根据3.2节的算法描述更新参与求交计算的各边的属性值。这四个函数的实现都很简单，结合3.2节的算法描述很容易理解，此处仅列出代码，不做过多解释。
91 void UpdateEdgesTableActiveRange(SP_EDGES_TABLE& spET, int yScan)
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))
97 spET.last++;
100 while(slET[spET.first].dy == 0)
102 spET.first++;
125 void FillActiveRangeScanLine(SP_EDGES_TABLE& spET, int yScan, int color)
127 std::vector<EDGE2>& slET = spET.slEdges;
128 int pos = spET.first;
130 do
132 pos = GetIntersectionInActiveRange(spET, pos);
133 if(pos != -1)
135 int x1 = ROUND_INT(slET[pos].xi);
136 pos = GetIntersectionInActiveRange(spET, pos + 1);
137 if(pos != -1)
139 int x2 = ROUND_INT(slET[pos].xi);
140 pos++;
141 DrawHorizontalLine(x1, x2, yScan, color);
143 else
145 assert(false);
148 }while(pos != -1);
151 bool EdgeXiComparator2(EDGE2& e1, EDGE2& e2)
153 return (e1.xi < e2.xi);
156 void SortActiveRangeByX(SP_EDGES_TABLE& spET)
158 std::vector<EDGE2>& slET = spET.slEdges;
160 sort(slET.begin() + spET.first,
161 slET.begin() + spET.last + 1,
162 EdgeXiComparator2);
165 void UpdateActiveRangeIntersection(SP_EDGES_TABLE& spET)
167 for(int pos = spET.first; pos <= spET.last; pos++)
169 if(spET.slEdges[pos].dy > 0)
171 spET.slEdges[pos].dy--;
172 spET.slEdges[pos].xi -= spET.slEdges[pos].dx;
177 void ProcessScanLineFill2(SP_EDGES_TABLE& spET,
178 int ymin, int ymax, int color)
180 for (int yScan = ymax; yScan >= ymin; yScan--)
182 UpdateEdgesTableActiveRange(spET, yScan);
183 SortActiveRangeByX(spET);
184 FillActiveRangeScanLine(spET, yScan, color);
185 UpdateActiveRangeIntersection(spET);
<下一篇：边标志填充算法>
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK