扫描线填充算法讲解(共23页)78

《扫描线填充算法讲解(共23页)78》由会员分享，可在线阅读，更多相关《扫描线填充算法讲解(共23页)78（24页珍藏版）》请在装配图网上搜索。

1、扫描线算法(sun f)（Scan-Line Filling）扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何(j h)位置，不需要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维 CAD 软件的渲染(xunrn)等等。对矢量多边形区域填充，算法核心还是(hi shi)求交。计算几何与图形学有关的几种常用算法一文给出了判断点与多边形关系的算法扫描交点的奇偶数判断算法，利用此算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的填充算法都是只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法效率问题之外，还存在一个光栅图形设备和矢

2、量之间的转换问题。比如某个点位于非常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。2.1 扫描线算法的基本思想 扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些交点按照 x 坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归纳为以下 4

3、 个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第 2 步得到的交点按照 x 值从小到大进行排序；（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第 1 步继续处理；整个算法(sun f)的关键是第 1 步，需要用尽量少的计算(j sun)量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算(j sun)，则计算量大，而且效率底下，如图（6）所示：图（6）多边形与扫描线示

4、意图 观察多边形与扫描线的交点情况，可以得到(d do)以下两个特点：（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线的斜率有关；第一个特点(tdin)是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动(hu dng)边”组成(z chn)的表，称为“活动(hu dng)边表（AET）”。例如扫描线 4 的“活动边表”由 P1P2 和 P3P4 两条边组成，而扫描线 7 的“活动边表”由 P1P2、P6P1、P5P6 和 P4P5 四条边组成。第二个特点可以进一步证明，假设当前扫描线与

5、多边形的某一条边的交点已经通过直线段求交算法计算出来，得到交点的坐标为（x,y），则下一条扫描线与这条边的交点不需要再求交计算，通过步进关系可以直接得到新交点坐标为（x+x,y+1）。前面提到过，步进关系x 是个常量，与直线的斜率有关，下面就来推导这个x。假设多边形某条边所在的直线方程是：ax+by+c=0，扫描线 yi和下一条扫描线 yi+1与该边的两个交点分别是（xi，yi）和（xi+1，yi+1），则可得到以下两个等式：axi+byi+c=0(等式 1)axi+1+byi+1+c=0(等式 2)由等式 1 可以得到等式 3：xi=-(byi+c)/a(等式 3)同样，由等式 2 可以得到

6、等式 4：xi+1=-(byi+1+c)/a(等式 4)由等式 4 等式 3 可得到 xi+1 xi=-b(yi+1-yi)/a 由于扫描线存在 yi+1=yi+1 的关系，将代入上式即可得到：xi+1 xi=-b/a 即x=-b/a，是个常量（直线斜率的倒数）。“活动(hu dng)边表”是扫描线填充算法的核心，整个算法都是围绕(wiro)者这张表进行处理的。要完整的定义“活动(hu dng)边表”，需要先定义边的数据结构(sh j ji u)。每条边都和扫描线有个交点，扫描线填充算法只关注交点的 x 坐标。每当处理下一条扫描线时，根据x 直接计算出新扫描线与边的交点 x 坐标，可以避免复杂

7、的求交计算。一条边不会一直待在“活动边表”中，当扫描线与之没有交点时，要将其从“活动边表”中删除，判断是否有交点的依据就是看扫描线 y 是否大于这条边两个端点的 y 坐标值，为此，需要记录边的 y 坐标的最大值。根据以上分析，边的数据结构可以定义如下：65 typedef struct tagEDGE 66 67 double xi;68 double dx;69 int ymax;74 EDGE;根据 EDGE 的定义，扫描线 4 和扫描线 7 的“活动边表”就分别如图（7）和图(8)所示：图（7）扫描线 4 的活动边表 图（8）扫描线 7 的活动边表 前面提到过，扫描线算法的核心就是围绕“

