2.3.2 扫描线填色算法

2.3.2 扫描线填色算法

^{一、算法的基本思想}电脑爱好者网%lA3D+e&S?+?

^{多边形以n, x_array, y_array形式给出，其中x_array，y_array中存放着多边形的n个顶点的x, y坐标。扫描线填色算法的基本思想是：}电脑爱好者网/\1GO#jjms

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

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

^{1. 左、右顶点处理 当以1, 2, 3的次序画多边形外框时，多边形的左顶点和右顶点如图2.3.3 (a)、(b)所示的顶点2。它们具有性质：}电脑爱好者网6{'?6X)d@&pr6[.H@

^{左顶点2：y1<y2<y3}

^{右顶点2：y1>y2>y3}

^{其中y1, y2, y3是三个相邻的顶点的y坐标。}电脑爱好者网B5PPJ
Cu(z)g8qDf

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

图2.3.3电脑爱好者网a"oP j z

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

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

^{对于左顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（,y2-1）；}电脑爱好者网+og?
b%r

H},G5lJ0^{对于右顶点：入边（x1, y1）（x2, y2）修改为（x1, y1）（,y2+1）；}电脑爱好者网5u+{ E2h4F$L

^{其中m=，即入边之斜率。}

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

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

^{3. 扫描线与边的求交点方法采用递归算法 边（x1, y1）（x2, y2）与扫描线i+1的交点为：}

Yw.j.I#i0

^{（当交点不为x1, y1时）}电脑爱好者网'wE*U(a"x5F1M2sP/I'S%~

^{否则，交点为x1, y1。}电脑爱好者网(wD|A"m~;}5k

^{由上式可知，求交点只须做两个简单的减法。}

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

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

图2.3.4 活性边表及其指针的表示电脑爱好者网 @g6Wtv2S#@wD

^{活性边表的构成方法是：}电脑爱好者网h%f%Cx%Crdm)o

^{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的边求交即可。这就缩小了求交的范围。}

^{3）活性边表中每个元素的内容包括：}电脑爱好者网So1sS9@!e/`!V

^{·边的max y值，记为y_top；}电脑爱好者网9{q$^Bmik D

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

^{·边的y方向当前总长。初始值为y2-y1。记为? y；}

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

^{4）活性边在每根扫描线扫描之后刷新。刷新的内容有2项：}

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

^{·调整first和last指针，以便让新边进入激活范围，处理完的边退出激活范围：}电脑爱好者网z!t1\$?I0S@%`

^{当first所指边的? y=0时，first=first+1；}电脑爱好者网O&ny;ZSl$B_

^{当last所指的下一条边的y_top? 下一扫描线的y值时，last=last+1。}

^{二、扫描线填色程序}电脑爱好者网 wH6eyz3T

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

图2.3.5 fill_area的程序结构电脑爱好者网"E2L4u8y7[+[u;Vc.?

typedef struct {

.Wzm4xm0

int y_top;

d!^9A:jI s|0

float x_int;电脑爱好者网!m6dX7QXt

int delta_y;

k3W-f/y/cs#q0

floaat x_change_per_scan;电脑爱好者网 H1n.b+E$AqK G

} EACH_ENTRY;

tP2BP6Z:[q[0

　电脑爱好者网YT#d)dC]%p3\M"I

EACH_ENTRY SIDES[MAX_POINT];

#W+E,[W%Q;EKN0

int x[MAX_POINT], y[MAX_POINT];

k
G5J+oU$`0

int side_count, first_s, last_s, scan, bottomscan, x_int_count, r;电脑爱好者网H.n u4QPRG3Q(f

fill_area(count, x, y)

t4Mb_*L7r^da0

int count, x[ ], y[ ];

!d:rI!~gjR A0

{

9d&U4?@6F j0

sort_on_bigger_y(count);电脑爱好者网$[]"@.C Uo\xVb

first_s=1;电脑爱好者网8qI3IeXN k"pY F

last_s=1;

/a'e jhY8IE {0

for (scan=sides[1].y_top; scan>bottomscan ?; scan - -)

3cYl"|K1KS0

   {电脑爱好者网_[TPg,DF9U4ZP

        up date_first_and_last(count, scan);电脑爱好者网qV'i&b"B5{w

        process_x_intersections(scan, first_s, last_s);

1M4rv+b \'|%t5J~0

        draw_lines (scan, x_int_count, first_s);电脑爱好者网e{#zPEX]

        update-_sides_list ( );电脑爱好者网d"\vF^/p

    }电脑爱好者网6E.R,X/D*W7_.G

}

Z2Y8ym-na0

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

,B&Y:n\(I.Z{y0

int entry, x1, y1, x2, y2, next_y;

J$_w%]O"_0

{

FzJh.i%G V?0

int maxy;电脑爱好者网a*K1i+M5\;@

float x2_temp, x_change_temp;电脑爱好者网 x(S/i t7M}:et

x_change_temp = (float) (x2-x1) / (float) (y2-y1);电脑爱好者网gs`
Y L
R$oe`-z/q

x2_temp =x2; /*以下为退缩一点操作. */电脑爱好者网~4[ Ti8Q4wC

if ((y2>y1) && (y2<next_y)) {电脑爱好者网)gn4Wo:]?e%U

          y2 - - ;电脑爱好者网(iOgM}0B-`

          x2_temp - = x_change_temp;

,P%L'pFb&fht0

              }电脑爱好者网
W$|7R1JRN%Y

else {

R3ng-Eh Mr7L0

          if ((y2<y1) && (y2 >next_y)) {

?d7f z6h-L0

                    y2++;

%B `f rF5_0

                    x2_temp+=x_change_temp;电脑爱好者网5[iYkdz(PF5Q

                              }电脑爱好者网7uG'@l];cg2cu

         }

8Q$Gtr[Y0

/* 以下为插入活性表操作. */

BTRR?$?0

maxy = (y1 > y2)? y1: y2;电脑爱好者网 t'd6|{P'L
|*`

while (( entry >1) && (maxy > sides [entry -1]. y_top)) 电脑爱好者网9IO3M3K+x

                   {电脑爱好者网Q'kCs]{J

                        sides[entry]=sides [entry ?];电脑爱好者网{K k3]v({!H'_"U

                        entry - -;电脑爱好者网r/vi(]8e-H

                   }电脑爱好者网(^*Pf*AP
lF.m

sides[entry]. y_top=maxy;电脑爱好者网
F7Q ^c_/f

sides[entry]. delta_y =abs(y2-y1)+1;电脑爱好者网 G"|%h
M*p!{q.Q m0kX$U

if (y1>y2)

mEl7K"H1I0

                sides[entry]. x_int =x1;电脑爱好者网,N"S C$R"S!M"z4@;o

else{电脑爱好者网Z)PK+_-Q^ b+k

                sides[entry].x_int=x2_temp;电脑爱好者网d O/l2U,Q2x1^#L

                sides[entry]. x_change_per_scan=x_change_temp;电脑爱好者网n a#}1qNr,^

   }电脑爱好者网lv4f(oQ,D

void sort_on_bigger_y(n)电脑爱好者网;AlQ"d)kD%K4x
o

int n;电脑爱好者网0rkXk]9r"g:h

{电脑爱好者网!O0k9i/p3P:L

int k, x1, y1;电脑爱好者网B/in,k8y'x7C

side_count=0;

%n-^ Kp&f2k9G2s
Zr0

y1=y[n];电脑爱好者网(}C'UkK{z'm}

x1=x[n];

(\r
\Gi0

bottomscan=y[n];电脑爱好者网,f$yWP7l

　电脑爱好者网5X!a9XV.uF

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

&dh&l)h z[
}L0

     {电脑爱好者网2G'g3NV8LJa4u1`

           if (y1 ! =y[k]) {

YA'~#X)|`@ D4k0

                               side_count ++;电脑爱好者网
y3C? f#jP

                            put_in_sides_list(side_count, x1, y1, x[k], y[k]);电脑爱好者网Zg0bWr
TFI"k"e`
N

                                }

!FaU(LV6d7B$K0

          else {

_3B5RO:W0

                             move ((short)x1, (short)y1);

2^;\:^h#n0

                             line((short)x[k], (short)y1, status);

7Eu!R%ybHly4c0

                  }

p2B#rVjlg:x0

           if (y[k] <bottomscan) bottomscan=y[k];

M e&z{uy8F0

           y1=y[k]; x1=x[k];电脑爱好者网-c6UdZ1?n)y1O_2U

      }电脑爱好者网Pb#H*Fs

}电脑爱好者网4k`J E.?+ew:Us

void update_first_and_last(count, scan)电脑爱好者网4Y e%c;RH5c7e

int count, scan;

Po yrf0

{

Sn5zoZzZQ0

while((sides[last_s+1]. y_top>=scan) && (last_s <count)) last_s ++;电脑爱好者网%p}!E'E9[(|Q

while(sides[first_s]. delta_y = = 0) first_s ++;

-mQ [V3`;{k0

}

F/@x-vu\y'U0

　

'm e:r#A1E S2T gp-D0

void swap(x, y)

G S.fq3T
e Q0

EACH_ENTRY x, y;

,~xGi6V3hD'El0

{电脑爱好者网[M-]nr

int i_temp;电脑爱好者网C\[Zu6DB

float f_temp;电脑爱好者网 c*boV@6}

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

~O(W'L:v5}F4Kd0

f_temp=x.x_int; x.x_int=y.x_int; y.x_int=f_temp;

I'S?N\V1j8{ Q0

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

NM:Ct(H!jLh7ak0

f_temp=x.x_change_per_scan; x. x_change_per_scan=y. x_change_per_scan; y.x.

w:T3Q2u+fM%S+Jgj0

change_per_scan=f_temp;

jML$HwqU0

}电脑爱好者网~i5R#|
V,n

　

Ti;X2m#xJ Vg0

void sort_on_x(entry, first_s)

8jA8f:q H1{0

int entry, first_s;

^[}j)O'Z)_0

{电脑爱好者网4_V(f2M%D)o#d%t$N

while((entry > first_s) && (sides[entry]. x_int < sides[entry-1]. x_int))

PUv1F2\0

         {电脑爱好者网?Y_T\,Y

               swap (sides[entry], sides[entry-1]);

aj [lFNu
e0

               entry - -;

%xr1z2gu0

}电脑爱好者网x hWc^ Oa

}

"?tO/j5v0IF8U0

void process_x_intersections(scan, first_s, last_s)

/y(~AAGONh7D|0

int scan, first_s, last_s;电脑爱好者网8As6[1M8D\Pg

{

u%f!Rw }3e0

int k;电脑爱好者网4S7ANy\7C$@[8x

x_int_cout=0;

!A,CqQ9\k2~{0

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

9DE0p p+G0

{

2^Lo.g?%FW0

if(sides[k]. delta_y >0) {电脑爱好者网 i3K|&@1Y

                      x_int_count ++;

:`1`h,Y1?ST7sy0

                      sort_on_x(k, first_s);

yL3q/b+wx0

}电脑爱好者网_~ IeY0P.m6Yh?

}电脑爱好者网p*pa#od`%Vu

}电脑爱好者网+A$d7E,g Yx,X {

　

P1E \~QJ5|v0

void draw_lines(scan, x_int_count, index)电脑爱好者网2o/feI4VtH&R)_9j

int scan, x_int_count, index;

HN5P!z R;_x&`8j0

{

b(Gx9mV0

int k, x, x1, x2;电脑爱好者网$d@.Kho8M mf(v%Y

for (k=1; k< (int) (x_int_count/2+1.5); k++)

2k5F!?'C.anw*O&SO0

{电脑爱好者网J5zo\frY[]u
dy

            while(sides[index]. delta_y = = 0) index ++;电脑爱好者网a9r9u
T/|g.s6VS,e7Ph

            x1=(int)(sides[index]. x_int +0.5);

t&Y_v&h/K*{~e~0

            index ++;电脑爱好者网z ]0Zf4t4_o

            while(sides[index].delta_y = = 0) index ++;电脑爱好者网 NC*?-x
oc
H

            x2 = (int) (sides [index]. x_int +0.5);

B;GXd:M0

            move((short)x1, (short)scan);

1H
br/RVm$Iiy0

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

+o%N HHLF4f#k0

            index ++;电脑爱好者网5_z(qjTV*r*a

}电脑爱好者网@w:l'Jbq5K1o#z

}电脑爱好者网;|}sBjda

void update_sides_list( )电脑爱好者网}$tH3RR1s:@

{电脑爱好者网c V"Yh Q;Z

int k;电脑爱好者网6e$?7N'].S#w|BxP

for (k=first_s; k<last_s +1; k++)电脑爱好者网u7~&~$\+v!`5w @4w7Mt

   {

x&W*g/]NI0

         if(sides[k].delta_y >0)

a:z*k.at
}]i0

                   {电脑爱好者网cnV$CbO(}
{e*v

                         sides[k].delta_y - -;

l'M`J]:B}H%[o0

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

2S e{9t;F,k0

                   }电脑爱好者网3c!Ip J6@2B1|\}L

  }电脑爱好者网}7bS(i
|1}O

}电脑爱好者网,PTT?6[Z2RvN

　

$Q oQ;P#H&h0

                       程序2.3.1 扫描线填色程序电脑爱好者网 axediy

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

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

^{3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围。}电脑爱好者网{&K'b_,{J8A

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

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

^{6、swap子程序的主要功能是交换活性边表中两条相邻位置边的彼此位置。}

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

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

    ^{x_int=x_int_x_chang_per_scan；}电脑爱好者网F e5@ \^!j*|