基于点的三角形构网算法及等值线自动生成方法

计算机与现代化2004年第5期JISUANJIYUXIANDAIHUA总第105期文章编号:100622475(2004)0520007203基于点的三角形构网算法及等值线自动生成方法郑盛贵,颜七笙,黄临平(东华理工学院,江西抚州344000)摘要:总结了各种等值线生成的方法及特点,详细阐述直接利用三角形网格生成等值线的原理、实现方法,独立开发出基于VCγγ的Contour绘图类,并嵌入电磁资料处理系统软件,为电磁资料的等值线可视化表示提供了便利。关键词:三角网;等值线;程序实现中图分类号:TP31文献标识码:AAlgorithmofTriangleConstructedGridBasedonPointsandMethodofAutomaticallyEstablishmentContourZHENGSheng2gui,QANQi2sheng,HUANGLin2ping(EastChinaInstituteofTechnology,Fuzhou344000,China)Abstract:Thecharacteristicsandapproachesofgeneratingcontouraresummarized,thetheoryandapproacheofusingtrianglegridgener2atingcontourdirectlyaredescribedindetail.TheVisualCγγcontourplotclassisdevelopedandisembeddedinthesystemofelectromag2neticdataprocessing,thusitprovidesgreatconvenienceforthevisualizationofcontourofelectromagneticdata.Keywords:triangulargrid;contourtracing;programmingrealization绘制等值线是对大量离散的、又具有一定规律的几何1概述量值或物理量值,用数学的方法插值变换成图的过1.1基于点的构网算法程。等值线绘制常采用矩形网格法和三角网格法两种。矩形网格法的基本思想是利用离散高程数据点,建立一个逼近于地形表面的曲面模型,并在此模型上迄今为止,建立矩形和三角形网格模型有很多种方法。建立矩形网格比较流行的算法有:按距离成反比的加权法、径向基函数插值法、B样条曲面插值法、内插出网格点的高程,形成规则的矩形网格数据,然有限元方法等;建立三角形网格比较流行的算法有De2后在每个矩形网格边上内插出各条等值线所有等值点的平面位置,并按一定的方法把各条等值线所有等值点全部追踪出来,最后连接成光滑曲线。三角网格法则是直接利用原始数据离散高程数据点剖分成三角形网格,然后在三角形单元边上内插出各条等值线所有等值点,并按一定的方法把各条等值线所有等值点全部追踪出来,最后连接成光滑曲线,与矩形网格法相比,三角网格法保持了原始数据的精度,现有的大比例尺数字测图系统多采用这种方法。各种网格法绘制等值线的步骤一般为:离散数据网格化;网格点数值化;等值点的计算;等值线追踪;光滑和标记等值线[2]。本文重点介绍三角网格法。launay三角形法和周培德提出的“平面点集三角剖分的[1]算法”等。Delaunay三角形法主要有三种方法:①分而治之算法;②数据点渐次插入算法;③三角网生长算法。图1周培德的平面点集三角剖分算法生成的三角形网格1.2等值线自动生成方法计算机自动绘制等值线是一个重要的研究课题,收稿日期:2003206218作者简介:郑盛贵(19762),男,江西临川人,东华理工学院硕士研究生,研究方向:三维可视化、科学计算可视化;颜七笙(19762),男,江西临川人,教研室副主任,讲师,硕士研究生,研究方向:数据仓库;黄临平(19642),男,江西九江人,系副主任,副教授,博士后,研究方向:电磁勘探数据处理数值模拟反演成像。8计算机与现代化2004年第5期公式(2)对区内所有单元进行遍历,记录该等值线通过的单元数(KI)以及特征棱边L(i,j)、L(i,j)及各2等值线的计算122.1数据准备自边的等值点坐标。需要有三角网格的结点、三角形单元、单元边编号信息、梭边集合、几何量值或物理量值。上述数据可归纳如下:(1)网格结点坐标:X,Y,i=1,2,⋯,N,2.棱边性质判断。判断有等值线通过的单元棱边集合中所有的棱边是否为边界边,若L是边界边,记1BL1(L)为1,否则为0,同样判断L,记入BL(L)中。1222iipN为结点总数;(2)三角形单元:TC(i,j,k),i,j,k=1,p3.等值线的追踪。在所有有等值线通过的单元(共KI个单元)内追踪,追踪法则[3]为:等值线游动必2,⋯,N;(3)单元边IJK编号:IJK(i,j),i=1,2,3,j=p1,2,⋯,N,N为区域内网格单元总数;(4)梭边集然穿过共棱边又有等值线通过的单元。其步骤如下:(1)初始化:置某等值线级链表为NULL,并置KII为零;ee合:BL(i),i=1,2,⋯,N,N为梭边总数;(5)网格结点ll(2)寻找等值线起点:先寻找第一个尚未用过的、且棱边为边界边的单元。若找到,以特征棱边为边界的边作为起点边,另一个为后续边;若第一次未找到尚未用过的、且棱边为边界边的单元,则找任意一个尚未用过的单元,以任意一边为起点边,另一个为后续边。然后,分别将起点边和后续边对应的等值点坐标存入等值线链表的第一点与第二点。将后续边对应的结点记入P、P,为下一步的追踪做准备,并给该单元物理量值:Z,i=1,2,⋯,N。ip2.2等值线值确定读入结点几何量值或物理量值,求出最大Zmax及最小Z结点几何量值或物理量值,根据给出的等值min线总条数IPI,计算出等值线间差值DIF,等值线计算公式如下:12DIF=(Zmax-Zmin)/(IPI+1);ZDIF=Zmin+DIF;(1)标记“用过”标志;KII自加1。(3)寻找共棱边的邻接单元:寻找与结点P、P所连边共12棱边的、且尚未用过的单元,将该单元的非共棱特征边作为下一个后续边,记入P、P,对应的等值点坐标存入链表,并置该3等值线追踪12单元“用过”标志;KII自加1。3.1等值点平面位置的确定(4)重复(3)过程,若KIIKI,表明存在等值线分支。因此,重复(2)、(3)、(4)过程,直至所有有等值线穿过的单元全首先进行等值点的判断。对于某一量值为Z的c等值线而言,单元棱边IJ之间存在等值点的条件是:部用完为止,表明本级所有等值线分支均追踪完毕。(Z-Z)3(Z-Z)Φ0(2)icjc3.3等值线分支的判断[3]若Z-Z或Z-Z等于零,则等值点必通过i或icjc根据上述等值线追踪法则,无法判断有多少分支。由分析得知,根据等值线追踪时实际通过的单元总数KII是否等于追踪前单元遍历的单元总数KI的条件来判断等值线是否已经绘制完毕。如果第一次追踪完成后,若KII=KI,则说明本级等值线仅有一条分支且已经绘制完毕,若KIIKI,则说明尚存在有等值线通过且记录为“未用过”的单元,即至少还存在另一条分支,此时可在三角形单元中按本文上述追踪法则继续追踪,从而形成另一条等值线分支,重复上述过程,直到KII=KI为止,表明本级等值线的所有分支均已绘制完毕。j点,此时不利于下一步等值点的追踪,因而只须做简单处理,Z=Z-ε或Z=Z-εε,为很小的正数,使等iijj值线在充分靠近Z或Z的网格点的附近通过。ij对于任意三角形单元,若存在棱边满足条件式(2),必有等值线通过此三角形单元。依式(2)对所有三角形单元遍历,即可求出某条等值线的单元总数KI和有该等值线通过的单元棱边。若某棱边ij存在4数据结构有Z的等值点,则等值点坐标应用线性插值公式得c三角形结点类型为:到:structtrinode{-X-XiZj-ZijX=X+(Z-Zi)cicintvt[3];//三角形的三个结点编号(3)structtrinode3next;-Yj-YiZj-ZiY=Y+(Z-Zi)cci};3.2等值线追踪1.单元遍历。首先,对某一级(m)等值线Z,用棱边结点类型为:structedgenode{-dzc2004年第5期郑盛贵等:基于点的三角形构网算法及等值线自动生成方法9intvergepro;//棱边性质(是否为边界结点)intel[2];structedgenode3next;-};等值线级类型为:structequgrade{-doublezc;//等值线级值structequvalue3next;-};有等值线通过的单元类型为:structequvalue{-intmark;//用过标志structtrinode3tri;-structedgenode3edge[2];-structequvalue3next;-};坐标结点类型为:structcoordvalue{-doublex;doubley;structcoordnode3next;-};5等值线程序编写流程图等值线程序编写流程图如图3所示。给出了图1中25条等值线的结果图。实践表明,本算法方便易行,结论正确,并已经编制了相应的计算机通用程序,在PC机上利用VC编译器调试成功。6结束语本文详细介绍了三角网格上等值线追踪生成的过程,较矩形网格法相比,完全不需要对各离散点的几何量值或物理量值进行曲面拟合,而是直接利用原始离散点构成三角网,保持了原始数据的精度。图4参考文献:[1]周培德.平面点集三角剖分的算法[J].计算机辅助设计与图形学学报,1996,8(4):259～264.[2]成建梅,陈崇希,孙红林.三角网格等值线自动生成方法及程序实现[J].水利学报,1998(10).[3]刘幸.直接法自动绘制等值线[J].武汉水利电力大学学报,1995,28(6):588～593.图4图1中25条等值线的结果图