基本图形生成算法

基本图形生成算法第一页，共六十四页，2022年，8月28日一光栅扫描：

1光栅扫描的基本原理：电子束在荧光屏上按照固定的扫描线和扫描顺序扫出一个由行和列组成的光的栅网。

2像素：栅网中的每一个孤立的光点，它是光栅显示的最小单位。像素可以有不同的亮度,像素的坐标值都是整数。

概论第二页，共六十四页，2022年，8月28日

3提出问题(1)目前使用的图形输出设备显示器：光栅图形显示器(2)光栅图形显示器:

以光栅扫描方式刷新线段、字符和图形。其本质:是一种画点设备，是由一定数量的网格状细小光点（像素）组成，使其某些像素亮，某些像素不亮来显示图形或文字.(3)问题：

光栅图形显示器是画点设备，而二维图形并不是点的集合，

如何在光栅图形显示器上构造基本二维几何图形(线圆)？(4)解决方法：

进行图形扫描转换

例：要在屏幕上显示一条直线时，只能确定出逼近直线的一组像素，并按扫描线顺序对这些像素进行写操作，即进行扫描转换。

结果:使所画的直线转换成为逼近理想直线的由无数个点构成的集合。

画图形：可使用同样的方法，即进行图形的扫描转换.

使所画的图形转换成为逼近理想图形的由无数个点构成的集合。第三页，共六十四页，2022年，8月28日扫描转换（光栅化）：

1什么叫扫描转换（光栅化）？在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。

2扫描转换的主要工作：由于理想的图形是连续的，而光栅图像是离散的，因此显示过程中不可避免地产生锯齿等畸变，扫描转换的主要工作就是研究使光栅图像逼近原始的图形的算法。用一系列的象素点来逼近直线第四页，共六十四页，2022年，8月28日

3学习扫描转换的目的：

(1)绘图函数具有局限性：

在实际工作中遇到画线的工作时，可以方便地调用程序设计语言中提供的绘图函数，不需要自己编写画线的程序。但它由局限性，不能满足用户特殊绘图要求，需要开发出满足需求的绘图程序。

(2)学习目的：掌握将数学的、模拟的、线形的图形变成数字的离散的图形的过程中的设计思想和方法，这些思想能够在科学研究和产品开发中发挥作用。第五页，共六十四页，2022年，8月28日5.1直线的生成三算法要求：

1准确：扫描点尽可能地逼近理想点。

2快速：改进算法尽快提高扫描转换速度。一问题的提出：

给定直线两端点P0(x0,y0)和P1(x1,y1)，在光栅显示器上画出该直线。二需要进行扫描转换：给出一个将直线转换为逼近理想直线的点的集合的算法。第六页，共六十四页，2022年，8月28日

2直线的斜截式方程：

y=kx+bb＝y1－kx1x从起点到终点每次增加1，用y=kx+b计算y值，再用putpixel(x,int(y+0.5),color)输出该像素。

3该算法的缺点：画线效率低，每步都需要一个浮点乘法运算和一个四舍五入运算，需要加以改进。

5.2.数值微分法(DDA算法

DigitalDifferentialAnalyzer)

1直线的微分方程：一数值微分法：是一种基于直线微分方程来生成直线的方法。

第七页，共六十四页，2022年，8月28日二数值微分法的改进算法（关键：找到Pi(Xi,Yi),Pi+1(Xi+1,Yi+1)的关系）

1推导：直线方程：y=kx+b

直线上的第i、第i+1……个点为：Pi(Xi,Yi),Pi+1(Xi+1,Yi+1),…

计算Pi+1时：x为xi+1,（在第1象限x总是向右前进一步），

y为y （画水平线时，y的值不变）

yi+1 （画非水平线时，y的值变化，需要计算）其中：yi+1的计算为：

yi+1=kxi+1+B =k(xi+△x)+B=kxi+k△x+B =kxi+B+k△x //yi=kxi+B =yi+k△x =yi+k //当△x的步进为1时故Pi+1点的坐标为：

xi+1=xi+1yi+1=round(yi+k) //进行取整运算第八页，共六十四页，2022年，8月28日分析：下一点的y坐标为当前点y坐标加上斜率k,省略了浮点乘法。Pi+1点的坐标为：

xi+1=xi+1yi+1=round(yi+k)

(xi,yi)

(xi+1,(int)(yi+k))

(xi,(int)(yi))

(xi+1,yi+k)数值微分法示意图理想直线上的坐标点扫描转换后的像素点第九页，共六十四页，2022年，8月28日

