📄 2.3.2 扫描线填色算法.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les232.htm -->
<HTML><HEAD><TITLE></TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR></HEAD>
<BODY>
<H3 align=justify><A name="2.3.2 扫描线填色算法"><B><FONT face=楷体_GB2312 size=4>2.3.2
扫描线填色算法</FONT></B></A></H3>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>一、算法的基本思想</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>多边形以n, x_array, y_array形式给出，其中x_array，y_array中存放着多边形的n个顶点的x,
y坐标。扫描线填色算法的基本思想是：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>上述基本思想中，有几个问题需要解决或改善。它们是：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>1. 左、右顶点处理 当以1, 2, 3的次序画多边形外框时，多边形的左顶点和右顶点如图2.3.3
(a)、(b)所示的顶点2。它们具有性质：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>左顶点2：y1<y2<y3</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>右顶点2：y1>y2>y3</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>其中y1, y2, y3是三个相邻的顶点的y坐标。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>(a)左顶点 (b)右顶点</FONT></SPAN></SUP></P>
<P align=center><FONT face=楷体_GB2312><IMG height=215
alt="2_3_3.gif (2620 bytes)" src="2.3.2 扫描线填色算法.files/2_3_3.gif"
width=182></FONT></P>
<P align=center><FONT face=楷体_GB2312>图2.3.3</FONT></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>当扫描线与多边形的每个顶点相交时，会同时产生2个交点，这是因为一个顶点同属于多边形之两条边的端点。这时，如果所交的顶点是左顶点或右顶点，填色就会因奇偶计数出错而出现错误。因此，对多边形的所有左、右顶点作如下处理；</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>左、右顶点的入边（以该顶点为终点的那条边），即1, 2边之终点删去。即：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>对于左顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（<IMG height=41
src="2.3.2 扫描线填色算法.files/Image87.gif" width=49>,y2-1）；</FONT></SPAN></SUP></P>
<P><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>对于右顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（<IMG height=41
src="2.3.2 扫描线填色算法.files/Image88.gif" width=49>,y2+1）；</FONT></SPAN></SUP></P>
<P align=justify><SPAN style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>其中</FONT></SUP><FONT face=Arial size=4><SUP>m=<IMG height=45
src="2.3.2 扫描线填色算法.files/Image90.gif" width=14><IMG height=43
src="2.3.2 扫描线填色算法.files/Image89.gif" width=51></SUP></FONT><SUP><FONT
face=楷体_GB2312 size=4>，即入边之斜率。</FONT></SUP></SPAN></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>对于多边形的上顶点（y2>y1 & y2>y3）或下顶点（y2<y1 &
y2<y3），奇偶记数保持正确，因此不必修改，保持相邻边原状不变。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>2. 水平边处理
水平边（y1=y2）与水平扫描线重合法求交点。因此，将水平边画出后删去，不参加求交及求交以后的操作。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>3. 扫描线与边的求交点方法采用递归算法 边（x1, y1）（x2,
y2）与扫描线i+1的交点为：</FONT></SPAN></SUP><FONT face=System></P></FONT>
<P><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4><IMG
height=72 src="2.3.2 扫描线填色算法.files/Image91.gif"
width=130></FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>（当交点不为x1, y1时）</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>否则，交点为x1, y1。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>由上式可知，求交点只须做两个简单的减法。</FONT></SPAN></SUP></P>
<P align=justify><SPAN style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>4. 减少求交计算，采用活性边表
对于一根扫描线而言，与之相交的边只占多边形全部边的一部分。因此，在基本算法思想中，每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改善。活性边表（Active
List of
Side）的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前的扫描线不相交的边的集合。后者不必予以求交，这样就提高了算法的效率。</FONT></SUP></SPAN></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>(a) (b)在scan1的情况</FONT></SPAN></SUP></P>
<P align=center><FONT face=楷体_GB2312> <IMG height=266
alt="2_3_4.gif (4139 bytes)" src="2.3.2 扫描线填色算法.files/2_3_4.gif"
width=410></FONT></P>
<P align=center><FONT face=楷体_GB2312>图2.3.4 活性边表及其指针的表示</FONT></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>活性边表的构成方法是：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>1）将经过左、右顶点处理及剔除水平边后的多边形之各边按照max y值排序，存入一个线性表中。表中每一个元素代表一根边。第一个元素是max
y值最大的边，最后一个元素是max y值最小的边。图2.3.4 (a)中的多边形所形成的线性表如（b）所示。其中F点和B点的y值相等，且为全部多边形的max
y的最大值。因此FG, FE, AB, BC等四边排在表之首。而C点的y值>E点的y值，所以CH排在DE前面，余类推。在max
y值相等的边之间，按任意次序排列。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>2）在上述线性表上加入两个指针first和last，即形成活性边表。这两个指针之间是与当前扫描线相交的边的集合和已经处理完（即扫描完）的边的集合。这两者的区分方法是在处理完的边上加上记号：?
y=0。在last指针以后的是尚未与当前扫描线相交的，在first指针以前的是已经处理完了的边。对于图2.3.4 (a)中扫描线scan1的情况下，图2.3.4
(b)中列出first,
last的位置。如果扫描线由上而下移到了scan2的位置，则活性边表的first应指向AB，last应指向CH。每根扫描线只须与位于first,
last之间的，而且? y? 0的边求交即可。这就缩小了求交的范围。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>3）活性边表中每个元素的内容包括：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·边的max y值，记为y_top；</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·与当前扫描线相交点的x坐标值，记为x_int；</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·边的y方向当前总长。初始值为y2-y1。记为? y；</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·边的斜率倒数：<IMG height=45 src="2.3.2 扫描线填色算法.files/Image92.gif"
width=53>，记为x_change_per_scan。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·调整first和last指针字间的参加求交的边元素之值：? y=? y-1; x_int = x_int -
x_change_per_scan;</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>·调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>当first所指边的? y=0时，first=first+1；</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>当last所指的下一条边的y_top? 下一扫描线的y值时，last=last+1。</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>二、扫描线填色程序</FONT></SPAN></SUP></P>
<P align=justify><SUP><SPAN style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count, x, y)，其中参数x,
y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为：</FONT></SPAN></SUP></P>
<P align=center><FONT face=楷体_GB2312> <IMG height=322
alt="2_3_5.gif (4681 bytes)" src="2.3.2 扫描线填色算法.files/2_3_5.gif"
width=424></FONT><FONT face=System></P>
<P align=center></FONT><FONT face=楷体_GB2312>图2.3.5 fill_area的程序结构</FONT></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>typedef struct {</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int y_top;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>float x_int;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int delta_y;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>floaat x_change_per_scan;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>} EACH_ENTRY;</FONT></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>EACH_ENTRY SIDES[MAX_POINT];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int x[MAX_POINT], y[MAX_POINT];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int side_count, first_s, last_s, scan, bottomscan, x_int_count,
r;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>fill_area(count, x, y)</FONT></P></BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int count, x[ ], y[ ];</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>sort_on_bigger_y(count);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>first_s=1;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>last_s=1;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>for (scan=sides[1].y_top; scan>bottomscan ?; scan -
-)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> {</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> up
date_first_and_last(count, scan);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
process_x_intersections(scan, first_s, last_s);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> draw_lines (scan,
x_int_count, first_s);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -