2.3.2 扫描线填色算法

2.3.2 扫描线填色算法

^{一、算法的基本思想}电脑爱好者网'R
x4S6] MH3F:E

^{多边形以n, x_array, y_array形式给出，其中x_array，y_array中存放着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：}

^{用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。多边形被扫描完毕后，填色也就完成。}

^{上述基本思想中，有几个问题需要解决或改善。它们是：}

^{1. 左、右顶点处理 当以1, 2, 3的次序画多边形外框时，多边形的左顶点和右顶点如图2.3.3 (a)、(b)所示的顶点2。它们具有性质：}

^{左顶点2：y1<y2<y3}电脑爱好者网Fy&w7X c

^{右顶点2：y1>y2>y3}电脑爱好者网*WR3V^X`q

^{其中y1, y2, y3是三个相邻的顶点的y坐标。}电脑爱好者网9jO1P8_.w|-f0Yn

^{(a)左顶点 (b)右顶点}

电脑爱好者网_Y{/I/DC

图2.3.3

^{当扫描线与多边形的每个顶点相交时，会同时产生2个交点，这是因为一个顶点同属于多边形之两条边的端点。这时，如果所交的顶点是左顶点或右顶点，填色就会因奇偶计数出错而出现错误。因此，对多边形的所有左、右顶点作如下处理；}

^{左、右顶点的入边（以该顶点为终点的那条边），即1, 2边之终点删去。即：}

^{对于左顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（,y2-1）；}

)C'C!e*Di
{/|Z0^{对于右顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（,y2+1）；}电脑爱好者网w5Xd9W&M

^{其中m=，即入边之斜率。}电脑爱好者网gz0\z
Za-D`h

^{对于多边形的上顶点（y2>y1 & y2>y3）或下顶点（y2<y1 & y2<y3），奇偶记数保持正确，因此不必修改，保持相邻边原状不变。}电脑爱好者网ap.}+n:D`yk

^{2. 水平边处理 水平边（y1=y2）与水平扫描线重合法求交点。因此，将水平边画出后删去，不参加求交及求交以后的操作。}电脑爱好者网/J/Ood5Ev*pk3x1k0X8u

^{3. 扫描线与边的求交点方法采用递归算法 边（x1, y1）（x2, y2）与扫描线i+1的交点为：}电脑爱好者网;^5[q"qXJ+V2|

.F5?VD1dSw0

^{（当交点不为x1, y1时）}电脑爱好者网#J;i%FU'w7B%c Y5`

^{否则，交点为x1, y1。}

^{由上式可知，求交点只须做两个简单的减法。}电脑爱好者网o r|;?9fp+W

^{4. 减少求交计算，采用活性边表 对于一根扫描线而言，与之相交的边只占多边形全部边的一部分。因此，在基本算法思想中，每根扫描线与多边形所有边求交的操作是一种浪费，需要加以改善。活性边表（Active List of Side）的采用将多边形的边分成两个子集：与当前扫描线相交的边的集合，以及与当前的扫描线不相交的边的集合。后者不必予以求交，这样就提高了算法的效率。}

^{(a) (b)在scan1的情况}

图2.3.4 活性边表及其指针的表示