2算法：

1)计算斜率k=△y/△x

2)画第1个点(x0,y0)

3)计算下一个点（x，y）的值P，

x=x+1,y=y+k 小数部分≥0.5,则y=y+1循环 小数部分<0.5,则y=y

画点（x，y）第十页，共六十四页，2022年，8月28日voidddaline(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx;floatdx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx; //计算斜率

y=y0; //设定第1点的y值

for(x=x0;x<=x1;x++) //x加1{putpixel(x,(int)(y+0.5),color); //画点，y值取整

y=y+k; //计算y的值

}}

3程序：

4分析：

本算法中k值需要使用浮点，每一步都要进行取整运算，不利于硬件实现。可以用中点画线法解决。第十一页，共六十四页，2022年，8月28日

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

中点画线法示意图3.2.2中点画线法：1有直线F(x,y)=ax+by+c=0，假定其斜率在0，1之间.2直线在x方向增加一个单位，则在y方向上的增量只能在0与1之间。3当前点为P（xp，yp）,下一点有两种选择:P1（xp+1,yp）或P2（xp+1,yp+1).4Q点是直线与垂直线x=xp+1的交点。M（xp+1，yp+0.5）为P1与P2的中点。若直线上的点Q在M的下方，说明直线离P1近，则应取P1为下一点。若直线上的点Q在M的上方，说明直线离P2近，则应取P2为下一点，

问题：如何判断Q在M的什么位置?

一原理:第十二页，共六十四页，2022年，8月28日二判别式推导：

1直线方程： F(x,y)=ax+by+c=0

直线上的点： F(x,y)=0

直线上方的点： F(x,y)>0

直线下方的点： F(x,y)<0

中点M的坐标为：xp+1 yp+0.5

2欲判断Q点在M的上方还是下方，将M带入F(x,y)，判断它的符号即可。判别式：dk=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c

dk>0

Q在M的下方（M在直线的上方）则：取P1作为下一个象素，

dk=dk

=0

Q在M的上（M在直线的上）则：同上

dk

<0Q在M的上方（M在直线的下方）则：取P2作为下一个象素，

对每一个象素计算判别式d，根据它的符号判定下一个象素。d是xp，yp的线形函数，可以采用增量计算来提高运算效率。

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十三页，共六十四页，2022年，8月28日根据不同情况分析如下：第一种情况：当dk≥0时，取正右方的象素p1，下一步则应在p3和p4当中选择，设它们的中点为M1（xp+2，yp+0.5）,则判断式d1为：

dk+1=F(M1)=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=axp+2a+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=dk+a下一步的判别式为：dk+1=dk+1+ad的增量为a。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十四页，共六十四页，2022年，8月28日第二种情况：当d<0时，取正上方的象素p2，下一步则应在p4和p5当中选择，设它们的中点为M2（xp+2，yp+1.5）,则判断式d2为：

dk+1=F(M2)=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=axp+2a+b(yp+1.5)+c=a(xp+1)+a+b(yp+0.5)+c+b=dk+a+b

下一步的判别式为：dk+1

=dk+a+bd的增量为a+b。

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十五页，共六十四页，2022年，8月28日初始值，第一个象素为起点（x0，y0），相应的判别式值为M0，由于起点（x0，y0）在直线上，故F（x0，y0）=0。推导：d0=F(M0)=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+by0+c+a+0.5b=F(x0，y0)+a+0.5b//∵起点必在直线上，∴F(x0，y0)=0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十六页，共六十四页，2022年，8月28日小结：1）根据M选择P1与P2之一：dk=a(xp+1)+b(yp+0.5)+c2）根据M1选择P3与P4之一：dk+1=dk+a3）根据M2选择P4与P5之一：dk+1=dk+a+b4)d的初始值为：d0=a+0.5b

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

三进一步改进算法：

注意到初始值中有浮点运算，消除浮点可以进一步改进算法。考察判别式dk，判别使用的仅仅是dk的符号，且dk的增量都是整数，

故用2dk来代替dk，摆脱小数（浮点），从而提高速度。

