基于格网的等值线生成与填充算法研究
摘要
随着地理信息系统(GIS)的发展,数字高程模型(DEM)成为空间信息系统的一个重要组成部分,并且是工程建设、战场环境仿真等许多领域最为重要的基础数据之一。由于规则格网模型具有计算处理方法简单有效,且和遥感数据在结构上容易匹配等优点,其被视为DEM中最基本和最重要的一种模型。
等值线图是在石油勘探开发、采矿、地质、地球物理、地球化学和气象等工程和技术领域内应用极广的一种图形,是众多领域成果表示的重要图件之一,它是一种形和数的统一。
本文主要研究了以下方面的内容：基于格网的等值线生成和填充算法。
在基于格网的等值线生成算法中,本文通过采用类似在平衡二叉树中插入结点的方法来选取和建立区间树的结点,通过扫描一次全部的格网单元就能建立起区间树的各级结点。在搜索给定的高程值时,仅对搜索路径经过的结点中的网格单元排序,避免了大量无效的排序,从而减少了搜索时间。
本文提出了一种能够处理复杂多边形下等值线填充的算法。在确定各级等值线之间的空间位置关系时,本文利用格网中等值线与格网单元的关系,利用格网单元边界建立射线,采用射线法原理,能一次判断多个等值线间的包含关系,大大提高了算法的效率。
With the development of Geographic Information System (GIS), Digital Elevation Model (DEM) has become an important part of spatial information system, and one of the best important and basic data in these fields, such as constructing project and emulating battlefield environment.
The isoline graph has been widely used in engineering and technique field, such as oil exploration development, mining, geology, physical geography, geochemistry and meteorology, and it is one of the important maps that the achievement of many fields show. It also unifies shape and data.
The thesis mainly researches the following contents:algorithms of isoline generation and fill based on grid model.
In the algorithm of isoline generation, the process of selecting and creating interval tree nodes is similar with the process of insert nodes in AVL tree, Interval tree's structure can be created by scaning all grids once.When searching the given altitude, we just sort those grids which are belonged to the nodes the search path passed, avoid sort all grids in the interval tree, reducing the search time。
This thesis proposes an algorithm which can fill the isolines graph with random boundaries。When creating the location relationship between all isolines, this thesis utilizes the relationship between boundary of grid and isoline, use boundary of grid and isoline to create radials.By the theory of radial, we can get the location relationship between some isolines once time, and the algorithm is faster than the other algorithms.
等值线图是在石油勘探开发、采矿、地质、地球物理、地球化学和气象等工程和技术领域内应用极广的一种图形,是众多领域成果表示的重要图件之一,它是一种形和数的统一。
本文主要研究了以下方面的内容：基于格网的等值线生成和填充算法。
在基于格网的等值线生成算法中,本文通过采用类似在平衡二叉树中插入结点的方法来选取和建立区间树的结点,通过扫描一次全部的格网单元就能建立起区间树的各级结点。在搜索给定的高程值时,仅对搜索路径经过的结点中的网格单元排序,避免了大量无效的排序,从而减少了搜索时间。
本文提出了一种能够处理复杂多边形下等值线填充的算法。在确定各级等值线之间的空间位置关系时,本文利用格网中等值线与格网单元的关系,利用格网单元边界建立射线,采用射线法原理,能一次判断多个等值线间的包含关系,大大提高了算法的效率。
With the development of Geographic Information System (GIS), Digital Elevation Model (DEM) has become an important part of spatial information system, and one of the best important and basic data in these fields, such as constructing project and emulating battlefield environment.
The isoline graph has been widely used in engineering and technique field, such as oil exploration development, mining, geology, physical geography, geochemistry and meteorology, and it is one of the important maps that the achievement of many fields show. It also unifies shape and data.
The thesis mainly researches the following contents:algorithms of isoline generation and fill based on grid model.
In the algorithm of isoline generation, the process of selecting and creating interval tree nodes is similar with the process of insert nodes in AVL tree, Interval tree's structure can be created by scaning all grids once.When searching the given altitude, we just sort those grids which are belonged to the nodes the search path passed, avoid sort all grids in the interval tree, reducing the search time。
This thesis proposes an algorithm which can fill the isolines graph with random boundaries。When creating the location relationship between all isolines, this thesis utilizes the relationship between boundary of grid and isoline, use boundary of grid and isoline to create radials.By the theory of radial, we can get the location relationship between some isolines once time, and the algorithm is faster than the other algorithms.
引文
[1]Robinson, A.N., The genealory of the isopleths[J], Cartographic J.,1971,8, 49～53
[2]李志林,朱庆.数字高程模型[M].武汉：武汉测绘科技大学出版社,2003,5，145～150
[3]Bi Huaxing, Li Xiaoyin, Guo Mengxia, et al. Digital Terrain Analysis Based on DEM[J]. Frontiers of Forestry in China,2006, (1):54～58
[4]张渭军,李永军,刘向阳.数字地面模型中等高线的自动绘制[J].地球科学与环境学报,2004,26(1)：76～78
[5]赵建三.基于格网DEM的自适应等高线内插方法[J].中南工业大学学报(自然科学版),2003,34(3)：315～319
[6]杨道勇,肖云岫.利用三角形网格进行等值线分析与绘制[J].四川气象,2005,(2)：38～39
[7]刘海涛,秦其明.DEM生成等高线图的再研究[J].地图.2001,2：15～18
[8]VAN KREVELD M. Efficient Methods for Isoline Extraction from a TIN. [J]International Journal of GIS.1996,10:523～540
[9]王涛,毋河海,刘纪平.基于区间树索引的等高线提取算法[J].武汉大学学报(信息科学版),2007,32(2)：131～134
[10]王涛,刘纪平,毋河海.基于排序预处理的等高线提取算法[J].测绘学报,2006,35(4)：390-394
[11]Julie Charleux-Demargne, Christian Puech. Quality assessment for drainage networks and watershed boundaries extraction from a digital elevation model (DEM)[J]. Proceedings of the 8th ACM international symposium on Advances in geographic information systems,2000,89～94
[12]宋丽娟,龚晓峰,钟猛.基于网格法的等值线绘制方法[J].现代电子技术,2005,14：65～67
[13]王永会,宋晓宇,栾方军.基于网格的等值线图快速生成算法[J].计算机工程与应用,2001,17：124～125
[14]吴卫华,袁宁.基于格网的等值线生成算法的研究.试验与研究,2003,(4)：27～30
[15]常会,柴华彬,邹友峰.基于搜索圆法的等值线追踪技术[J].测绘科学,2009,34(2)：119～120
[16]高斌,朱景华,徐振宇,等.基于网格拓扑关系追踪的等值线生成方法 [J].2007,24(6)：4-6
[17]顾滨兵,杨兆海,高宇基,等.基于网格序列法和端点量化的等值线生成算法[J].吉林大学学报(信息科学版),2010,28(1)：89～93
[18]刘斌.地形图等高线的自动绘制[J].全国水力水电测绘科技学术交流会,1998,10：79～80
[19]高正夏,吴继敏,康政虹,等.等值线平滑方法简介及效果比较[J].工程地质计算机应用,2002,3(3)：19～20
[20]陈学工,黄晶晶.等高线高程自动标注算法的研究[J].测绘科学,2007,32(4)：101～103
[21]夏金伟,赵东宝.等高线图等高线高程自动标注算法研究[J].地矿测绘,2004,20(2)：18-20
[22]韩丽娜,石昊苏.等值线标注的一种算法探讨.计算机工程与设计[J],2006,(11)：4084～4086
[23]刘冬韡,戴建华,林红,等.基于等值线分类的区域填充算法[J].气象科技,2009.37(5)：597～599
[24]庞世明,蔡玉华,靳文芳.等值线图的彩色填充方法[J].计算机应用,2004,24(1)：60～62
[25]韩丽娜,石昊苏,张群会.基于边界点追踪的等值线图区域填充算法[J].计算机工程与科学,2006,28：66～67
[26]彭革伟,韩家新.等值线图区域填充的快速搜索算法[J].中国科技信息,2006,17：252～253
[27]孙桂茹,马亮,路登平,等.等值线生成和图形填充算法[J].天津大学学报,2000,33(6)：816～818
[28]吴自银,高金耀.一种基于格网的快速等值线充填算法[J].测绘学报,1999,28(4)：350～354
[29]张登荣,刘绍华,毛天露,等.等值线自动建立拓扑关系算法与快速填充应用[J].中国图像图形学报,6(A)：3,264-269
[30]陈树强,陈学工,王丽青.判定检测点是否在多边形内的新方法[J].微电子学与计算机.2006,23(8)：194～195
[31]陈瑞卿,周健,虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报.2007,41(1)：59～63
[32]宫晓峰.基于OpenGL的三维GIS地形可视化技术的研究与实现[硕士学位论文].北京：北京邮电大学,2009
[33]Floriani LD, Marzano P, Puppo E. Multiresolution models for topographic surface description[J].The Visual Computer,1996,12 (7):317-345
[34]Groshong R H.3-D Structural Geology:A Practical Guide Io Quantitative Surface and Subsurfaces Map Interpretation[J]. Berlin:Springer,2006
[35]黄晶晶.数字高程模型TIN和等高线建模[硕士学位论文].长沙：中南大学,2007
[36]Su Wei Min, Wu Fan. Research on Constructing Contours from Regular Terrain Grids Containing Invalid Data[J]. Journal of China University of Mining and Technology 2004,14 (2):138～142
[37]李志林,朱庆.数字高程模型[M].武汉：武汉大学出版社,2001
[38]Julie Charleux-Demargne, Christian Puech. Quality assessment for drainage networks and watershed boundaries extraction from a digital elevation model (DEM) [J]. Proceedings of the 8th ACM international symposium on Advances in geographic information systems,2000,89～94
[39]汤国安,刘学军,闾国年.数字高程模型及地学分析的原理与方法[M].北京：科学出版社,2005
[40]武俊红,汪云甲.基于Surfer的煤矿等值线空间插值方法有效性评价[J].中国矿业,2007,16(1)：108～110
[41]于海生.复杂断块油田的等值线插值及绘制新方法研究[硕士学位论文].北京：中国石油勘探开发科学研究院,2001
[42]杨锦,张小望.解析插值法在等值线绘制中的应用[J].勘测科学技术,2008,(3)：55～58
[43]林怡,陈鹰.一种数字高程模型生成系统的研究[J].测绘学院学报,2000,(28)9：187～190
[44]蒋红斐,詹振炎.利用锥构建DTM生成算法研究[J].武汉测绘科技大学学报,2000,(13)4：120～126
[45]武俊红,汪云甲.基于Surfer的煤矿等值线空间插值方法有效性评价[J].中国矿业,2007,16(1)：108～110
[46]TOMATISN, NOURBAKHSH I, SIEGWART R. Hybrid simultaneous localization and map building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003,44 (1):3～14
[47]白世彪,陈哗,王建,等.等值线绘图软件SURFER7.0中九种插值法介绍[J].物探化探计算技术,2002,24(2)：157
[48]冯锦明,赵天保,张英娟.基于台站降水资料对不同空间内插方法的比较[J]. 气候与环境研究,2004,9(2)：261～276
[49]颜辉武,祝国瑞,徐智勇.基于Voronoi图的距离倒数加权法的改进研究[J].武汉大学学报,2004,29(11)：1017～1020
[50]郭尚,苏鸿根.基于距离倒数加权法的等值面绘制简化算法[J].计算机工程与设计,2008,29(5)：1200～1202
[51]Mark de Berg, Otfried cheong, Marc van kreveld,等.计算几何—算法与应用(第二版)[M].邓俊辉,译.北京：清华大学出版社,2005
[52]严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,1997
[53]王家耀,崔铁军,苗国强.数字高程模型及其数据结构[J].海洋测绘,2004,24(3)：1～4
[54]张显全,刘忠平.基于格网模型的等高线算法[J].计算机科学,2005,32(9)：199～201
[55]刘凯敏.数字高程建模与数据可视化：[硕士学位论文].中南大学,2007
[56]杨明强,闫继涛.数字化测图中等高线平滑处理方式的比较与分析[J].平顶山工学院学报,2004,13(4)：29～31
[57]马小虎,潘志庚,石教英.基于凹凸顶点判定的简单多边形Delaunay三角剖分[J].计算机辅助设计与图形学学报.1999,11(1)：1-3
[2]李志林,朱庆.数字高程模型[M].武汉：武汉测绘科技大学出版社,2003,5，145～150
[3]Bi Huaxing, Li Xiaoyin, Guo Mengxia, et al. Digital Terrain Analysis Based on DEM[J]. Frontiers of Forestry in China,2006, (1):54～58
[4]张渭军,李永军,刘向阳.数字地面模型中等高线的自动绘制[J].地球科学与环境学报,2004,26(1)：76～78
[5]赵建三.基于格网DEM的自适应等高线内插方法[J].中南工业大学学报(自然科学版),2003,34(3)：315～319
[6]杨道勇,肖云岫.利用三角形网格进行等值线分析与绘制[J].四川气象,2005,(2)：38～39
[7]刘海涛,秦其明.DEM生成等高线图的再研究[J].地图.2001,2：15～18
[8]VAN KREVELD M. Efficient Methods for Isoline Extraction from a TIN. [J]International Journal of GIS.1996,10:523～540
[9]王涛,毋河海,刘纪平.基于区间树索引的等高线提取算法[J].武汉大学学报(信息科学版),2007,32(2)：131～134
[10]王涛,刘纪平,毋河海.基于排序预处理的等高线提取算法[J].测绘学报,2006,35(4)：390-394
[11]Julie Charleux-Demargne, Christian Puech. Quality assessment for drainage networks and watershed boundaries extraction from a digital elevation model (DEM)[J]. Proceedings of the 8th ACM international symposium on Advances in geographic information systems,2000,89～94
[12]宋丽娟,龚晓峰,钟猛.基于网格法的等值线绘制方法[J].现代电子技术,2005,14：65～67
[13]王永会,宋晓宇,栾方军.基于网格的等值线图快速生成算法[J].计算机工程与应用,2001,17：124～125
[14]吴卫华,袁宁.基于格网的等值线生成算法的研究.试验与研究,2003,(4)：27～30
[15]常会,柴华彬,邹友峰.基于搜索圆法的等值线追踪技术[J].测绘科学,2009,34(2)：119～120
[16]高斌,朱景华,徐振宇,等.基于网格拓扑关系追踪的等值线生成方法 [J].2007,24(6)：4-6
[17]顾滨兵,杨兆海,高宇基,等.基于网格序列法和端点量化的等值线生成算法[J].吉林大学学报(信息科学版),2010,28(1)：89～93
[18]刘斌.地形图等高线的自动绘制[J].全国水力水电测绘科技学术交流会,1998,10：79～80
[19]高正夏,吴继敏,康政虹,等.等值线平滑方法简介及效果比较[J].工程地质计算机应用,2002,3(3)：19～20
[20]陈学工,黄晶晶.等高线高程自动标注算法的研究[J].测绘科学,2007,32(4)：101～103
[21]夏金伟,赵东宝.等高线图等高线高程自动标注算法研究[J].地矿测绘,2004,20(2)：18-20
[22]韩丽娜,石昊苏.等值线标注的一种算法探讨.计算机工程与设计[J],2006,(11)：4084～4086
[23]刘冬韡,戴建华,林红,等.基于等值线分类的区域填充算法[J].气象科技,2009.37(5)：597～599
[24]庞世明,蔡玉华,靳文芳.等值线图的彩色填充方法[J].计算机应用,2004,24(1)：60～62
[25]韩丽娜,石昊苏,张群会.基于边界点追踪的等值线图区域填充算法[J].计算机工程与科学,2006,28：66～67
[26]彭革伟,韩家新.等值线图区域填充的快速搜索算法[J].中国科技信息,2006,17：252～253
[27]孙桂茹,马亮,路登平,等.等值线生成和图形填充算法[J].天津大学学报,2000,33(6)：816～818
[28]吴自银,高金耀.一种基于格网的快速等值线充填算法[J].测绘学报,1999,28(4)：350～354
[29]张登荣,刘绍华,毛天露,等.等值线自动建立拓扑关系算法与快速填充应用[J].中国图像图形学报,6(A)：3,264-269
[30]陈树强,陈学工,王丽青.判定检测点是否在多边形内的新方法[J].微电子学与计算机.2006,23(8)：194～195
[31]陈瑞卿,周健,虞烈.一种判断点与多边形关系的快速算法[J].西安交通大学学报.2007,41(1)：59～63
[32]宫晓峰.基于OpenGL的三维GIS地形可视化技术的研究与实现[硕士学位论文].北京：北京邮电大学,2009
[33]Floriani LD, Marzano P, Puppo E. Multiresolution models for topographic surface description[J].The Visual Computer,1996,12 (7):317-345
[34]Groshong R H.3-D Structural Geology:A Practical Guide Io Quantitative Surface and Subsurfaces Map Interpretation[J]. Berlin:Springer,2006
[35]黄晶晶.数字高程模型TIN和等高线建模[硕士学位论文].长沙：中南大学,2007
[36]Su Wei Min, Wu Fan. Research on Constructing Contours from Regular Terrain Grids Containing Invalid Data[J]. Journal of China University of Mining and Technology 2004,14 (2):138～142
[37]李志林,朱庆.数字高程模型[M].武汉：武汉大学出版社,2001
[38]Julie Charleux-Demargne, Christian Puech. Quality assessment for drainage networks and watershed boundaries extraction from a digital elevation model (DEM) [J]. Proceedings of the 8th ACM international symposium on Advances in geographic information systems,2000,89～94
[39]汤国安,刘学军,闾国年.数字高程模型及地学分析的原理与方法[M].北京：科学出版社,2005
[40]武俊红,汪云甲.基于Surfer的煤矿等值线空间插值方法有效性评价[J].中国矿业,2007,16(1)：108～110
[41]于海生.复杂断块油田的等值线插值及绘制新方法研究[硕士学位论文].北京：中国石油勘探开发科学研究院,2001
[42]杨锦,张小望.解析插值法在等值线绘制中的应用[J].勘测科学技术,2008,(3)：55～58
[43]林怡,陈鹰.一种数字高程模型生成系统的研究[J].测绘学院学报,2000,(28)9：187～190
[44]蒋红斐,詹振炎.利用锥构建DTM生成算法研究[J].武汉测绘科技大学学报,2000,(13)4：120～126
[45]武俊红,汪云甲.基于Surfer的煤矿等值线空间插值方法有效性评价[J].中国矿业,2007,16(1)：108～110
[46]TOMATISN, NOURBAKHSH I, SIEGWART R. Hybrid simultaneous localization and map building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003,44 (1):3～14
[47]白世彪,陈哗,王建,等.等值线绘图软件SURFER7.0中九种插值法介绍[J].物探化探计算技术,2002,24(2)：157
[48]冯锦明,赵天保,张英娟.基于台站降水资料对不同空间内插方法的比较[J]. 气候与环境研究,2004,9(2)：261～276
[49]颜辉武,祝国瑞,徐智勇.基于Voronoi图的距离倒数加权法的改进研究[J].武汉大学学报,2004,29(11)：1017～1020
[50]郭尚,苏鸿根.基于距离倒数加权法的等值面绘制简化算法[J].计算机工程与设计,2008,29(5)：1200～1202
[51]Mark de Berg, Otfried cheong, Marc van kreveld,等.计算几何—算法与应用(第二版)[M].邓俊辉,译.北京：清华大学出版社,2005
[52]严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,1997
[53]王家耀,崔铁军,苗国强.数字高程模型及其数据结构[J].海洋测绘,2004,24(3)：1～4
[54]张显全,刘忠平.基于格网模型的等高线算法[J].计算机科学,2005,32(9)：199～201
[55]刘凯敏.数字高程建模与数据可视化：[硕士学位论文].中南大学,2007
[56]杨明强,闫继涛.数字化测图中等高线平滑处理方式的比较与分析[J].平顶山工学院学报,2004,13(4)：29～31
[57]马小虎,潘志庚,石教英.基于凹凸顶点判定的简单多边形Delaunay三角剖分[J].计算机辅助设计与图形学学报.1999,11(1)：1-3