TIN向规则格网DEM转换的快速算法

TIN向规则格网DEM转换的快速算法 130 No14 Vol第 30 卷第 4 期 测绘科学 2005 年 8 月Science of Surveying and Mapping Aug T IN 向规则格网 D EM 转换的快速算法 吴飞 , 吴凡 ()武汉大学资源与环境科学学院 , 湖北 武汉 430079 【摘 要】从 T IN 内插成规则格网可以获得高质量的 D EM 。在内插过程中 , 需要重点解决的问题就是如何快速查 找待插点所在的三角形 。本文介绍了一种基于建立空间索引实现 T IN 到 D EM 的快速转换算法 , 通过建立的索引 , 可以大大地提高检索的速度 , 提高内插的效率 。最后本文通过实验验证了该算法的正确性与可行性 。 【关键词】 T IN ; D EM ; 格网分块 ; 空间索引 ; 空间内插 () 【文章编号】1009 - 2307 200504 - 0076 - 02 【中图分类号】P208 【文献标识码】A , 存储经过该块的三角形号 。这 小是划分的子块的总个数 1 引 言 种方法一次性的申请内存 , 最后一次性的释放 , 比使用动 在建立 D EM 的时候 , 规则格网模型经常被用到 。规则 态链效率高 。 格网具有数据结构简单 , 存储量小 , 属性值便于存储 、管 3 快速转换算法的实现 理以及计算等优点 。构建规则格网的常用方法是 : 先 311 数据结构的设计 建立 T IN , 然后由 T IN 内插成规则格网 D EM 。因为在建立 T IN 时充分考虑了等高线自身的特征 , 能够顾及地形特征 , 要建立空间索引 , 需要以下的数据结构 :可以灵活 的 适 应 任 意 复 杂 的 图 形 数 据 , 运 行 速 度 也 很 快 , 三角网链表 , 存储三角形 :1 因此该方法应用十分广泛。另外构建规则格网的方法还 t ypedef st ruct Tin 有 : 由空间离散点数据插值得到或者从等高线直接内插得 { D PO IN T dp1 ; / / 三角形的顶点 到 。和这两种方法比较 , 由 T IN 内插成 D EM 的方法无论 D PO IN T dp2 ; / / 三角形的顶点 D 在精度 还 是 在 效 率 方 面 都 是 最 优 的 。从 T IN 向 规 则 格 网 PO IN T dp3 ; / / 三角形的顶点 D EM 转换的过程是 : 在对原始等高线生成 T IN 的基础上 , TriAngle Index 3 next ; / / 后继指针 利用点集对应的三角形 , 判断当前格网节点属于哪个三角 T IN ; } 2 形 , 由此三角形内插出格网节点的高程值。在这一过程 格网链表 , 存储栅格化三角形所经过的块 ; 中 , 需要解决的问题就是如何快速查找待插点所在的三角 t ypedef st ruct cel Grid 形 。内插过 程 中 如 果 每 次 都 要 对 所 有 的 三 角 形 进 行 比 较 , { int row ; / / 块的行号 ( 特别是对于大的数据量 , 构造的三角形的数量会很庞大 本 int col ; / / 块的列号 ) 文实验用 7 917 个点构造了 15 451 个三角形, 相应的内插 cel Grid 3 next ; / / 后继指针效率是极其低下的 。如何解决这个问题就尤为重要 , 因此 } CEL GR ID ; 我们用空间索引技术来达到快速搜索的目的 。 动态字符串数组 , 它的大小是划分的子块的总数 , 下 标表示子块号 , 存储的是经过该块的三角形号 : CSt ring 32 实现快速转换的基本思想 p IndexOfBlock ; 随着地理信息系统的发展 , 越来越多的空间数据需要 312 空间索引的建立有效的管 理 , 这 使 得 空 间 数 据 的 索 引 技 术 成 为 研 究 热 点 , ) 1对于给定的范围 , 确定子块的宽度 blockWidt h , 根 3 ,4 并得到了较快的发展。由于 D EM 构建过程中所需的空 据给 定 范 围 的 跨 度 确 定 块 行 数 blockRowNum , 块 列 数 间索引 , 不存在增加 、删除等动态维护操作 ; 因此 , 空间 () blockColNum , 总块数 blockNum 。如式 1所示 : 索引技术的采用主要从算法的空间 、时间效率等方面来考 虑 。本文采用基于网格分块的方法 。基本思路如下 : blockRowNum = LyRange/ blockWidt h ; ()blockColNum L xRange/ blockWidt h ; 1 )从等高线生成 T IN 后 , 将整个内 插 范 围 划 分 成 子 1 blockNum = = blockRowNum ×blockColNum ;块 ; ) 2从 T IN 链表中取出三角形 , 三角形号为 t riangle ID , 6 )2 记录下通过的每个子块的三角形 , 即建立三角形的 用种子填充算法对它进行面栅格化 , 格网大小即是块大 空间索引 ; 小 blockWidt h , 把得到的格网存储在 CEL GR ID 链表中 。该 ) 3检索索引 , 判断当前的格网节点属于哪一块 , 比较 链表是临时的 , 栅格化每个三角形的时候重新生成 。 该块中的所有三角形 , 找出该节点所在的三角形 ; ) 3遍历链表 CEL GR ID , 得 到 每 个 格 网 的 行 列 号 , 开 ) 4用这个三角形的三个顶点拟合一个曲面 , 由该曲面 辟一个 大 小 为 blockNum 的 数 组 p IndexOfBlock , 初 始 值 为 的曲面方程计算出待插格网的高程值 。 空 , 它记录落入每块中的三角形的 ID 号 , 数据类型为字符 本文在建立索引时 , 构造了一个字符串数组 , 它的大串型 。如图 1 所示 。 收稿日期 : 2004 - 10 - 08 () 基金项目 : 国家基础测绘科技资助项目 1469990324231 验 。实验表明 : ) 1建 立 空 间 索 引 后 内 插 的速度会得到显著的提高 , 图 2 是内插时间曲线 , 建立索引 对内插效率的影响从中可见一 ( 斑 。特 别 当 数 据 量 变 大 或 格 1 空间索引的建立 图 ) 网间距减 小的 时 候 这 种 影 响 (格网表示划分的子块 , 数字表示经过此块的三角形 , 就更加明显 。 ) 字母表示块的行列号算法描述如下 :) 2决 定 分 块 划 分 大 小 的 ( ) while CEL GR ID 不为空blockWidt h 值 , 与建空间索引 row = CEL GR ID2 > row ; 所用 的 时 间 成 反 比 , 与 D EM ({ A : 未建立索引所用时间曲线 , col = CEL GR ID2 > col ; )B : 建立索引后所用时间曲线的生成效率也有着明显的相关 row 得到块的序列号 block ID =图 2 内插时间曲线3 blockColNum + 关系 。如图 3 所示 。 col ; 试验 生 成 的 D EM 格 网 间 p IndexOfBlock block ID = 距是 50m , D EM 分辨率是 486 行 ×856 列 。可以看出当格 p IndexOfBlock ( ) Cst ringt riangle ID + “”; block ID + 网大小和分块建立索引的子块的大小接近时所用的时间最 } 少 , 生成 D EM 的效率最高 。 313 空间索引的检索和插值 5 结 论 建立好空 间 索 引 后 就 可 以 进 行 搜 索 三 角 形 的 工 作 了 。 搜索的过程如下 : 本文 讨 论 了 如 何 由 T IN ) 1由内插格网号 grid ID 、格网的列数 gridColNum 、格快速 内 插 成 规 则 格 网 D EM 。 网的宽度 gridWidt h 以及格网的最小坐标值 grid x0 , grid 首先 , 建 立 三 角 形 的 空 间 索 () y0 求出格网的中心点 P T 的坐标 P Tx , P Ty , 如式 2所示 : 引 , 然后检索索引得到待插点 (曲线 A 代表建立索引所用时间 , row = grid Index/ gridColNum ; 所在三角形 , 最后由三角形内 )曲线 B 代表内插所用时间col = grid Index %gridColNum ; 插出待插点的高程 ; 并对算法 图 3 blockWidt h 值与所用 P Tx = col 3 gridWidt h + gridWidt h/ 210 + x0 grid ; 的效 率 进 行 了 分 析 。实 验 证 时间的关系曲线 P Ty grid ; = row 3 gridWidt h + gridWidt h/ 210 + y0 明 , 索引的建立可以大大减少 ()2 从 T IN 转换成格网 D EM 的时间 , 特别是在大数据量的时 ) 2由 grid x , grid y 、块的列数 blockColNum 、块的 候 , 效果就更加明显 。证明了在 T IN 转换成规则格网时建 宽度 blockWidt h 以及块的最小坐标值 block x0 , block y0 立索引的必要性以及空间索引建立的正确性 。 () 求出该点位于哪一块内 , 如式 3所示 : 参考文献 ( ) row = Pt y2block y0/ blockWidt h ; 1 汤国安 , 赵牡丹 . 地理信息系统 M . 北京 : 科学 ( ) col = P Tx2block x0/ blockWidt h ; 出版社 , 2001 : 1212122 . ()block Index = row 3 blockColNum + col ; 3 2 柯正谊 , 何建邦 , 池天河. 数字地面模型 M . 北 ) 3遍历索引 , 取出经过该块的三角形的序号 , 从 T IN 京 : 中国科学技术出版社 , 1993 .链表中取出该三角形 。断点 P T 是否位于该三角形内 , 如果 3 Vol ker Gaede , Oliver Gunyher . Multidimensio nal access 是就内插出该点的高程值 , 否则继续查找 , 直到数组遍历 met hods J . ACM Co m p uting Surveys , 1998 , 30 结束 。() 2: 1702231 . 遍历过程如下 :4 岳小 平 , 鞠 时 光 , 李 芷 . 空 间 数 据 索 引 技 术 J . 取出索引的值 , 赋给字符串 st r 计算机应用研究 , 2002 , 2 : 32234 . 在这个字符串中找到空格的位置 positio n 5 马照亭 , 潘懋 , 胡金星 , 等 . 一种基于 T IN 的地形 ()while positio n > 0 剖面线生成算法 J . 地理与地理信息科学 , 2003 , { 从 st r 中取出 positio n 前的字符串 , 赋给新的字() 19 6: 28230 . 符串 temSt r6 David F Rogers. Procedural Elements for Computer Graghics temSt r 就是首个三角形序号M . 北京 : 机械工业出版社 , 2002 , 992102. 从 st r 中删除首个三角形序号 , 后续的三角形成为 首三角形 ( ) 作者简介 : 吴 飞 19812, 男 , 安 徽 安 庆人 , 现 为 武 汉 大 学 资 源 与 环 境 科 学 学 判断并且插值 ; / / 院地 图 学 与 地 理 信 息 系 统 专 业 研 究 生 , 研 究 方 向 地 理 信 息 系 统 。 E2mail : fly2再次在 st r 中找到空格的位置 positio n woo2002 @1631co m } 6 ABS TRAC TS O F T HE PR ESEN T ISSU E mizatio n and B F GS met hod an algorit hm is given for t he gener2 cial objects on maps alized no nlinear dynamic L S model . Abstract : Mar king special object s o n map s means to mar k Key words : multi2source multi2dimensio n multi2type mul2 various spatial p heno mena and object s o n a map to describe so me ti2 p recisio n and multi2state surveying data ; generalized no nlin2 2 event s or object dist ributio n. General System of Mar king Speear dynamic L S model ; B F GS met hod ; met hod of variables al2 cial Object s o n Map s can mar k different kinds of p rofessio nal ternating mar ks o n t he map background wit h co mp uter . In t his paper , 2shan , The user’s requirement s is analyzed , and t he f unctio n dist ribu2 L I Shu( TAO Hua2xue , ZHOU Chang2yin Shan2 do ng U niversity of Science and Technology Qingdao 266510 , tio n , interface style , data st ruct ure , cent ral arit hmetic and t he )China design are p resented ; The specific sof t ware st ruct ure and real2 izatio n is expatiated. Key words : map ; mar king ; informatio n system The integration of “3S”techn iques and their appl ications in ? ? ? land management L I Ho ng2li , L I Han2ro n , ZHAN G Wei2cheng , A I ?Abstract : This paper discusses t he developing t rend of ( Yo ng2qian ?The Naval Instit ute of Hydrograp hic Surveying “3 S”by int roducing GPS , GIS , RS , t heir integratio n and ap2 & Charting , Tianjin 300061 , China ; ?The U nit 92910 ofplicatio ns in land management . The applicatio n of “3 S”tech2 )PL A , Zhejiang zhoushan 316000 , China niques in land management is developing very vast . The“3 S” techniques integratio n have beco me a powerf ul technique in t he 2sha ding map Research on point annotation of hilldevelop ment and p rogress of land management career . Abstract : This paper analyzed t he current stat us and t he Key words : GPS ; RS ; GIS ; The Integratio n of “3 S” p roblems about t he annotatio n in co mp uter hill2shading. By us2 Techniques ; land management ing t he technique of t he Open GL’s text ure mapping , a series of ( WAN G Zhen2zho ng Henan L and Surveying and Planning p roblems for creating bit map and pointing annotatio n have been )Instit ute , Zhengzhou 450002 , China solved. An inter2operative met hod about point annotatio n wit h fluct uant effect alo ng t he terrain o n hill2shading map is imple2 2major Design and real ization of roa d surveying system f or nonmented. users Key words : annotatio n ; hill2shading map ; text ure map2 Abstract : To meet t he need of up dating elect ro nic map for ping ; open GL navigatio n , t his paper int roduces t he data collectio n and data J IAN G Wen2liang , L I Lin , Hu J ing2yan , ZHA I Liang p rocessing wit h t he applicatio n of GPS in GIS data collectio n. ( School Of Resource and Enviro nmental Science , Wuhan U ni2 It analyzes t he road collecting wit h GPS , and discusses key )versit y , Wuhan 430079 technique of visualizatio n data editing wit h Map X. So me result s are p resented The road surveying system which f ulfils t he naviga2 An eff icient algorithm f or converting TIN to grid D EM tio n p recisio n for no n2major users is realized. 2 Abstract : Interpolating t he T IN to GR ID can p rovide p re Key words : gp s ; navigatio n ; road surveying ; data col2 cisio n D EM data . In t he p rocess how to loo kup t he needed t ri2 lectio n angle efficiently is a key p roblem. This paper p rovides an effi2 (SHI Shan2bin , ZHAO Do ng2qing , L U Zhi2ping 3 S Engi2 cient algorit hm for co nverting T IN to GR ID base o n spatial in2 neering Research Center , Instit ute of Surveying and Mapping , dex , which can accelerate t he interpolatio n. And t he experi2 Informatio n Engineering U niversity , Zhengzhou , Henan , P. ment illust rates t hat it is efficient . )R. China , 450052 Key words : T IN ; D EM ; spatial index ; interpolatio n ( WU Fei , WU Fan School of Resource and Enviro nmental )Using struts in attribute data query of Web GIS system based Science , Wuhan U niversity , 430079 on arc IMS Abstract : MVC is an ideal mode for web applicatio n. And 2based virtual scene The construction of 3D Web ( ) St rut s can be used to embody MVC effect ually. The web GIS Abstract : The develop ment of World Wide Web WWWsystem based o n Arc IMS neads efficient met hod to perform web has brought about a lot of Internet2based applicatio ns. The dis2 applicatio ns such as data querying f ro m co mmercial database li ke play and analysis of t hree2dimensio nal scene o n t he web is a Oracle etc. St rut s can make our web GIS system bet ter for hot spot in GIS and it needs 3D models and 3D virt ual scene to f unctio n extending and code up dating. abst ract and rep resent t he real world. So it is necessary to st udy Key words : Arc IMS ; MVC ; st rut s ; Web GIS 3D models , 3D virt ual scene and 3D scene languages to imple2 ? ? ( ment Web2based 3D GIS. This paper discusses t he 3D scene WU Fang , WAN G Ling ?School of Remote Sensing languages such as V RML and J ava3D , gives detail descrip tio n and Informatio n Engineering , Wuhan U niversity , Wuhan of t heory and implementatio n2mechanism of V RML and J a2 ) 430079 ; ?L and Plan Bureau , Shenzhen518031 , China va3D. Finally it is demo nst rated t hat V RML &J ava3D can gen2 The design and real ization of general system f or marking spe2 erate a dynamic , real2time , interactive , dist ributed t hree2di2