^{活性边表的构成方法是：}电脑爱好者网g^jnuI[

^{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值相等的边之间，按任意次序排列。}

^{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的边求交即可。这就缩小了求交的范围。}电脑爱好者网 QIsAu{b|fv

^{3）活性边表中每个元素的内容包括：}电脑爱好者网WC3N\Pn

^{·边的max y值，记为y_top；}电脑爱好者网Y.lY{@b

^{·与当前扫描线相交点的x坐标值，记为x_int；}

^{·边的y方向当前总长。初始值为y2-y1。记为? y；}电脑爱好者网,e3i6d?|Q;AJG N

^{·边的斜率倒数：，记为x_change_per_scan。}

^{4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：}电脑爱好者网kx1F5j1@5oYcr6V

^{·调整first和last指针字间的参加求交的边元素之值：? y=? y-1; x_int = x_int - x_change_per_scan;}

^{·调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：}电脑爱好者网-z.P-A4M"Bn FF

^{当first所指边的? y=0时，first=first+1；}电脑爱好者网]h6A3zu
q

^{当last所指的下一条边的y_top? 下一扫描线的y值时，last=last+1。}电脑爱好者网Wn8N c:_

^{二、扫描线填色程序}

^{程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为：}

  电脑爱好者网*XN~6nN%R

图2.3.5 fill_area的程序结构电脑爱好者网}:hFA[:X:Y
\~i

typedef struct {电脑爱好者网zvm'q"EpQ?!n_zl2v

int y_top;

;na"?n}6J0

float x_int;电脑爱好者网ZyA,`:yxw%u

int delta_y;电脑爱好者网'T X3uWyCy"z\+\

floaat x_change_per_scan;电脑爱好者网r w8Bc8@J

} EACH_ENTRY;

2s^a
f&^%AeFAe&S0

EACH_ENTRY SIDES[MAX_POINT];

P&qX+}.Q)x'x\0

int x[MAX_POINT], y[MAX_POINT];电脑爱好者网@bf9q,p

int side_count, first_s, last_s, scan, bottomscan, x_int_count, r;

G+I'n5^/xft0

fill_area(count, x, y)电脑爱好者网1i?/UG izPN

int count, x[ ], y[ ];

jg{%CMC0

{电脑爱好者网ft4Q6`7mU Z

sort_on_bigger_y(count);电脑爱好者网*[@9q!olI8JR_

first_s=1;

O u8G"Q)ou2v1vX0

last_s=1;电脑爱好者网(\SU
EgAv

for (scan=sides[1].y_top; scan>bottomscan ?; scan - -)电脑爱好者网wK\Fagj#kav

   {

4^7neBcp!UT0

        up date_first_and_last(count, scan);电脑爱好者网 {0F7q:ue.`(V

        process_x_intersections(scan, first_s, last_s);

y"M w h"E~ zI9H{(G-S0

        draw_lines (scan, x_int_count, first_s);

1Uwc S:jxJ|4s0

        update-_sides_list ( );电脑爱好者网'Z!n0[BX#JiGKF

    }电脑爱好者网kQf9{Q ]r

}

5Z-X6_jy O_0

void put_in_sides_list(entry, x1, y1, x2, y2, next_y);

H$_.JJ9M0D0

int entry, x1, y1, x2, y2, next_y;电脑爱好者网[6X(n4K,| I o

{电脑爱好者网B O]8oC }+a4T[
k7~y-L

int maxy;

/w1stm*V/E8kh/m0

float x2_temp, x_change_temp;电脑爱好者网liM-\4^-~-[jz

x_change_temp = (float) (x2-x1) / (float) (y2-y1);

p:RIb/[hv,?a4X0

x2_temp =x2; /*以下为退缩一点操作. */

2d X9B[8ZX0

if ((y2>y1) && (y2<next_y)) {电脑爱好者网 C1p;~#CD2h{Fl,?

          y2 - - ;电脑爱好者网0qJ.]? z1DY

          x2_temp - = x_change_temp;电脑爱好者网P8e'j C"\0J

              }电脑爱好者网&kD8? X/a Ts:Q

else {电脑爱好者网E%k m0|(F0im{
?A

          if ((y2<y1) && (y2 >next_y)) {电脑爱好者网H!kWE7Aw

                    y2++;

A iv;g!c(Pz%B0

                    x2_temp+=x_change_temp;

5?$]5C[:G |&w]8r9V9C0

                              }

DI;BO*H0

         }

1P?`N"Z
AGhA0

/* 以下为插入活性表操作. */电脑爱好者网1}z,n9vo2w[:nh

maxy = (y1 > y2)? y1: y2;电脑爱好者网ozt3aO5xg|G

while (( entry >1) && (maxy > sides [entry -1]. y_top)) 电脑爱好者网-hT#Q] q
G m

                   {

GKvFmo.\\5IM){0

                        sides[entry]=sides [entry ?];

uH/Cf]f
}~q(L+|0

                        entry - -;

jw5dB#SN0

                   }电脑爱好者网oBFu+J3G4ulX#D"mD

sides[entry]. y_top=maxy;电脑爱好者网A(i
o { }t%~F

sides[entry]. delta_y =abs(y2-y1)+1;

Iq#Cg%j,\kr0

if (y1>y2)

+kFutb~"L9xzs0

                sides[entry]. x_int =x1;电脑爱好者网LhV4W2r ndVwi

else{电脑爱好者网C l7l6Nyv'j)J/[,W

                sides[entry].x_int=x2_temp;

R'yu#F*j/E }ydf@0

                sides[entry]. x_change_per_scan=x_change_temp;电脑爱好者网W+I3x*A2qXV

   }电脑爱好者网3k R$k @X2V

void sort_on_bigger_y(n)

3r aQ7r&d@"_l4a&J0

int n;电脑爱好者网,GF PxF1hQc

{

NE*y-Y"~0

int k, x1, y1;

l0e,?A iR*w-X\0

side_count=0;电脑爱好者网 r7e7j;y"pbg

y1=y[n];

.? qE8A h+i O1`'j0

x1=x[n];电脑爱好者网 zOn|X*r,a

bottomscan=y[n];电脑爱好者网1A6pu+DBep

　

.bBqgU0

for (k=1; k<n+1; k++)

W-[G!qau0

     {

d OL |R"Y0VO _7{0

           if (y1 ! =y[k]) {电脑爱好者网-c.k e} ],a\g

                               side_count ++;电脑爱好者网l{7H\2K#n.T@

                            put_in_sides_list(side_count, x1, y1, x[k], y[k]);

bF*Z!f%utT~i-G0

                                }电脑爱好者网]gR8u
x T9nb Z

          else {

NS"iJJ-?_0

                             move ((short)x1, (short)y1);电脑爱好者网7^&g3T@R.fo}K,eo

                             line((short)x[k], (short)y1, status);电脑爱好者网7YB!Ol6W

                  }

(l.A
s\x}2d'e0

           if (y[k] <bottomscan) bottomscan=y[k];电脑爱好者网m0wp:n:t rle\u#E

           y1=y[k]; x1=x[k];

s2DY%{ am4C0

      }电脑爱好者网-\L-],qo

}

fr @6^k%TQ3p A)MV0

void update_first_and_last(count, scan)

ZZk c!{8N0

int count, scan;

@#~;kcW0

{

y-Hz2} CJ i0

while((sides[last_s+1]. y_top>=scan) && (last_s <count)) last_s ++;电脑爱好者网o l7f
a&dy`%]A

while(sides[first_s]. delta_y = = 0) first_s ++;电脑爱好者网{;u@7r$u0Zn

}

kAJ0P\O^0

　电脑爱好者网mJ b5ZvG2L

void swap(x, y)

7AR5fmg0

EACH_ENTRY x, y;

W Rb`^){Q6?0

{电脑爱好者网Qc,~s]8r6M1tjr

int i_temp;

5xLu-^cVo2G0

float f_temp;

-V1d0O,o"idd.j0

i_temp=x.y_top; x.y_top=y.y_top; y.y_top=i_temp;

6f[ T9F_+y0

f_temp=x.x_int; x.x_int=y.x_int; y.x_int=f_temp;电脑爱好者网}'O+M/n8J9fC\ K4h ?:e

i_temp=x.delta_y; x.delta=y.delta_y; y.delta_y=i_temp;

|8P)@L)U&aI0

f_temp=x.x_change_per_scan; x. x_change_per_scan=y. x_change_per_scan; y.x.电脑爱好者网'H+U6v{0@/T0e LBy

change_per_scan=f_temp;电脑爱好者网~I dn+`kL

}电脑爱好者网#|)y,m~+ur

　电脑爱好者网!fGU9dG f;k

void sort_on_x(entry, first_s)

j{6~$`Z0

int entry, first_s;

["v!iX p,^K!D1X0

{

!?S*Fb#uO~"wF,h0

while((entry > first_s) && (sides[entry]. x_int < sides[entry-1]. x_int))电脑爱好者网sg3u@3\2F)dr

         {电脑爱好者网(|K4} f1P'nq_0^ W

               swap (sides[entry], sides[entry-1]);电脑爱好者网?$P*aQ8NkW

               entry - -;电脑爱好者网]eZ
A/h f0eZU

}

6A8D pD A(C0H E0

}

&c6Y0U2`4X)t)G0

void process_x_intersections(scan, first_s, last_s)电脑爱好者网?;I{u Kbk K

int scan, first_s, last_s;

:Ya/l2Sfg\3Z+L0

{

bI;a3J
l hVC,GP0

int k;电脑爱好者网/S iEm*oZ&jH*b

x_int_cout=0;

:Tz])m|;Vl0

for(k=first_s; k<last_s+1; k++)

+C)Cb~\0hZC1T0

{电脑爱好者网ga*e8v:F+Aq4@5u

if(sides[k]. delta_y >0) {

iJ2m[4m$_V0

                      x_int_count ++;

\yiArk$GF0

                      sort_on_x(k, first_s);

B*Pv.C{{E/V0

}

1J9jO[,o5m0

}电脑爱好者网9@['^"j4g\wD/u

}

@@{6V@&l&mX-_0

　

yM @9_o:`-d7eM0

void draw_lines(scan, x_int_count, index)

(`2zk ]+yk \-w I&|0

int scan, x_int_count, index;电脑爱好者网#g(n(U f3t5Fk7_

{电脑爱好者网1`T-k$J:{
p&\F

int k, x, x1, x2;电脑爱好者网2yNW4RhR3{N+C4Rz

for (k=1; k< (int) (x_int_count/2+1.5); k++)电脑爱好者网*i8hjEEd%y

{电脑爱好者网qi [Ak

            while(sides[index]. delta_y = = 0) index ++;电脑爱好者网Gy|nKgA F#G}6[

            x1=(int)(sides[index]. x_int +0.5);电脑爱好者网#WOLOa

            index ++;

?VY.k1I'B0

            while(sides[index].delta_y = = 0) index ++;电脑爱好者网qKV(P)nq4Gq

            x2 = (int) (sides [index]. x_int +0.5);电脑爱好者网-h"g!B _ y5g(P? |*Yb

            move((short)x1, (short)scan);电脑爱好者网1RJZ:p6g

            line((short)x2, (short)scan, status);

:r3hl*c$c/?5{0

            index ++;

AXB~*R.\o4d4b0

}电脑爱好者网Y'd7f(I#Y0UT:^

}电脑爱好者网@F9A+rx&|@ oS

void update_sides_list( )电脑爱好者网8n8o$_n3HA

{

R9b+N%v I0

int k;

'Y^y7_/ur0

for (k=first_s; k<last_s +1; k++)

)p2}7F{om"KU2k0

   {

m;k"u Uq5A?:k{0

         if(sides[k].delta_y >0)

.P5Y,w;FD#B
]%hHJ e0

                   {电脑爱好者网!C`*M-?&B$m

                         sides[k].delta_y - -;

"r.V8hdId0

                         sides[k]. x_int - = sides[k]. x_change_per_scan;

uE|:W*yg'N b)q0

                   }

^8v [ ~ b5bOrHb0

  }电脑爱好者网8}k B\rW)q m^6D%o

}电脑爱好者网l,j5W.N-I2^

　

)dK6u*i8H%c,We'U0

                       程序2.3.1 扫描线填色程序

9d:IQ/?e%YI0

^{1、sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表。操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来；如是水平边则直接画出。}电脑爱好者网t(xKWk
O

^{2、put_in_sides_list子程序的主要功能是将一条边存入活性边表之内。操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，在该边的位置中填入数据。}电脑爱好者网cNA{a2nx{W

^{3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。}

^{4、process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且? y? 0的边）按照x_int的大小排序。操作步骤是：从first到last，对每一根? y? 0的边，调用sort_on_x子程序排入活性边表中合适位置。}电脑爱好者网*W'VZ|"IW7IJ

^{5、sort_on_x子程序主要功能是将一条边side[entry]，在活性边表的first到entry之间按x_int的大小插入合适位置。操作步骤是：检查位于entry的边的x_int是否小于位置entry-1的边的x_int，如是，调用swap子程序交换两条边的彼此位置。}电脑爱好者网 c d_}T K8PI6y

^{6、swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。}电脑爱好者网H]Y2{&ai

^{7、draw_lines子程序的主要功能是在一条扫描线位于多边形内的部分，填上指定的色彩。操作步骤是：在活性边表的激活边范围内，依次取出Δy¹ 0两边的x_int，作为两个端点（x1, scan），(x2, scan)，画一条水平线。}电脑爱好者网+oBCP;t

^{8、update_sides_list子程序的主要功能是刷新活性边表内激活边的值：Δy=Dy-1}

    ^{x_int=x_int_x_chang_per_scan；}