8、活动边表（AET）”展开的，为了方便活性边表的建立与更新，我们为每一条扫描线建立一个“新边表（NET）”，存放该扫描线第一次出现的边。当算法处理到某条扫描线时，就将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。“新边表”通常在算法开始时建立，建立“新边表”的规则就是：如果某条边的较低端点（y 坐标较小的那个点）的 y 坐标与扫描线 y 相等，则该边就是扫描线 y 的新边，应该加入扫描线 y 的“新边表”。上例中各扫描线的“新边表”如下图所示：图（9）各扫描线的新边表 讨论(toln)完“活动(hu dng)边表（AET）”和“新边表（NET）”，就可以开始算法的具体实现了，但是在进

9、一步详细(xingx)介绍实现算法之前，还有以下几个关键的细节问题需要明确：（1）多边形顶点(dngdin)处理 在对多边形的边进行求交的过程中，在两条边相连的顶点处会出现一些特殊情况，因为此时两条边会和扫描线各求的一个交点，也就是说，在顶点位置会出现两个交点。当出现这种情况的时候，会对填充产生影响，因为填充的过程是成对选择交点的过程，错误的计算交点个数，会造成填充异常。假设多边形按照顶点P1、P2 和 P3 的顺序产生两条相邻的边，P2 就是所说的顶点。多边形的顶点一般有四种情况，如图（10）所展示的那样，分别被称为左顶点、右顶点、上顶点和下顶点：图（10）多边形顶点(dngdin)的四种类

10、型 左顶点(dngdin)P1、P2 和 P3 的 y 坐标(zubio)满足条件：y1 y2 y2 y3；上顶点P1、P2 和 P3 的 y 坐标满足条件：y2 y1&y2 y3；下顶点P1、P2 和 P3 的 y 坐标满足条件：y2 y1&y2 y3；对于左顶点和右顶点的情况，如果不做特殊处理会导致奇偶奇数错误，常采用的修正方法是修改以顶点为终点的那条边的区间，将顶点排除在区间之外，也就是删除这条边的终点，这样在计算交点时，就可以少计算一个交点，平衡和交点奇偶个数。结合前文定义的“边”数据结构：EDGE，只要将该边的 ymax 修改为 ymax 1 就可以了。对于上顶点和下顶点，一种处理方

11、法是将交点(jiodin)计算做 0 个，也就是修正两条边的区间，将交点从两条边中排除；另一种处理(chl)方法是不做特殊处理，就计算 2 个交点，这样也能保证(bozhng)交点奇偶个数平衡。（2）水平(shupng)边的处理 水平边与扫描线重合，会产生很多交点，通常的做法是将水平边直接画出（填充），然后在后面的处理中就忽略水平边，不对其进行求交计算。（3）如何避免填充越过边界线 边界像素的取舍问题也需要特别注意。多边形的边界与扫描线会产生两个交点，填充时如果对两个交点以及之间的区域都填充，容易造成填充范围扩大，影响最终光栅图形化显示的填充效果。为此，人们提出了“左闭右开”的原则，简单解释就

12、是，如果扫描线交点是1 和 9，则实际填充的区间是1,9），即不包括 x 坐标是 9 的那个点。2.2 扫描线算法实现 扫描线算法的整个过程都是围绕“活动边表（AET）”展开的，为了正确初始化“活动边表”，需要初始化每条扫描线的“新边表（NET）”，首先定义“新边表”的数据结构。定义“新边表”为一个数组，数组的每个元素存放对应扫描线的所有“新边”。因此定义“新边表”如下：510 std:vector std:list slNet(ymax-ymin+1);ymax和 ymin 是多边形所有顶点中 y 坐标的最大值和最小值，用于界定扫描线的范围。slNet 中的第一个元素对应的是 ymin 所在

