l学术探讨经验交流 二二一… 三角网格等值线的追踪与填充 刘静玮 (成都理工大学,四川 成都 610059) [摘要] 等值线是一种形和数的统一,在许多领域是成果数据表示的重要图件之一。常规的等值线绘制方法分为矩形 网格法和三角形网格法两种,三角网法不仅适合于规则的网格数据,也适合于不规则、甚至畸形分布的散乱数据。本文介绍了 使用三角网实现追踪等值线,使用弦长样条插值方法对等值线进行插值处理,最后结合二维块体追踪技术对等值线图区域进 行追踪并填充。 [关键词] 三角网格;等值线;三次样条曲线;二维块体追踪 1.引言 2.等值线的追踪 2.1三角网格数据结构 表1三角网表(GTriMesh) 等值线是制图对象某一数量指标值相等的各点连成的 平滑曲线,由地图上标出的表示制图对象数量的各点,采用 内插法找出各整数点绘制而成的。 常见有等温线,等压线,等高线,等势线等。以一组相等 数值的连线表示制图对象数量、特征的地图,简称等值线 图,如年平均气温图、年降水量图。它是专题地图的重要图 型,最先用于描述地形。常见的有表现地势起伏和地貌结构 顶点列表 points 三角形列表 triangles 边列表 triEdges 通过GTriMesh数据结构可以向顶点列表添加顶点,插 的等高线图与等深线图;表现气温、水温、地温变化的等温 线图;表现大气降水量变化的等降水量线图;表现地磁、地 震变化的等磁偏线图、等磁力线图、等震线图。另外,还有等 压线、等风速线、等日照线、等云量线、等湿度线、等密度线、 等透明度线、等盐分含量线、等时线等图。通常等值线所代 表的数值为整数。 入顶点,删除顶点,得到顶点的数目。可以向三角形列表追加 三角形,并可以通过下标得到指定的三角形。可以通过边列 表得到边界边的数目,通过下标得到边界的指针,可以通过 顶点编号得到对应的边指针。可以根据当前三角网建立自身 的边表。 等值线地图的编制,通常是在地理底图上标出制图对 象的相对点位(测站)的数值,然后把数值相等的点联成圆滑 曲线,勾画出制图对象的空间结构特征。等值线地图还常辅 以分层设色,以提高地图的直观效果。 等值线生成方法中,大体上可归纳为三种方案: 表2顶点结构类(GPoint) 二维顶点坐标 顶点属性值 value mVector( ̄维数组,0位置表示x坐标, 1位置表示Y坐标) 表3边索引类(GTriEdge (1)利用四边格网的高程点,采用线性插值直接进行等 值线的生成; (2)以不规则原始数据为依据,用二阶曲面方程、三阶曲 面方程、二元三次样条函数等拟合一张曲面Z=f(x,Y1,然后 在GriEdge索引类数据结构中,IdxCode用无符号64位 整形存放,高位存放v0,低位存放v1,可以得到唯一边。在类 以输入数据为规则网格点的平面坐标来调用模拟地形的曲 面方程,在求得所有网格点高程后再追踪等值线; 中可以得到v0和vl的索引,得到三角形索引,得到共边的 三角形数目。 (3)先以离散数据点构成TIN,然后再基于TIN进行等 值线的生成。 基于规则网格的等值线生成算法又称为规则网格法, 基于TIN的等值线追踪算法又称为不规则网格法,无论采 用哪一种方法进行等值线生成,所要研究的基本问题是相 利用三个数据结构,可以通过三角网的数据结构访问到 项点,得到顶点相关属性值和坐标;通过边表可以访问边索 引类,可以得到一条边,通过这条边我们可以到相关的两个 顶点坐标及属性值,还可以得到由该边组成的三角形数目, 还可以得到需要访问的三角形索引表;可以访问三角形列 表,可以访问某个三角形的边和顶点的属性值和方法。 同的,如等值点位的计算、等值线的追踪、并对生成的等值 线进行光滑等。 作者简介:刘静玮,男,四川雅安人,本科。研究方向:多媒体与图示技术。 66— 2.2三角网的等值线生成算法 (1)得到所有顶点,并对每个顶点添加索引。并设定一个 bool数组mEdgeAccessList用来设置在三角网格中的所有边 是否已被引用。 (2)判定每个点的值是否与当前搜索的等值点的值相同, 若相同,对于奇异点三角网顶点特征值Z =z(i=1,2,3),提出 了对所有这样顶点z 加上一个(或减1一个微小正数。 (3)由GTriMesh可以到所有边的数目,通过改变共用的 三角形数目来判定边是属于内边界,还是外边界,将边界分 为内、外两组。 (4)检查外边界,追踪全部开曲线,判断该边是否已被 引用。如没有,则判断该边是否有等值点。判断方法:由该条 边的两点的特征值Za,Z 得到。 若:(za_z) (Zb.z)>0 I31,该边无等值点,反之则有等值点。 并把该边作为等值线的起始点,把该边的bool值设为true。 (5)在确定了等值点所在的边后,就可用线性内插法求 出等值点的坐标值,把此点作为等值线经过三角形的进入 点 Xi=X ̄+(Xb-Xa) ((Z—Z ̄)/(Zb-Z )) Yi=Y +(Yb-Ya) ((z—za)/(z『za)) (6)用(4)中的判别法求得该边所组成的三角网的中另 外两条边中哪边含有等值点,把该边设为true,并按照(5)求 得等值点在边上的坐标。直到遇到边界线f即该边共用的三 角形数目只有一个)。 (7)求闭合等值曲线和开曲线类似的,从内边界的数组 中开始搜索。经过(4)的判断和(5)求等值点,最后判断点是否 为起点,如果是,则闭合等值曲线绘制完成。 图1矩形网格追踪等值线 图2三角网格法追踪的等值线 2.3利用累加三次样条曲线对等值线进行插值 用样条函数方法构造参数曲线时,需知道每个数据点处 的参数值,而实际应用中,参数值在很多情况下是无法预知 的,因此在构造参数样条曲线的第一步是将给定的数据点 经验交琉学术探讨l _上一 ————__三 参数化,即为每个数据点确定节点的参数值,而节点参数的 选取方法将直接影响所构造的曲线插值精度和形状。目前 常用的节点参数选取方法有:均匀参数化法、累加弦长参数 化法、向心参数化法和修正弦长参数化法。其中累加弦长法 应用最为广泛,其基本思想是以弦长参数近似取代弦长参数 为数据节点的参数。 下面给出累加弦长三次样条曲线的定义:在平面直角坐 标系中有n+1个型值点{P (x。,Y。),(i=O,1,2,……n)},相邻 两个型值点之间的弦长为Li=、/ 造三次样 条函数,取参数t的间隔为O=to<tl<t2<……<tn,其中t。=0 (i=O),t =ti-i+L(i>O)。 定义t为每个节点的累加弦长,对每个节点t.分别以 x。, 为插值数据,构造参数样条曲线: …P(t、) fX(t);=S:s (t); 其中Sx(t)为以t为自变量对x的三次样条函数,S (t)为 以t为自变量对Y的三次样条函数。 P(t)即为累加弦长三次样条曲线。实践证明如图2与图 3比较,累加弦长三次样条,对于解决大扰度、多曲线具有很 好的效果,同时其只与相邻的三个节点相关,所以同样能保 证对其曲线局部特征的描述。 图3累加弦长样条插值等值线效果图 3.等值块体追踪 3.1块体追踪交点表的结构 表4等值边界点(GISOEdgePoint1 边界点的属性值 标记该点是否已 对应的等值线值 rnPtType(0:顶点;1:等值 经被使用 mValue f顶点对应 线开始;2:等值线结束) tmUseFlag 为0) 表5等值线区域追踪类(GISOBlockTracer1 网格数据指 开曲线追踪 非闭合曲线 闭合曲线集 针 起始边界点 边界点列表 集合 mpGridData (mBegin— mEdgePoints mOpenLine— mCloseLine— Point) Set Set 通过GISOBlockTracer类,可以追踪等值区域,并对其填 充值。 3.2块体的追踪算法 等值线的一些性质: 性质1各条等值线必不相交。 性质2对于给定的某个属性值value,相应的等值线数 一67— jl 学术探讨经验交流 L———— ——————————一‘‘ 一’——‘‘…~ ’———— — ———一 量可能不止一条。 性质3 出于定义域是有界的,等值线可能是闭合的, 也可能是不闭合的。 步骤1把等值区分为由非封闭等值线和边界线组成的 非闭合区和由闭合等值线组成的闭合区,所对应的算法也 就分为非闭合区算法和闭合区算法。 r1)形成非闭合区算法:将所有非封闭等值线的起点、终 点以及区域矩形的四个顶点按逆时针顺序排序(也可按顺时 针1,存放在如mEdgePoints,即为边界点序列。首先在边界 点序列中取出标记为未使用的一点Pi(xi,),i)作为当前点,若 此点为顶点,则返回继续搜索边界序列中的下一个点,若此 点为等值线的起点,则把该点标记为已使用,把此点加入到 区域中;若此点为等值线的终点,则把此条等值线反向加入 到区域中,把此点作为当前点,并且标记为已使用,继续查 找下个一个点。如此循环,直到回到起始点pi(x ,Yi)为止,从 而形成一个闭合的连通区域,即非闭合区。依次在边界点序 列中取出标记为未使用的另一点pi(x.,yi),重复刚才的方法, 就能形成一个个新的连通区域。直到将所有标记为未使用 的边界点都己使用,这样就得到了所有的非闭合区。 在搜索查找下个点时,遇到岔口时此处提出了判断点 搜索方向的方法。利用平面搜索的最小顺时针夹角原则[2J来 判定选择点方向,并给出角度的计算方法。 设矢量P:(X ,Y1),Q=(X:,y2),则矢量叉积定义为由 (0,0)、P 、P:和p +p:所组成的平行四边形的带符号的面积, 即:px Q=Xl y2一X2 Y ,其结果是一个标量。显然有性质 P×Q=一(Q×P)和px(一Q)=一(px Q)。一般在不加说明的情况 下,本文下述算法中所有的点都看作矢量,两点的加减法就 是矢量相加减,而点的乘法则看作矢量叉积。叉积的一个非 常重要性质是可以通过它的符号判断两矢量相互之间的顺 逆时钊 关系: 若P×Q>0,则P在Q的顺时针方向。 若px Q<0,则P在Q的逆时针方向。 若P×Q=0,则P与Q共线,但可能同向也可能反向。 利用P×0符号来判断下个点处在当前点的方向。利用 向量点乘可以求得向量之间的夹角COS0=(a・b)/(1al*lb1),0 可以用反余弦公式得到,并对其做绝对值处理l0l。若下一个 点在当前点的逆时针方向,则用d=360。.0,如果下个点处于 当前点的顺时针方向,则 =l 0l,如果下个顶点和当前点处同 向或反向,则让得到 =180。。根据求得下个点处于当前点 的方向求得d,选择角度更小的那个点作为下一个点。 (2)形成闭合区的算法:闭合区的形成较非闭合区的形 成简单一些。首先,在每一条闭合的等值线中找出横坐标最 小的点,然后将这些闭合的等值线按照横坐标最小的点坐 标从小到大依次进行排序。这样,同心区域中的内部闭合区 域将排在外部闭合区的后面。当按照从外到内的顺序填充 时,内部闭合区必然填充不同于外部闭合区的颜色。 步骤2填充颜色:对于非闭合区域来说,从非闭合构成 的等值线开区域集合中取出一条开区域边界线,判断构成 当前等值区域是否由两种不同的等值曲线构成,如果是,则 取等值区域的为两个等值的平均值,如果开区域仅由等值相 同的曲线构成,必须根据边界点与周围边界点的关系判定, 只查找区域中的边界点,找到不同的等值并设置该区域的 值,把当前得到的等值区域添加到填充区域集合中。对于闭 合区来说,从闭曲线集合中得到一条边界曲线,对闭曲线形 成的闭区域设置一个包围盒子,把该闭区域加入到填充区域 集合中,按包围面积大小排序所有填充区域,通过不同的填 充值从填充区域集合中得到闭区域,查找闭区域的外包围区 域,判断当前填充区域集中的形成闭区域的点构成的多边形 是否包含填充区域的点,如果是,则跳出循环,设置闭区域 的填充值。如果无法找到外包围区域,查找内包围区域,并 设置相应的填充值,如果无法查找到内、外包围区域,给该 填充区域设置保险值。 图4等值区域填充 4.结语 本文针对基于三角网的等值线的追踪生成提出了算法 实现方法和奇异处理方法;并且指出累加弦长三次样条算法 作为等值线光滑算法的优点,经过在实际应用证明,累加弦 长三次样条算法作为等值线的一种光滑算法,可以提高等值 线的拟合精度,且方便灵活,易于编程实现,具有广泛的应 用前景,最后给出了等值区域的搜索和填充算法,实现了等 值线绘制到填充的整套算法。 参考文献: 【】】1王淼导航GPS道路轨迹自动矢量化[D】上海:同济大学土 木工程学院,2009,03 f2]徐能雄,段庆伟,梅钢,武雄,田红三维地质建模方法及程序 实现[M】.北京:地质出版社,2011,2 【3】胡德鹏,黄晓萍,任年海.基于不规则三角网(TIN)的追踪等值 线算法及对等值线光滑算法的研究【I1. 计算机与信息技术,2006, (03) [4]孙桂茹,马亮,路登平,赵国瑞,都嘉林等值线生成与图形填 充算法lI1.天津大学学报(自然科学与工程技术版),2000,(06). 【5】LAN Renehun,YAOLan,OPtimized Triangulation Algorithm in Terrain Modeling[J】.Geos Patial Information Seienee,2007,(1) [6]刘冬群,戴建,林红,贺千山 基于等值线分类的区域填充算法 【Il_气象科技,2009,(05). [7]韩丽娜,石昊苏,张群会,基于边界点追踪的等值线图区域填充 算法U Jl计算机工程与科学.2006,28(11). 【8】孟雅琴,叶正麟,王小平,郑红蝉.空间均匀有理张力样条参数 曲线 计算机学报,2003,(12). 学 堡 _l_ ———— Contour Line Tracking and Filling Based on the Triangular Mesh Liu Jingwei (Chengdu University ofTechnology,Chengdu 610059,Sichuan) 【Ab曩嘲】 Contour line is the unity of form and number. It is one of the important datum resuits in many areas.There drre two kinds of contour line drawiing methods which are rectangular grid and triangular mesh.Triangulation method is not only suitable for regular grid data,but also suitable for irregular and even deformed distirbution of scattered data.This paper introduces the triangulation method to realize tracking contour line and the spline interpolation method to interpolate the contour line.Finally,we combine with two・dimensional block tracking technology to track and populate the isoline areas. 【l【| 喇m】triangulra mesh;isoline;cubic spline curve;two.dimensional block tracking (上接第63页) Research on the Integrated Course System in Computer Specialty of Technician Institute Wang Hao Tian Fengchun r1.Zhejiang Commercial Technician Institute,Ningbo 315012,Zhejiang; 2.Nanjing Xiaozhuang University,Nanjing 210029,Jiangshu) 【 b—mct】 This paper naalyzes the current enteprrise occupation post demands,optimizes the specialyt course structure,and con. structs the teaching pattern of integrated practice course for technician academy,to train the computer professionals with strong OCCU— pation ability and technical ability for enterprises. 【 唧 】technician institute;teaching reform;course system (上接第65页) The Application of Four Steps Teaching Method in Flash Course Deng Biqin (Guangzhou Light Industry Technicina College,Guangzhou 510545,Guangdong) 【 ,曲m醴】 Flash is a basic course of multimedia major.This paper introduces four steps teaching method,and discusses the whole teaching process in masking animation.With the teaching practice,it achieves good results. 【 哪山】flash;teaching method;action oriented;discovery teaching method