自动联结三角网构网法
一、形成最佳三角网的条件
用三角网法绘制等值线，是在三角形的三条边上用线性内插方法寻找等值点，这种方法的机理是将每个三角形看作是空间的一个平面，这就要求在每个三角形的三个顶点内的地貌形态无明显的变化，故此希望将其中最靠近的三个点构成三角形，以符合上述机理，使插补的等值点精度较高，更好的反映地貌的实际形态。符合这些条件的三角形称之为“最佳三角形”。
建立最佳三角形的条件，最常用的方法是，用邻近离散点组成三角形时，应尽可能使三角形均为锐角三角形，或使三角形的三条边长近似相等，这是较为理想的情况。但在实际中，往往是首先确定三角形的一条边（即两个顶点），在确定第三个顶点时，可使第三个顶点与已知两点所形成的夹角最大，从而使形成的三角形为“最佳三角形”。
二、使用的数据结构及控制变量说明（定义）
控制变量的说明
ｎ~离散点的个数
L~构网完成后形成的三角形个数
M~构网完成后形成的边数
K~计数器，记录目前正在用来扩展的三角形计数号
二、点、线、三角形的说明
点的定义：Type point = record x,y:real
线的定义：Type line =record P1,P2:point
三角形定义：Type ver = record I,J,R :int
由以上三个定义可以引出下面的说明：
点组： array[1...N] of point
线组： array[1...M] of line
三角形组：array[1...L] of ver
＊在本章中后续内容中，这些说明直接引用而不再解释其含义。
＊点组、线组、三角形组为动态组，以便节省内存。
三、构网的步骤（原理）
自动联结三角网方法构网的步骤如下：
（一）确定第一个三角形
从ｎ个离散点中任取一点作为P1，然后在其余的离散点中找出距P1最近的点P2，利用余弦公式计算剩余点与第一点、第二点的夹角的余弦值，将余弦值最小（即夹角最大）的那个点作为P3，至此第一个三角形已形成，并记录三个点号，计数器分别开始计数：即K＝L+１。
（二）三角形扩展
有了第一个三角形后，就可以从第K号三角形按照一定的规则往外扩展三角形，从而完成构网过程。其规则是：
1.第K号三角形开始扩展
由K号三角形的P1，P2构成有向直线＝。
2.搜索符合扩展条件的点
如图3-1，将P3点及除P1，P2，P3，点外的其它离散点Pj代入式(2-5)，当Pj与P3在的两侧时，则Pj为符合扩展条件的点。
3.扩展新三角形
用符合扩展条件的点Pj计算其与P1、P2点连线的夹角，找出夹角最大的点Pm ,和P1、P2组成新的三角形，同时计数器L加１。
4.判断新三角形是否成立
为了避免重复和交叉的情形，要对新三角形进行检查判断，其方法为：
对新三角形（计数为L）的三条边逐次与前面的L－１个三角形的各边进行比较，如果新三角形的某一条边与某两个相邻三角形的公用边重合，则认为新三角形无效，应使计数器L减１。
5.第K号继续扩展
由第K号三角形的第２条边，第３条边为基础，重复２－４步骤，则第K号三角形扩展工作完毕。
6.扩展结束
比较两计数器K和L之值。
若K〈L，则令计数器K加１，然后重复１－５全部步骤。
若K＝L，则扩展工作完成。
四、构网算法
算法１
输入 ｎ个离散点坐标P1 (x1,y1),P2 (x2,y2),...,Pn (xn,yn)并存入P：array(1...n) of point
输出 三角网的所有三角形顶点信息 v:array(1...L) of ver
第１步 形成第１个三角形
第1.1步 初始化计数器之值，使K1，L１
第1.2步 输入作为第１点的点号W1,并记录在第L号三角形信息结点中，VLIW
第1.3步 在余下的n-1个离散点中，求出距点Pw1最近的点（即第２点），其点号为E，并记录在第L号三角形信息结点中。VLJE
第1.4步 在余下的n-2个离散点中，求出与Pw1,PE连线夹间最大的点，其点号为F，将其记录在第L号三角形信息结点中。VLRF
第２步 扩展三角形
第2.1步 找出第K号三角形第一条扩展边的两端点及第三点： WVkI, EVkJ, FVkR, , KK1
第2.2步 由Pw,PE用式(2-3)生成有向直线。
第2.3步 搜索符合扩展的点进行扩展新三角形
⑴ 在ｎ个离散点中，利用式(2-6)，判别Pi (i=1,2,...n)和PF点在线的同侧还是在两侧；
若在同侧，则Pi不符合扩展条件；否则，计算Pi与Pw,PE连线夹角的余弦值，并保留其最小值及相应的点号DH。
⑵ 计数器L加1，登录新三角形的三个顶点到第L号三角形信息结点中。L←L+1, VLIW, VLJE, VLRDH
第2.4步 判断新三角形的有效性
⑴ F1←0,F2←0,F3←0; WVLI, EVLJ, FVLR
⑵ 逐次判断新三角的三条边p、、与第i(i=1,2,...L-1)号三角形的三条边是否重合；
若与有重合，则令F1F1+1；
若与有重合，则令F2F2+1；
若与有重合，则令F3F3+1
⑶ 如果(F1,F2,F3之中有一个值为2)，则新三角形无效，计数器减1。
第2.5步 找出第号三角形第二或第三条扩展边的两端点及第三点：
如果 KK=1 则 WVKJ, EVKR, FVKI,KKKK+1,转第2.2步；
如果KK=2则 WVKR, EVKI, FVKJ,KKKK+1,转第2.2步；
第2.6步 判断扩展是否结束。
如果 (KK=3,并且K=L)，则转向第３步；否则，计数器K加１；KK+1；转向第2.1步
第３步 输出三角网各三角形信息组Ｖ
五、代码（用C++版）
一、头文件
#include #include #include #include #include #include #include #include class gouwang{ private: int k,l,nn,ii,d[500],ver[501][4]; double x[500],y[500],h[500]; public: gouwang(); void print(); void minxy(); void mittxy(); void sjx1(); void kz(); int kz1(int n1,int n2,int n3); double kz11(int n1,int n2,int n3); int kz2(int n1,int n2,int n3,int mm); void kz3(int n1,int n2); int pd(int a,int b); void graph(); void cshq(double p[2],int maxxy[2],double maxx_minx[2],double maxy_miny[2]); void ht(); }; 二、联结三角形-构网 #include"gouwang.h" /*组成第一个三角形的函数*/ void gouwang::sjx1() {double r,r1,dx,dy,x0,y0; int n1,n2; l=1; ver[l][1]=ii; r1=10000; for(int i=1;i<=nn;i++) { if(i==ii) continue; dx=x[i]-x[ii]; dy=y[i]-y[ii]; r=sqrt(dx*dx+dy*dy); if(r ver[l][2]=i; } } n1=ver[l][1];n2=ver[l][2]; x0=(x[n2]-x[n1])/2+x[n1]; y0=(y[n2]-y[n1])/2+y[n1]; r1=20000; for(i=1;i<=nn;i++) { if(i==n1||i==n2)continue; dx=x[i]-x0;dy=y[i]-y0; r=sqrt(dx*dx+dy*dy); if(r>=r1)continue; double xn21=x[n2]-x[n1]; if(fabs(xn21)<0.001) { if(fabs(x[i]-x[n1])>0.1){r1=r;ver[l][3]=i;} } else{ double a1=(y[n2]-y[n1])/(x[n2]-x[n1]); double b1=(y[n1]*x[n2]-y[n2]*x[n1])/(x[n2]-x[n1]); double ff=y[i]-a1*x[i]-b1; if(fabs(ff)>0.1){ r1=r;ver[l][3]=i;} } } clrscr(); } /*扩展三角形函数*/ void gouwang::kz() { int n1,n2,n3,p1,kv,mm,kw,k0; k=1,kw=111; while(kw==111) { p1=100; kv=0; if(k>1){ p1=pd(1,2); if(p1==200)kv=kv+1; } if(p1==100||k==1) {n1=ver[k][1];n2=ver[k][2];n3=ver[k][3]; mm=kz1(n1,n2,n3); k0=kz2(n1,n2,n3,mm); if(k0!=0)kz3(n1,n2); kv=kv+1; } if(k>1){ p1=pd(1,3); if(p1==200)kv=kv+1; } if(p1==100||k==1) {n1=ver[k][1];n2=ver[k][3];n3=ver[k][2]; mm=kz1(n1,n2,n3); k0=kz2(n1,n2,n3,mm); if(k0!=0)kz3(n1,n2); kv=kv+1; } if(k>1){ p1=pd(2,3); if(p1==200)kv=kv+1; } if(p1==100||k==1) {n1=ver[k][2];n2=ver[k][3];n3=ver[k][1]; mm=kz1(n1,n2,n3); k0=kz2(n1,n2,n3,mm); if(k0!=0)kz3(n1,n2); kv=kv+1; } if(k==l&&kv==3)kw=222; clrscr(); k=k+1; } } /*计算判别式系数,并将对顶点N3的坐标 代入判别式计下相应的符号, 形参为n1,n2,n3,返回 值为符号mm */ int gouwang::kz1(int n1,int n2,int n3) { double xn21,ff; int mm; xn21=x[n2]-x[n1]; if(xn21==0) {if(x[n3]>x[n2])mm=555; if(x[n3] } else{ ff=kz11(n1,n2,n3); if(fabs(xn21)<0.001) {if(fabs(ff)<0.001)mm=0; if(x[n3]>x[n2])mm=555; if(x[n3] else{ if(fabs(ff)<0.001)mm=0; if(ff<-0.001)mm=111; if(ff>0.001)mm=555; } } return mm; } /*计算判别式的值并返回之*/ double gouwang::kz11(int n1,int n2,int n3) {double a,b,ff; if(x[5]!=1249)x[5]=1249; if(x[6]!=1202)x[6]=1202; a=(y[n2]-y[n1])/(x[n2]-x[n1]); b=(y[n1]*x[n2]-y[n2]*x[n1])/(x[n2]-x[n1]); ff=y[n3]-a*x[n3]-b; return ff; } /*用于寻找符合扩展条件的点, 并用来扩展,即找出与n3点不在同一侧的点 并计算与n1,n2?连线的夹角需要参数n1,n2,n3, 返回 k0,k0记录的是与n1,n2形成的最大夹角的 点号*/ int gouwang::kz2(int n1,int n2,int n3,int mm) { int m1=mm,m2,k0=0; double dx1,dx2,dy1,dy2,x21,y21,aa,bb,cc,coc,tt=0; l=l+1;ver[l][3]=0; for(int i=1;i<=nn;i++) { if(i==n1||i==n2||i==n3)continue; m2=kz1(n1,n2,i); if(m1==0||m1==m2)continue; dx1=x[n1]-x[i];dy1=y[n1]-y[i]; dx2=x[n2]-x[i];dy2=y[n2]-y[i]; x21=x[n2]-x[n1];y21=y[n2]-y[n1]; aa=dx2*dx2+dy2*dy2; bb=dx1*dx1+dy1*dy1; cc=x21*x21+y21*y21; coc=1-(aa+bb-cc)/(2*sqrt(aa)*sqrt(bb)); if(coc>tt){tt=coc;k0=i;ver[l][3]=k0;} } if(k0==0)l=l-1; return k0; } /*用来判断新扩展的三角形是否有效若无效则令L=L-1*/ void gouwang::kz3(int n1,int n2) { int l1,kk=0,mm=0,ll=0; l1=l-1; if(ver[l][3]==0)return; for(int i=1;i<=l1;i++) {if((ver[l][1]==ver[i][1]||ver[l][1]==ver[i][2]|| ver[l][1]==ver[i][3]) &&(ver[l][3]==ver[i][1]||ver[l][3]==ver[i][2]|| ver[l][3]==ver[i][3]))mm=mm+1; if((ver[l][2]==ver[i][1]||ver[l][2]==ver[i][2]|| ver[l][2]==ver[i][3]) &&(ver[l][3]==ver[i][1]||ver[l][3]==ver[i][2]|| ver[l][3]==ver[i][3]))kk=kk+1; if((ver[l][1]==ver[i][1]||ver[l][1]==ver[i][2]|| ver[l][1]==ver[i][3]) &&(ver[l][2]==ver[i][1]||ver[l][2]==ver[i][2]|| ver[l][2]==ver[i][3]))ll=ll+1; } if(mm==2||ll==2||kk==2) {ver[l][3]=0;l=l-1;} else{ver[l][1]=n1; ver[l][2]=n2; } // return 0; } /*判断用于扩展的第k号三角形是否与前L个三角形的某条边重合,若重合则不扩展*/ int gouwang::pd(int a,int b) { int pp=100; for(int i=1;i<=l;i++) {if(i==k)continue; if((ver[k][a]==ver[i][1]||ver[k][a]==ver[i][2] ||ver[k][a]==ver[i][3])&&(ver[k][b]==ver[i][1]|| ver[k][b]==ver[i][2]||ver[k][b]==ver[i][3]))pp=200; } return pp; } 三、主程序 #include"gouwang.h" gouwang::gouwang() { ii=0; k=0; l=0; for(int i=0;i<=nn;i++) {for(int j=0;j<4;j++) ver[i][j]=0;} FILE *fp; if((fp=fopen("c:\\\\data\\\\xyhd.bat {cout<<"canot not open xyhd.bat"< exit(0); } fread(x,sizeof(x),1,fp); fread(y,sizeof(y),1,fp); fread(h,sizeof(h),1,fp); fread(d,sizeof(d),1,fp); fclose(fp); nn=d[0]; // cout<<"nn=";cin>>nn; for(i=1;i<=499;i++){d[i]=0;h[i]=0;} for(i=nn+1;i<=499;i++){x[i]=0;y[i]=0;} //cout<<"nn="< } void gouwang::print() { cout<<"k="< {printf("x(%d)=%f\",i,x[i]); printf("y(%d)=%f\",i,y[i]); printf("h(%d)=%f\",i,h[i]); printf("d(%d)=%d\\n",i,d[i]); if(i%10==0)getch(); } getch(); } void gouwang::minxy()//寻找左下角的点函数，存放在全局变量ii中 { double r,r1; ii=1; r=sqrt(x[1]*x[1]+y[1]*y[1]); for(int i=2;i<=nn;i++) {r1=sqrt(x[i]*x[i]+y[i]*y[i]); if(r1 } //cout<<"minxy="< void gouwang::mittxy()//寻找中心的点函数，存放在全局变量ii中 {double xx,yy,r,r1; ii=1; r=10000.0; yy=0.0; xx=0.0; for(int i=1;i<=nn;i++) { xx=xx+x[i]; yy=yy+y[i]; } xx=xx/nn; yy=yy/nn; for(i=1;i<=nn;i++) {r1=(x[i]-xx)*(x[i]-xx)+(y[i]-yy)*(y[i]-yy); r1=sqrt(r1); if(r1 } //cout<<"mittxy="< int main() //主调函数 {clock_t star,end; gouwang a; //定义类变量a //a.print(); //调用类成员函数print() a.minxy(); //调用类成员函数minxy() a.mittxy(); //调用类成员函数mittxy() a.sjx1(); //调用类成员函数sjx1() star=clock(); a.kz(); //调用类成员函数kz() end=clock(); a.graph(); //调用类成员函数graph() a.ht(); //调用类成员函数ht() cout<<"star="< closegraph(); return 0; } 四、绘图部分 /*屏幕初始化函数*/ #include"gouwang.h" void gouwang::graph() { int gdriver,gmode; detectgraph(&gdriver,&gmode);/*自动测试硬件*/ //cout<<"detect graphics driver is"< //getch(); initgraph(&gdriver,&gmode,"c:\\\\bc4\\\\bgi");/*初始化*/ int gerror=graphresult();/*检测初始化是否成功并返回图形操作代码*/ if(gerror<0)/*显示图形操作失败代码*/ {cout<<"graphics initialization error"; cout< exit(1); } // outtext("hello graphics world! Press ang key to your work..."); // getch(); //return 0; } /*坐标转换参数获取函数*/ void gouwang::cshq(double p[2],int maxxy[2], double maxx_minx[2],double maxy_miny[2]) { // cout<<"run cshq():p[0],p[1]begin="< maxxy[1]=getmaxy();/*获取屏幕坐标的最大 y*/ maxx_minx[0]=x[1];maxx_minx[1]=x[1]; maxy_miny[0]=y[1];maxy_miny[1]=y[1]; for(int i=2;i<=nn;i++) { if(x[i]>maxx_minx[0]) maxx_minx[0]=x[i]; if(x[i] if(y[i] p[0]=maxxy[0]/(maxy_miny[0]-maxy_miny[1]); p[1]=maxxy[1]/(maxx_minx[0]-maxx_minx[1]); p[0]=p[0]/1.2;p[1]=p[1]/1.2; /*求出两坐标系的变换比例参数*/ } void gouwang::ht() { outtext("Run ht()"); char str[3]; int maxxy[2]={1,1};/*屏幕坐标最大值参数数组初始化*/ double p[2]={1.0,1.0};/*X,Y 两方向转换比例系数初始化*/ double maxx_minx[2]={1.0,1.0};//存放最大，最小的X并初始化 double maxy_miny[2]={1.0,1.0};//存放最大，最小的Y并初始化衁 int xy[8]={1,2,10,200,620,450,1,2};/*定义多边形(即三角形)四顶点坐标数组*/ setcolor(RED); setbkcolor(WHITE); //drawpoly(4,xy); // getch(); cshq(p,maxxy,maxx_minx,maxy_miny);/*调用参数获取函数,获取参数*/ for(int i=1;i<=l;i++)/*绘出L个三角形*/ { for(int j=1;j<=3;j++)/*将三顶点坐标转换成屏幕坐标*/ { xy[2*j-1]=-10+maxxy[1]-int(p[1]*(x[ver[i][j]]-maxx_minx[1])); xy[2*j-2]=10+int(p[0]*(y[ver[i][j]]-maxy_miny[1])); } xy[6]=xy[0];xy[7]=xy[1]; drawpoly(4,xy);/*绘制闭合多边形,即三角形函数调用*/ for(j=1;j<=3;j++) {sprintf(str,"%d",ver[i][j]); outtextxy(xy[2*j-2]+10,xy[2*j-1]-2,str); } } }
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
