凸壳算法2.doc

离散点集多层凸壳嵌套的建立算法 2任务：1。逐步生成多层凸壳嵌套 2实时记录当前凸壳点的地址下标于一个地址串，用坐标冲零法消去外层凸壳坐标点。在形成内层点集时，要滤掉零坐标点。 算法：1。极值点肯定是凸点。2从一个极值点（XMIN,YA）出发，求出与该点相关的两个最大夹角点： YA 之上的一点为凸壳终止条件点 PEND； YA 之下的一点为当前凸壳的第2点，借此形成第一个凸壳边；3从第一边开始，反时针方向求其最大夹角点为下一个凸壳点，直到下一个凸壳点为点PEND时为止。一、生成离散点数据集：N，xi,yi二、将离散点集读入数组 N， X( ),Y( ) XD,YMAX三、 设置当前凸壳多边形顶点的原数组序号于 IRECT( )四、由外向内逐层生成凸壳： D45DO 3000 IIII=1,200 XMIN,YA A 若总点数N为0，则结束。 C XMAX,YC若总点数N为1，则绘一点符，结束。 若总点数N为2，则绘一直线，结束。 B若总点数N为3，则绘一三角形，结束。 XB,YMIN（1）求四个方向的坐标极值：XMIN,YA; XB, YMIN; XMAX,YC; XD, YMAX 并记下最左点的点号于 IA（2）过A点作纵坐标轴矢量 （XMIN,YA）,(XMIN,YMAX)（3）求与纵轴矢量的最小夹角矢量点PEND 最小夹角初值：ALFMIN99 初始辅助矢量（按反时针方向）：P P1X1=XMIN Y1=YMAXX2=XMIN P Y2=YA PENDax=(X1-X2)ay=(Y1-Y2) XMIN，YA P1（4） 通过扫描判别以确定 PENDDO 100 I=1,N X3=X(I) P2 Y3=Y(I) IF(X3.EQ.XMN.AND.Y3.EQ.YA) GOTO 100 BX=(X3-X2) BY=(Y3-Y2) A1=AX*BX+AY*BY S1=SQRT(AX*2+AY*2) S2=SQRT(BX*2+BY*2) ARCCOS=A1/S1/S2 AA=AMIN1(1.,ARCCOS) ALF=ACOS(AA) IF(ALF.LT.ALFMIN) THEN ALFMIN=ALF A=X(I) B=Y(I) III=I ENDIF100 CONTINUE 最小夹角点PEND 的坐标: XEND=A YEND=B（5） 最大夹角矢量点P2 点的确定，形成初始矢量 P1 P2：X1=XMNY1=YMXX2=X1Y2=YAXX(1)=X2YY(1)=Y2IRECT(1)=IAK=1IA 为最左点的点号； K 为凸壳点计数器通过扫描判断，确定与初始矢量构成最大夹角的下一个矢量端点DO 2000 II=1,1000最大夹角初值：ALFMAX=-4.AX=(X1-X2)AY=(Y1-Y2)DO 1000 I=1,N排除全部已确定的凸壳点DO 200 J=1,KIF(X(I).EQ.XX(J).AND.Y(I).EQ.YY(J) GOTO 1000200CONTINUEX3=X(I)Y3=Y(I)BX=(X3-X2)BY=(Y3-Y2)A1=AX*BX+AY*BYS1=SQRT(AX*2+AY*2)S2=SQRT(BX*2+BY*2)ARCCOS=A1/S1/S2AA=AMIN1(1.,ARCCOS)ALF=ACOS(AA)IF(ALF.GT.ALFMAX) THEN ALFMAX=ALF A=X(I) B=Y(I) III=IENDIF1000CONTINUE 新增凸壳点及其点号 III ： K=K+1 IRECT(K)=III XX(K)=A YY(K)=B 新增凸壳点是否到达终止条件点 PEND（Xend,Yend） 若是： IF(A.EQ.XEND.AND.B.EQ.YEND) THEN K=K+1 XX(K)=XX(1) YY(K)=YY(1) GOTO 2100ENDIF 若否：变当前矢量为初始矢量： X1=X2 Y1=Y2 X2=A Y2=B AX=(X1-X2) AY=(Y1-Y2)2000CONTINUE2100 绘制当前凸壳多边形根据所记录的当前凸壳点在原数组的下标串，对相应的坐标点冲零：DO 2500 I=1,K-1IREC=IRECT(I)X(IREC)=0.Y(IREC)=0.2500CONTINUE形成内部新的非零离散点集 N,X（），Y（）：K=0DO 2600 I