13、的扫描线，以此类推，最后一个元素是 ymax 所在的扫描线。在开始对每条扫描线处理之前，需要先计算出多边形的 ymax 和 ymin 并初始化“新边表”：503 void ScanLinePolygonFill(const Polygon&py,int color)504 505 assert(py.IsValid();506 507 int ymin=0;508 int ymax=0;509 GetPolygonMinMax(py,ymin,ymax);510 std:vector std:list slNet(ymax-ymin+1);511 InitScanLineNewEdgeTabl

14、e(slNet,py,ymin,ymax);512/PrintNewEdgeTable(slNet);513 HorizonEdgeFill(py,color);/水平边直接画线填充 514 ProcessScanLineFill(slNet,ymin,ymax,color);515 InitScanLineNewEdgeTable()函数(hnsh)根据多边形的顶点和边的情况初始化“新边表”，实现过程中体现了对左顶点和右顶点的区间修正(xizhng)原则：315 void InitScanLineNewEdgeTable(std:vector std:list&slNet,316 const

15、 Polygon&py,int ymin,int ymax)317 318 EDGE e;319 for(int i=0;i ps.y)336 337 e.xi=ps.x;338 if(pee.y=pe.y)339 e.ymax=pe.y-1;340 else 341 e.ymax=pe.y;342 343 slNetps.y-ymin.push_front(e);344 345 else 346 347 e.xi=pe.x;348 if(pss.y=ps.y)349 e.ymax=ps.y-1;350 else 351 e.ymax=ps.y;352 slNetpe.y-ymin.push_

16、front(e);353 354 355 356 多边形的定义(dngy)Polygon 和本系列第一篇计算几何与图形学有关的几种(j zhn)常用算法一文中的定义一致，此处就不再重复说明。算法通过遍历所有的顶点获得边的信息，然后(rnhu)根据与此边有关的前后两个顶点的情况确定此边的 ymax 是否(sh fu)需要-1 修正。ps 和 pe 分别是当前处理边的起点和终点，pss 是起点的前一个相邻点，pee 是终点的后一个相邻点，pss 和 pee 用于辅助判断 ps 和 pe 两个点是否是左顶点或右顶点，然后根据判断结果对此边的 ymax 进行-1 修正，算法实现非常简单，注意与扫描线平

17、行的边是不处理的，因为水平边直接在 HorizonEdgeFill()函数中填充了。ProcessScanLineFill()函数开始对每条扫描线进行处理，对每条扫描线的处理有四个操作，如下代码所示，四个操作分别被封装到四个函数中：467 void ProcessScanLineFill(std:vector std:list&slNet,468 int ymin,int ymax,int color)469 470 std:list aet;471 472 for(int y=ymin;y=ymax;y+)473 474 InsertNetListToAet(slNety-ymin,aet)

18、;475 FillAetScanLine(aet,y,color);476/删除非活动边 477 RemoveNonActiveEdgeFromAet(aet,y);478/更新活动边表中每项的 xi 值，并根据 xi 重新排序 479 UpdateAndResortAet(aet);480 481 InsertNetListToAet()函数负责将扫描线对应的所有新边插入到 aet 中，插入操作到保证 aet 还是有序表，应用了插入排序的思想，实现简单，此处不多解释。FillAetScanLine()函数执行具体的填充动作，它将 aet 中的边交点成对取出组成填充区间，然后根据“左闭右开”的

19、原则对每个区间填充，实现也很简单，此处不多解释。RemoveNonActiveEdgeFromAet()函数负责将对下一条扫描线来说已经不是“活动边”的边从 aet 中删除，删除的条件就是当前扫描线y 与边的 ymax 相等，如果有多条边满足这个条件，则一并全部删除：439 bool IsEdgeOutOfActive(EDGE e,int y)440 441 return(e.ymax=y);442 443 444 void RemoveNonActiveEdgeFromAet(std:list&aet,int y)445 446 aet.remove_if(std:bind2nd(std:

20、ptr_fun(IsEdgeOutOfActive),y);447 UpdateAndResortAet()函数(hnsh)更新边表中每项的 xi 值，就是(jish)根据扫描线的连贯性用 dx 对其进行(jnxng)修正，并且根据 xi 从小到大的原则(yunz)对更新后的 aet 表重新排序：449 void UpdateAetEdgeInfo(EDGE&e)450 451 e.xi+=e.dx;452 453 454 bool EdgeXiComparator(EDGE&e1,EDGE&e2)455 456 return(e1.xi=e2.xi);457 458 459 void Upd

21、ateAndResortAet(std:list&aet)460 461/更新 xi 462 for_each(aet.begin(),aet.end(),UpdateAetEdgeInfo);463/根据 xi 从小到大重新排序 464 aet.sort(EdgeXiComparator);465 其实更新完 xi 后对 aet 表的重新排序是可以避免的，只要在维护aet 时，除了保证 xi 从小到大的排序外，在 xi 相同的情况下如果能保证修正量 dx 也是从小到大有序，就可以避免每次对 aet 进行重新排序。算法实现也很简单，只需要对 InsertNetListToAet()函数稍作修改

22、即可，有兴趣的朋友可以自行修改。至此，扫描线算法就介绍完了，算法的思想看似复杂，实际上并不难，从具体算法的实现就可以看出来，整个算法实现不足百行代码。第二种讲解 下面这个程序能对任意多边形填充，用鼠标画一个封闭多边形，画回到起始点说明画图完毕！然后点右键填充！我用的是扫描线算法，不过在对边界点的填充上有点问题，希望高手帮忙！#include#include#include#include#define FALSE 0#define TRUE 1#define NULL 0 union REGS regs;/*鼠标的变量*/int X_max,Y_max;/*鼠标活动范围最大值*/int x_O

23、rigin,y_Origin,x_Old,y_Old,x_New,y_New;/*鼠标点击的初始点,前一点和当前点的坐标*/int PointNum=0;/*判断鼠标是否是第一次按下*/int LineDrawFlag=FALSE;/*随鼠标画线标志*/int AddFlag=TRUE;/*边是否加入边表标志*/int y_Now;/*扫描线 y 的当前值*/int y_Start,y_Over;/*扫描线的起点与终点*/typedef struct Etable/*边表数据结构*/int Ymax;/*一条边中 Y 值较大点的 Y 值*/float x;/*一条边中 Y 值较小点的 X 值*

24、/int y;/*一条边中 Y 值较小点的 Y 值*/float dx;/*一条边的斜率的倒数*/struct Etable*next;/*指向下一条相临边的指针*/ETable;typedef struct AEtable/*活动边表数据结构*/int Ymax;float x;float dx;struct AEtable*next;AETable;/*交换结点数据时用的临时指针,这个指针我放在相应函数中定义编译时会有警告并*/AETable*temp;/*会在程序退出时报错,不清楚原因!*/void Initgr()/*初始化图形模式*/int gdriver=DETECT,gmode;

25、registerbgidriver(EGAVGA_driver);initgraph(&gdriver,&gmode,);X_max=getmaxx();Y_max=getmaxy();/*鼠标活动范围最大值*/ETable*AddtoEtable(int x_Old,int y_Old,int x_New,int y_New,ETable*head)/*将边加入边表*/ETable*p,*q1;p=head;while(p-next!=NULL)/*转到边表最后一个结点处*/p=p-next;q1=(ETable*)malloc(sizeof(ETable);/*临时建立一个结点来加入新边的

26、信息*/if(y_Newy_Old)/*如果当前点比前一点高,就把当前点的 Y 值赋予边的 Ymax*/q1-Ymax=y_New;q1-x=x_Old;q1-y=y_Old;else/*如果当然点比前一点低,就把前一点的 Y 值赋予边的 Ymax*/q1-Ymax=y_Old;q1-x=x_New;q1-y=y_New;q1-dx=(float)(x_New-x_Old)/(y_New-y_Old);if(head-Ymax Ymax)/*将边表中 Ymax 的最大值存入边表头结点,以确定扫描线的终点*/head-Ymax=q1-Ymax;if(head-y q1-y)/*将边表中 Y(它是

27、一条边中 X 值较小的点的 Y 值)的最大值存入边表头结点,*/head-y=q1-y;/*以确定扫描线的起点*/q1-next=p-next;p-next=q1;if(x_New=x_Origin&y_New=y_Origin)/*如果画回到初始点,说明多边形绘制完成,停止加入边表的工作*/AddFlag=FALSE;/*将加入边表的标志置为假*/return head;/*返回边表的头指针*/ETable*SortEtable(ETable*head)/*把边表中的奇异点消除*/(0)回复(huf)1 楼 2007-04-26 15:11 举报(j bo)|bravejun20 ETabl

28、e*p,*q;p=head-next;q=p-next;while(q!=NULL)/*如果一条边的 Ymax(y)与下一条边的 y(Ymax)相等(xingdng),Ymax 减一,以达到消除奇异点的目的*/if(p-y=q-Ymax)q-Ymax-;if(p-Ymax=q-y)p-Ymax-;if(q-next=NULL)if(q-y=head-next-Ymax)/*处理(chl)最后一条边与加入的第一条边的情况*/head-next-Ymax-;if(q-Ymax=head-next-y)q-Ymax-;p=p-next;q=q-next;p=head-next;q=p-next;re

29、turn head;/*返回(fnhu)边表头指针*/AETable*SortAEtable(AETable*head)/*对活动(hu dng)边表中的边按x 从小到大排序*/AETable*p,*q;p=head-next;q=p-next;while(q!=NULL)/*对活动边表中的边按 X 从小到大排序*/if(p-x q-x)temp-Ymax=q-Ymax;temp-x=q-x;temp-dx=q-dx;q-Ymax=p-Ymax;q-x=p-x;q-dx=p-dx;p-Ymax=temp-Ymax;p-x=temp-x;p-dx=temp-dx;temp=NULL;q=q-ne

30、xt;p=p-next;return head;/*返回活动边表的头指针*/void AET_Fill(AETable*head,int color)/*填充活动边表中的奇数边到偶数边间的像素*/AETable*p,*q;p=head-next;q=p-next;setcolor(color);while(q!=NULL)/*如果活动边表中有边要填充*/line(p-x,y_Now+1,q-x,y_Now+1);delay(1000);q=q-next;p=p-next;if(q!=NULL)/*如果活动边表仍不为空*/q=q-next;p=p-next;AETable*DeleteAETab

31、le(int Ymax,AETable*head)/*删除活动边表中 Ymax 大于扫描线 y 的边*/AETable*p,*q,*m;p=head;q=head-next;while(q!=NULL)if(q-Ymax=Ymax)/*删除活动边表中边的 Ymax 值与当前扫描线 Y 值相等的所有边*/p-next=q-next;free(q);q=head-next;p=head;else q=q-next;p=p-next;return head;void PolygonFill(ETable*head1,AETable*head2)/*填充多边形*/ETable*p1,*q1;AETab

32、le*p2,*q2;y_Over=head1-Ymax;/*从边表的头结点获取扫描线的起始值*/y_Start=head1-y;/*从边表的头结点获取扫描线的终结值*/head1=SortEtable(head1);/*对边表 按 Y 值从小到大排序*/for(y_Now=y_Start;y_Nownext;while(q1!=NULL)/*如果边表不为空*/回复(huf)2 楼 2007-04-26 15:11 举报(j bo)|bravejun20 if(y_Now=q1-y)/*如果(rgu)边表中有与扫描线 Y 值相等的 Y 值,则将这些边加入活动边表*/p2=head2;while(

33、p2-next!=NULL)p2=p2-next;q2=(AETable*)malloc(sizeof(AETable);q2-Ymax=q1-Ymax;q2-x=q1-x;q2-dx=q1-dx;q2-next=p2-next;p2-next=q2;p1-next=q1-next;free(q1);/*将 边表中 已经加入(jir)活动边表的边删除*/p1=head1;q1=p1-next;else q1=q1-next;p1=p1-next;head2=SortAEtable(head2);/*对活动(hu dng)边表中的边按 X 从小到大排序*/AET_Fill(head2,RED);

34、/*填充活动边表中从奇数(j sh)边到偶数边间的像素点*/head2=DeleteAETable(y_Now,head2);/*删除活动边表中已经填充完毕了的边*/p2=head2-next;while(p2!=NULL)p2-x=(float)(p2-x+p2-dx);/*将活动边表中的边的 X 值增加 dx,即:x=x+dx;*/p2=p2-next;int MouseInit(int Xp0,int Xp1,int Yp0,int Yp1)/*初始化鼠标*/*这里的参数是鼠标活动范围的左上角坐标和右下角坐标*/int retcode;regs.x.ax=0;int86(0 x33,s,

35、s);retcode=regs.x.ax;if(retcode=0)return 0;regs.x.ax=7;regs.x.cx=Xp0;regs.x.dx=Xp1;int86(0 x33,s,s);regs.x.ax=3;regs.x.cx=Yp0;regs.x.dx=Yp1;int86(0 x33,s,s);return retcode;int MouseState(int*m_x,int*m_y,int*mstate)/*获取鼠标状态和位置*/static int x0=10,y0=10,state=0;int xnew,ynew,ch;do if(kbhit()ch=getch();i

36、f(ch=13)*mstate=1;return-1;else return ch;regs.x.ax=3;int86(0 x33,s,s);xnew=regs.x.cx;ynew=regs.x.dx;*mstate=regs.x.bx;while(xnew=x0&ynew=y0&*mstate=state);state=*mstate;x0=xnew;y0=ynew;*m_x=xnew;*m_y=ynew;return-1;void DrawCursor(int x,int y)/*在鼠标当前位置画鼠标指针 和 跟随鼠标移动的直线*/int color;char str50;line(x-6

37、,y,x-2,y);line(x,y-6,x,y-3);line(x+2,y,x+6,y);line(x,y+3,x,y+6);if(LineDrawFlag=TRUE)line(x_New,y_New,x,y);color=getcolor();setcolor(getbkcolor();outtextxy(10,20,str);sprintf(str,(%d,%d),x,y);/*显示鼠标当前的坐标值*/setcolor(WHITE);outtextxy(10,20,str);setcolor(color);main()int X,Y,m_state,y,a,b,i,j;AETable*h

38、ead2;ETable*head1;head1=(ETable*)malloc(sizeof(ETable);/*开辟边表的一个头结点来保存扫描线的起始和终结值*/head1-Ymax=0;/*初始化 Ymax 为零,以便比较得到最大的 Ymax*/head1-y=10000;/*初始化 Y 为 10000,以便比较得到最小的 Y*/head1-next=NULL;head2=(AETable*)malloc(sizeof(AETable);/*开辟活动边表的一个头结点,以便加入符合条件的新边*/head2-next=NULL;回复(huf)3 楼 2007-04-26 15:11 举报(j

39、bo)|bravejun20 Initgr();/*BGI 初始化*/setcolor(WHITE);setwritemode(XOR_PUT);/*设定输入(shr)模式为异或模式*/MouseInit(0,X_max,0,Y_max);/*初始化鼠标*/a=X_max;b=Y_max;m_state=0;/*初始化鼠标状态为移动状态*/DrawCursor(a,b);while(m_state!=2)/*如果没有点击右键*/MouseState(&X,&Y,&m_state);/*获取鼠标当前状态与坐标值*/DrawCursor(a,b);/*通过异或输入模式删除之前的鼠标指针*/if(m

40、_state=1)/*如果鼠标左键点击*/LineDrawFlag=TRUE;/*将跟随鼠标画线标志置为真*/if(0=PointNum)/*如果是第一次点击左键*/x_Origin=a;y_Origin=b;x_Old=a;y_Old=b;x_New=a;y_New=b;else/*如果不是第一次点击鼠标左键*/x_Old=x_New;y_Old=y_New;x_New=a;y_New=b;PointNum+;/*记录鼠标左键点击次数,以便确定是否要跟随鼠标画线*/if(x_Origin-x_New)-10&(x_Origin-x_New)-10&(y_Origin-y_New)next（5）if(ch=13)*mstate=1（6）else return ch（7）