第十七页，共六十四页，2022年，8月28日改进结果：(中点画线法的精髓）

d0=2a+b(a=y0-y1,b=x1-x0)dk+1=dk+2a（dk》0）此时取正右方像素

dk+2a+2b（dk<0）此时取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

学习目标：1理解该算法的来龙去脉（上述结果是怎么得来的）。2能够用上述结果解题，编程实现该算法。第十八页，共六十四页，2022年，8月28日四总结中点画线算法：

1基本思想：通过判断dk的值来确定下一个该点亮的像素

2思路：

(1)先求d0的值(利用中点M求）：d0=2a+b(2)再找到dk+1与dk的关系：

dk+1=dk+2a（dk》0）此时取正右方像素

dk+2a+2b（dk<0）此时取右上方像素

ax+by+c=0

Q

P1

P2

M

P3

P4

P5

M1

M2

P

第十九页，共六十四页，2022年，8月28日五利用推导结果编程实现中点画线算法：voidMidpointLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{inta,b,delta1,delta2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b; //d为d0，d=a+0.5b，2d=2a+b，D=2a+b,D=a+a+b delta1=2*a; //delta1为d1delta2=2*(a+b); //delta2为d2x=x0;y=y0;putpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=delta2;

}else{x++;d+=delta1;}putpixel(x,y,color);} //while} //MidpointLine

第二十页，共六十四页，2022年，8月28日课后作业题：用中点画线算法扫描转换从像素点(1,1)到(8,5)线段的像素位置第二十一页，共六十四页，2022年，8月28日3改进的Bresenham算法假定直线段的0≤k≤1基本原理：第二十二页，共六十四页，2022年，8月28日误差项的计算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1第二十三页，共六十四页，2022年，8月28日算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、d=0、x=x0、y=y0。3.绘制点(x,y)。4.d更新为d+k，判断d的符号。若d>0.5，则(x,y)更新为(x+1,y+1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。第二十四页，共六十四页，2022年，8月28日改进1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1第二十五页，共六十四页，2022年，8月28日算法步骤为：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。第二十六页，共六十四页，2022年，8月28日改进2：用2e△x来替换ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△x第二十七页，共六十四页，2022年，8月28日1/27/202327算法步骤：1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。2.计算初始值△x、△y、e=-△x、x=x0、y=y0。3.绘制点(x,y)。4.e更新为e+2△y，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y)。5.当直线没有画完时，重复步骤3和4。否则结束。第二十八页，共六十四页，2022年，8月28日三利用推导结果编程实现bresenham算法：voidbresenhamline(intx0,inty0,intx1,inty1){intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;

while(x<=x1){ putpixel(x,y); x=x+1;

e=e+2*dy;

if(e>0){y=y+1;e=e-2*dx;}}}第二十九页，共六十四页，2022年，8月28日五中点画线算法与bresenham算法的比较：

相似处：1求出d0的值2再找到dk+1与dk的关系.3利用dk的值判断下一个该点亮的像素：不同点：1求d0时：中点画线法：利用中点M坐标来求，d0＝2a＋bbresenham法：利用始点终点来求，d0＝2△y-△x2利用dk的值取像素时：

bresenham法：dk》0时取右上方像素

dk<0时取右方像素中点法正相反：dk》0时取右方像素

dk<0时取右上方像素第三十页，共六十四页，2022年，8月28日课后作业题：用bresenham算法扫描转换从像素点(1,1)到(8,5)线段的像素位置。第三十一页，共六十四页，2022年，8月28日3.3圆的生成3.3.1八分法画圆算法思路：（考虑到圆的对称性）画出A点则剩下的7个点都能画出，画出B点则剩下的7个点都能画出，因此，只讨论8分圆的画法即可A(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)B第三十二页，共六十四页，2022年，8月28日二算法原理：利用其函数方程，直接离散计算圆的函数方程为：缺点：计算量过大第三十三页，共六十四页，2022年，8月28日三圆的极坐标方程为：第三十四页，共六十四页，2022年，8月28日可先通过平移变换，把计算所得的像素(x1,y1)坐标加上一个位移量(delta_x和delta_y)即得所求像素坐标(x2,y2)。即：

x2=x1+delta_xy2=y1+delta_y四中点不在原点的圆：第三十五页，共六十四页，2022年，8月28日3.3.2中点画圆算法（关键：找到d的增量）一基本思路：利用中点M来选择下一个要显示的像素。二分析：

M的坐标是（x+1,y-0.5）

F(M)>0点M在圆的外边,圆离P2点近,取P2F(M)=0点M在圆的上边,取P2F(M)<0点M在圆的里边,圆离P1点近,取P1

问题：下一次取P3？P4？P5？

M1P1P2M2M3P3P4P5第三十六页，共六十四页，2022年，8月28日1

构造判别式：若d<0点M在圆的里边，圆离P1点近,则应取P1

下一个中点M2的判别式为：

d=F(xp+2,yp-0.5) =(xp+2)2+(yp-0.5)2-R2 =d+2xp+3

即求出d的增量为：2xp+3若d≥0点M在圆的外边,圆离P2点近,则应取P2

下一个中点M3的判别式为：

d=F(xp+2,yp-1.5) =(xp+2)2+(yp-1.5)2-R2 =d+2(xp-yp)+5

即求出d的增量为：2(xp-yp)+5总结求得的d的增量：2xp+3d<02(xp-yp)+5d≥0

2求d的增量：（目的：判断下一个该显示的像素）解决方法：M1P1P2M2M3P3P4P5p第三十七页，共六十四页，2022年，8月28日3求d的初始值d0：

起始点（即第一个像素)为（0,R）,

