计算机图形学————扫描线多边形填充算法（讲解）⼀.基本原理 扫描线多边形区域填充算法是按扫描线顺序（由下到上），计算扫描线与多边形的相交区间，再⽤要求的颜⾊显⽰这些区间的象素，即完成填充⼯作。
区间的端点可以通过计算扫描线与多边形边界线的交点获得。 对于⼀条扫描线，多边形的填充过程可以分为四个步骤：
（1）求交：计算扫描线与多边形各边的交点；
（2）排序：把所有交点按x值递增顺序排序；
（3）配对：第⼀个与第⼆个，第三个与第四个等等；每对交点代表扫描线与多边形的⼀个相交区间;
（4）填⾊：把相交区间内的象素置成多边形颜⾊;
如图所⽰，扫描线 6 与多边形的边界线交于四点A、B、C、D。
这四点把扫描线分为五个区间 [0, 2]，[2, 3.5]，[3.5, 7]，[7, 11]， [11, 2]。
其中， [2, 3.5]， [7, 11] 两个区间落在多边形内，该区间内的象素应取多边形⾊。
其它区间内的象素取背景⾊。
这⾥的四个交点在计算时未必是按从左到右的顺序获得。
例如，当多边形采⽤顶点序列 P1P2P3P4P5P6 表⽰时，把扫描线 6 分别与边 P1P2，P2P3，P3P4，P4P5，P5P6，P6P1 相交，
得到交点序列D、C、B、A，必须经过排序，才能得到从左到右，按 x 递增顺序排列的
交点 x 坐标序列。
⼆.问题
（1）当扫描线与多边形顶点相交时，交点 的取舍问题（保证交点正确配对）：
检查相交顶点的两条边的另外两个顶点的y值。按这两个y值中⼤于交点y值的个数是0,1,2来决定是取零个、⼀个、还是两个。
当扫描线与多边形顶点相交时，会出现异常情况。例如图所⽰，扫描线 2 与 P1 相交。
按前述⽅法求得交点 ( x 坐标)序列：2，2，8。这将导致 [2, 8] 区间内的象素取背景⾊，
⽽这个区间的象素正是属于多边形内部，需要填充的。
所以，我们拟考虑当扫描线与多边形的顶点相交时，相同的交点只取⼀个。
这样，扫描线 2 与多边形的交点序列就成为 2，8。正是我们所希望的结果。
然⽽，按新的规定，扫描线 7 与多边形的交点序列为 2，9，11。
这将导致错把[2,9]区间作为多边形内部来填充。
为了正确地进⾏交点取舍，必须对上述两种情况区别对待。
在第⼀种情况，扫描线交于⼀顶点，⽽共享顶点的两条边分别落在扫描线的两边。
这时，交点只算⼀个。在第⼆种情况，共享交点的两条边在扫描线的同⼀边，这时交点作为零个或两个，
取决于该点是多边形的局部最⾼点还是局部最低点。
具体实现时，只需检查顶点的两条边的另外两个端点的 y 值。按这两个 y 值中⼤于交点 y 值的个数是 0，1，2 来决定是取零个、⼀个、还是⼆个。
例如，扫描线 1 交于顶点 P2，由于共享该顶点的两条边的另外⼆个顶点均⾼于扫描线，故取交点 P2 两次。
这使得 P2 象素⽤多边形颜⾊设置。
再考虑扫描线 2。在 P1 处，由于 P6 ⾼于扫描线，⽽ P2 低于扫描线，所以该交点只算⼀个。
⽽在 P6 处，由于 P1和P5均在下⽅，所以扫描线 7 与之相交时，交点算零个，该点不予填充。
//
该边(如果某⼀条边，平⾏于某⼀条扫描线；那这⼀条边，不予记录)///
（2）多边形边界上象素的取舍问题（避免填充扩⼤化）：
对扫描线与多边形的相交区间取左闭右开。
例如，对左下⾓为 (1,1)，右上⾓为(3,3)的正⽅形填充时，若对边界上所有象素均进⾏填充，
被填充的象素覆盖的⾯积为 3×3 单位，⽽⽅形实际⾯积只有 2×2 单位。显然，
这个扩⼤化问题是由于对边界上的所有象素进⾏填充引起的。
为了克服这个问题，规定落在右/上边界的象素不予填充，⽽落在左/下边界的象素予以填充。
在具体实现时，只要对扫描线与多边形的相交区间取*左闭右开*。
容易看出，我们在前⾯⼀个问题所采⽤的⽅法，即扫描线与多边形顶
点相交时，交点的取舍⽅法，保证了多边形的 “下闭上开”——丢弃上⽅⽔平边以及上⽅⾮
⽔平边上作为局部最⾼点的顶点。
重合点的处理：当扫描线和边界相交于边界顶点时，同时产⽣两个交点，通常采⽤ “起闭终开”或“起开终闭” 。
⽔平边处理：⽔平边不参加求交计算，跳过。
三. 解决步骤
为了计算每条扫描线与多边形各边的交点， 最简单的⽅法是把多边形的所有边放在⼀个表中。
这样处理效率很低。这是因为⼀条扫描线 往往只与少数⼏条边相交，甚⾄与整个多边形 都不相交。若在处理每条扫描线时，不分青红 皂⽩地把所有边都拿来与扫描线求交，则其中 决⼤多数计算都是徒劳⽆⽤的。
为了提⾼效率，在处理⼀条扫描线时，仅 对与它相交的多边形的边进⾏求交运算。我们 把与当前扫描线相交的边称为活性边，并把它 们按与扫描线交点 x 坐标递增的顺序存放在⼀个链表中，称此链表为活性边表（AET）。
假定当前扫描线与多边形某⼀条边的交点的x坐标为x，则下⼀条扫描线与该边的交点不要重计算，只要加⼀个增量△x。(连贯性)
设该边的直线⽅程为：ax+by+c=0；
若y＝yi，x=xi；则当y = yi+1时，
xi+1=xi-b/a
其中ΔX= -b/a为常数，
另外使⽤增量法计算时，我们需要知道⼀条边何时不再与下⼀条扫描线相交，以便及时把它从活性边表中删除出去。
x i+1 = ( - by i+1 –c)/a = x i –b/a 其中△x = -b/a 为常量。△x 可以存放在对应 边的活性边表结点中。另外，使⽤增量法计算时，我们需要知道⼀条边何时与下⼀条扫描线 相交，以便及时把它从活性边表中删除出去， 避免下⼀步进⾏⽆谓的计算。综上所述，活性边表的结点中⾄少应为对应边保存如下内容：
第1项存当前扫描线与边的交点坐标x值；
第2项存从当前扫描线到下⼀条扫描线间x的增量D x；
第3项存该边所交的最⾼扫描线号ymax；
第4项存指向下⼀条边的指针（Λ代表⼀条边的退出，即结束或抛弃）；
扫描线6的活性边表 ：
扫描线7的活性边表：
为了⽅便活性边表的建⽴与更新，我们为每⼀条扫描线建⽴⼀个新边表（NET），存放在该扫描线第⼀次出现的边。也就是说，若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。
1.这个结构实际上是⼀个指针数组，数组的每个变量是个指针，
这个指针指向所有的以这个y值作为起点的边。
2.把多边形所有的边全部填成这样的结构，插到这个指针数组⾥⾯来。
3.从上⾯这个指针数组⾥⾯就知道多边形是从哪⾥开始的。
在这个指针数组⾥只有1、2、3、5处有边，因此当从下往上进⾏扫描转换的时候，
从y=1开始做，⽽在1这条线上有两条边进来了，然后就把这两条边放进活性边表来处理。
4.当处理y=2这条扫描线时（活性边⾥有2条边），先看活性边表⾥是否有边要退出和加⼊，
实际上p1p2边要退出了（y=ymax），p1p6边要加⼊了。
退出的边要从活性边表⾥去掉，不退出的边要进⾏处理，即把x值加上⼀个增量。
（这时p1p2变后边需要加⼀个Λ）
5.后⾯持续步骤3,4，只到y=5这扫描线结束。
6.即每做⼀次新的扫描线时，要对已有的边进⾏三个处理：
⼀是否被去除掉；如果不被去除；
第⼆就要对它的数据进⾏更新，所谓更新数据就是要更新它的x值，即x+△x；
最后，就是有没有新的边进来，新的边在NET⾥，可以插⼊排序插进来。
四.算法描述
这个算法过程从来没有求交，这套数据结构使得你不⽤求交点！避免了求交运算。
扫描线多边形填充算法的主要步骤：
1. 建⽴NET(NewEdgeList)
2. 从最低扫描线开始到最⾼扫描线循环
3. 建⽴或调整AET(ActiveEdgeList)
4. 按照AET中的接点顺序填充
void polyfill (多边形 polygon, 颜⾊ color)
{ for (各条扫描线i )
{ 初始化新边表头指针NET [i]；把ymin = i 的边放进边表NET [i]; }
y = 最低扫描线号；
初始化活性边表AET为空；
for (各条扫描线i )
{ 把新边表NET[i]中的边结点⽤插⼊排序法插⼊AET表，使之按x坐标递增顺序排列；
遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i结点的x值递增D x；
若允许多边形的边⾃相交，则⽤冒泡排序法对AET表重新排序；
遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，⽤drawpixel (x, y, color) 改写象素颜⾊值； }
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议