判别式d的初始值为：

d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R4推导出的结果:d0＝1.25-R

d+2xp+3d<0d+2(xp-yp)+5d≥0

M1P1P2M2M3P3P4P5d=

5可以利用推导出的结果，编写程序。第三十八页，共六十四页，2022年，8月28日三算法步骤：1.输入圆的半径R。2.计算初始值d=1.25-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x<y时，重复步骤3和4。否则结束。第三十九页，共六十四页，2022年，8月28日改进：用d-0.25代替d算法步骤：1.输入圆的半径R。2.计算初始值d=1-R、x=0、y=R。3.绘制点(x,y)及其在八分圆中的另外七个对称点。4.判断d的符号。若d≤0，则先将d更新为d+2x+3，再将(x,y)更新为(x+1,y)；否则先将d更新为d+2(x-y)+5，再将(x,y)更新为(x+1,y-1)。5.当x<y时，重复步骤3和4。否则结束。第四十页，共六十四页，2022年，8月28日四源程序：voidMidpointCircle(r,color)intr,color;{intx,y,d;x=0;y=r;d=1-r;wholecircle(x,y,color);

while(x<y){if(d<0) {d+=2*x+3;x++;}else {d+=2*(x-y)+5; x++;y--;}wholecircle(x,y,color);}}voidWholeCircle(xc,yc,x,y.color)intxc,yc,x,y,color;{putpixel(xc+x,yc+y,color);putpixel(xc-x,yc+y,color);putpixel(xc+x,yc-y,color);putpixel(xc-x,yc-y,color);putpixel(xc+y,yc+x,color);putpixel(xc-y,yc+x,color);putpixel(xc+y,yc-x,color);putpixel(xc-y,yc-x,color);}第四十一页，共六十四页，2022年，8月28日3.4区域填充:

区域填充研究如何用一种颜色或一个图案来充满一个二维区域。

一区域：一组具有相同的属性相邻又相连的象素。二区域填充：根据边或顶点的简单描述生成区域的过程叫作区域填充。三区域填充要做的两个工作：

1在什么地方填充，2填充什么内容。四区域填充算法分为两大类：

1.扫描转换填充算法：按扫描线的顺序确定。

2.种子填充算法：假设在多边形或区域的内部，至少有一个象素是已知的，然后设法找到区域内所有其它象素，并对它们进行填充。

第四十二页，共六十四页，2022年，8月28日3.4.1种子填充算法一种子填充算法的原理：假设在多边形区域内部有一像素已知，由此出发找到区域内的所有像素。假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有象素均不取这一特定值，而边界外的像素则可具有与边界相同的值。第四十三页，共六十四页，2022年，8月28日

从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。图(a)所示的区域是四连通区域。

特点：区域内像素由四向连接，而区域的边界却是八连通式的。二几个概念：区域分两种：四向连通区域和八向连通区域1四向连通区域：第四十四页，共六十四页，2022年，8月28日区域内每—个象素，可以通过左、右、上、下、左上、右上、左下、右下这八个方向的移动的组合来到达区域内的任意象素。图(b)所示的区域是八连通区域。

特点：区域内象素由八向连接。如两个矩形的连接处为右上连接。但是区域的边界是四连通式的。

八向连通区域：第四十五页，共六十四页，2022年，8月28日允许从四个方向寻找下一象素，称为四向算法；允许从八个方向寻找下一象素，称为八向算法。八向算法可以填充八向连通区域，也可以填充四向连通区域。四向算法只能填充四向连通区域，而不能填充八向填充区域。如果图(b)中的区域是两个分离的区域，并且每个区域需填成不同的颜色，那么，用八向算法会使两个区域被错误地填上同一颜色。3四向算法和八向算法：第四十六页，共六十四页，2022年，8月28日1问题点：采用什么数据结构？

(1)联想迷宫求解问题：

相似处：迷宫图中的每一个方块象一个像素，所有的通道块象要填充的区域。不同处：求解迷宫路径：不是所有的通道块都被选中区域填充：与种子像素特性相同的不超过边界的所有像素都被选中。本质：属于后进先出问题。

(2)四向算法采用的数据结构：栈结构

四向算法：第四十七页，共六十四页，2022年，8月28日2四向算法原理：种子像素入栈；当栈非空时重复执行如下三步操作：

(1)栈顶像素出栈

(2)将出栈像素置成多边形色

(3)按右上左下方向逆时针旋转，顺序检查与出栈像素相邻的四个像素，若其中某个像素不在边界而且未置成多边形色则把该像素入栈。第四十八页，共六十四页，2022年，8月28日有一个用边界表示的区域，用种子填充算法对该区域进行填充。

3

8

24

7

9

24

7

9

1

4

3

84

7

9

5

6

4

84

7

9

5

6

84

7

9

7

6

84

7

9

7

84

7

9

8

4

7

9

4

7

9

7

9

9

堆栈中的数据：红色代表出栈数据，灰色代表栈顶

1号出栈填充,按右上左下顺序寻找未填充象素。

2号出栈填充,按右上左下顺序找到8，3。

3号出栈填充,按右上左下顺序找到4。

4号出栈填充,按右上左下顺序找到6，5。

5号出栈填充,6为栈顶。

6号出栈填充,按右上左下顺序找到7。

7号出栈填充,8为栈顶。

8号出栈填充,4为栈顶.4号出栈填充,7为栈顶(4号重复填充)7号出栈填充,9为栈顶(7号重复填充)

9号出栈填充,栈空，结束。第四十九页，共六十四页，2022年，8月28日

3四向算法的缺点：

1把太多的象素压入堆栈，有些象素甚至会入栈多次，降低了算法的效率，

2要求很大的存储空间以实现栈结构.4解决办法：在任意一个扫描线与多边形的相交区间中，只取一个种子象素。通过沿扫描线填充水平象素段，来代替处理4-邻接点和8-邻接点。第五十页，共六十四页，2022年，8月28日3.4.2扫描线填充算法算法原理：种子象素入栈；当栈非空时作如下四步操作：

1栈顶象素出栈；

2沿扫描线对出栈象素的左右象素进行填充，直至遇到边界象素为止，即每出栈一个象素，就对包含该象素的整个区间进行填充；

3上述区间内最左、最右的象素分别记为xl，xr（x_left,x_right）;4在区间[xl，xr]中检查与当前扫描线相邻的上下两条扫描线的有关象素是否全为边界象素或已填充的象素，若存在非边界、末填充的象素，则把每一区间的最右象素取作种子象素入栈。第五十一页，共六十四页，2022年，8月28日二扫描线填充算法举例：

要求：用红色象素●填充，以◆为边界的艺术A字。1．种子位置为●，填充一行（红），检查上下两行中未填充区域，将最右的一个象素压入堆栈中，堆栈中为1，2，3，栈顶为3，故下一步填充3号行。

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆

3◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆第五十二页，共六十四页，2022年，8月28日2．填充一行（绿），检查上下两行中未填充区域，将最右的一个象素压入堆栈中，堆栈中为1，2，3，4，下一步处理4号的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆

4◆◆◆◆

3◆◆

◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆

第五十三页，共六十四页，2022年，8月28日3填充一行（绿），堆栈为1，2，3，新4，下一步处理新4号的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆

4◆

◆

◆◆

◆

◆

◆◆◆◆◆

◆◆◆◆第五十四页，共六十四页，2022年，8月28日4．填充了两行（兰色），堆栈为1，2，3，下一步处理3号的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆

3◆◆●●◆

◆

◆◆●●◆

◆

◆◆◆◆◆

◆◆◆◆第五十五页，共六十四页，2022年，8月28日5．填充了三行（绿色），堆栈为1，2，下一步处理2号的行

◆◆◆◆◆◆

◆

◆

◆

◆◆

◆◆◆◆

◆◆

◆

◆

◆◆

2◆◆◆◆

1◆◆●●●●●●●●◆◆●●●●●●●●◆◆●●◆◆◆◆●●◆◆●●◆

◆●●◆◆●●◆

◆●●◆◆◆◆◆

◆◆◆◆

第五十六页，共六十四页，2022年，8月28日6．填充了三行（绿色），堆栈为1，2，下一步处理2号的行

◆◆◆◆◆◆

◆

◆

◆

2◆◆●●◆◆◆◆

◆