等高线生成算法的研究
|
摘要
地形图是用来表示自然或人文现象的各种地图符号，是人们认知世界的一种重要工具。随着测绘事业的发展，一种以数字储存代替纸质储存，由计算机进行控制、管理、显示、必要时可输出到纸介质上的数字地图(也称为电子地图)正在逐渐成为各种自动化系统中的重要组成部分。
在数字地图编辑过程中，经常会碰到等高线短缺的问题，这就需要在已有的等高线间内插出短缺的等高线，通常作业员根据自己的经验，用鼠标描绘出需要内插的等高线。为了满足等高线三维显示的需求，需要等高距不同但彼此相容的等高线。这就需要内插出大量的等高线，这时如果继续用鼠标逐条内插，其工作量可想而知。我们考虑能够用软件自动、有效、精确地实现这一过程，无疑是我们图形矢量化的亮点之一。为此，笔者在葛永慧教授开发的EasyMapRead软件的基础上，分析了构建不规则三角网数字地面模型时用到的主要的Delaunay三角剖分算法，进行了离散点生成三角网并拟合成
太原理工大学硕士研究生学位论文
等高线的工作。顾及地形图矢量化后的编辑以及需适应等高线
的三维显示，本论文实现了由离散数据点直接绘制等高线，并
尝试了等高线的删除与内插。
等高线内插是指在己有等高线的基础上自动内插出若干
条与己知等高线相一致的等高线，等高线的自动内插在地图制
图与出版以及地理信息系统中是很有用的。
Geographical map is a kind of map symbol for showing natural or human phenomena, a kind of tool for people cognizing the world. With the development of surveying, digit-storage instead of paper-storage, computer controlling, managing, showing and digital map outputting to paper mediator when they will be required are the important parts of kinds of automating system.
In the course of digital map editing, we always run into problem of contour line shorting, thus, we should interpolate new contour lines from original ones. Usually draftsman can draw new contour lines by mouse according to one's experience. In order to cater the 3-D showing of contour line, we should generate different contour interval lines and compatible with each others. If we draw them one by one, the large amount of work we should do
is hard to imagine. Without any doubt, it is a bright point in geographical map editing that we start to think drawing them by automatically, effectively and precisely. So the writer bases her tutor's software-EasyMapRead, analyzes a wild variety of Delaunay triangulation algorithm that are used in the creation of DTM based on the triangulate irregular network (TIN), creates triangulation net from discrete points and fits contour lines. Take into account suiting to map editing and 3-D display, the subject realizes direct drawing of contour line from discrete points, tries deleting and interpolating of contour line.
Contour lines interpolating is interpolate new contour lines accord to original ones and agreement to them, it is very useful for contour lines interpolating voluntarily.
在数字地图编辑过程中，经常会碰到等高线短缺的问题，这就需要在已有的等高线间内插出短缺的等高线，通常作业员根据自己的经验，用鼠标描绘出需要内插的等高线。为了满足等高线三维显示的需求，需要等高距不同但彼此相容的等高线。这就需要内插出大量的等高线，这时如果继续用鼠标逐条内插，其工作量可想而知。我们考虑能够用软件自动、有效、精确地实现这一过程，无疑是我们图形矢量化的亮点之一。为此，笔者在葛永慧教授开发的EasyMapRead软件的基础上，分析了构建不规则三角网数字地面模型时用到的主要的Delaunay三角剖分算法，进行了离散点生成三角网并拟合成
太原理工大学硕士研究生学位论文
等高线的工作。顾及地形图矢量化后的编辑以及需适应等高线
的三维显示，本论文实现了由离散数据点直接绘制等高线，并
尝试了等高线的删除与内插。
等高线内插是指在己有等高线的基础上自动内插出若干
条与己知等高线相一致的等高线，等高线的自动内插在地图制
图与出版以及地理信息系统中是很有用的。
Geographical map is a kind of map symbol for showing natural or human phenomena, a kind of tool for people cognizing the world. With the development of surveying, digit-storage instead of paper-storage, computer controlling, managing, showing and digital map outputting to paper mediator when they will be required are the important parts of kinds of automating system.
In the course of digital map editing, we always run into problem of contour line shorting, thus, we should interpolate new contour lines from original ones. Usually draftsman can draw new contour lines by mouse according to one's experience. In order to cater the 3-D showing of contour line, we should generate different contour interval lines and compatible with each others. If we draw them one by one, the large amount of work we should do
is hard to imagine. Without any doubt, it is a bright point in geographical map editing that we start to think drawing them by automatically, effectively and precisely. So the writer bases her tutor's software-EasyMapRead, analyzes a wild variety of Delaunay triangulation algorithm that are used in the creation of DTM based on the triangulate irregular network (TIN), creates triangulation net from discrete points and fits contour lines. Take into account suiting to map editing and 3-D display, the subject realizes direct drawing of contour line from discrete points, tries deleting and interpolating of contour line.
Contour lines interpolating is interpolate new contour lines accord to original ones and agreement to them, it is very useful for contour lines interpolating voluntarily.
引文
【1】 葛晓光，吴道祥，不规则三角网上的等值线索进过程，合肥工业大学学报，第24卷第6期，1145～1148
【2】 杜殿发，王志明，计算机绘制等值图的新方法，石油大学学报，第20卷增刊，122～125
【3】 王晓峻，吴鹏，王志坚，基于三角网的等值线生成及ActiveX实现，长江科学院院报，第18卷第4期，51～53
【4】 张梅华，梁文康，一个三角形网格上等值线图的绘制算法，计算机辅助设计与图形学学报，第9卷第3期，213～217
【5】 曾广鸿，张新长，邓良炳，折线式等值线的曲线化模型探讨，测绘通报，1999年第6期，15～18
【6】 胡卫明，吴兵，凌海滨，地图等高线自动内插算法，计算机学报，第23卷第八期，848～851
【7】 LAI Poh-Chin，黄培之，2D几何图形整体内插的一种方法，计算机学报，第22卷第2期，165～170页
【8】 徐建新，徐地保，段玉清，等高线内插数学模型的探讨，江苏测绘，第23卷，第4期，2000年12月
【9】 乔朝飞，陈军，李志林等，基于图论的等高线空间关系表达，中国矿业大学学报，第32卷，第3期
【10】 蒋红斐，詹振炎，利用三叉树构建三角网数模的生成算法研究，铁路航测，2000年第2期，1～3页
【11】 李军、林宗坚，一种图纸扫描图像新的阈值选取法，数据采集与处理，第12卷第2期，1997
【12】 刘海涛，秦其明，DEM生成等高线图的再研究，计算机与地图
【13】 龚有亮，何玉华，付子傲等，一种实用的等高线内插算法，测绘学院学报，第hh19卷第一期，35～37页
【14】 刘少华，程朋根，陈红华等，Delaunay三角网内插特征点算法研究，华东地质学院学报，2002年9月
【15】 徐庆荣，杜道生，黄伟，费立凡，计算机地图制图原理，武汉市，武汉测绘科技大学出版社，1993年6月
【16】 刘学军，龚健雅，约束数据域的Delaunay三角剖分与修改算法，测绘学报，vol．30 no．1，2001．2
【17】 李志林，朱庆，数字高程模型，武汉市，武汉测绘科技大学出版社，2000
年3月，52～53页
【18】 龚建雅，地理信息系统基础，北京市，科学出版社，2001年
【19】 郝向阳，地图信息识别与提取，北京：测绘出版社，2001
【20】 陈建春，Visual C++开发GIS系统，电子工业出版社，2001年10月
【21】 葛永慧，地形图图像要素分类和图形绘制技术的研究，博士论文，2001
【22】 傅仲良，地形图图纸技术读取的研究，博士论文，1996
【23】 郭虎，地形图扫描图像预处理，硕士论文，2002
【24】 张渝，数字地面模型的建立，硕士论文，2002
【25】 Leila De Floriani, Bianca Falcidieno, George Nagy, and Caterina Pienovi. A hierarchical structure for surface approximation. Comput. & Graphics, 8(2):183-183, 1984.
【26】 hiessen A H. Precipitation Averages for Large Areas, Monthly Weather Review, 1911(39):1082～1084
【27】 elaunay B. Sur la Sphere Vide, Bulletin of the Academy of Sciences of the USSR, Classe des Sciences Mathematiques et Naturelles, 1934(8):793～800
【28】 Franz Aurenhammer, Voronoi diagrams - a survey of a fundamental geometric data structure, ACM Computing Surveys, 23(3):345-406, 1991.
【29】 Rippa, S., Minimal roughness property of the Delaunay triangulation, Computer Aided Geometric Design, 1990, 7, pp. 489-497.
【30】 A. Mirante and N. Weingarten. The radial sweep algorithm for constructing triangulated irregular networks. IEEE Computer Graphics and Applications, 2(3):11-21, 1982
【31】 B.A. Lewis and J.S. Robinson. Triangulation of planar regions with applications. The Computer Journal, 21 (4):324-332, 1978
【32】 D.T. Lee and B.J. Schachter. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer and Information Sciences, 9(3):219-242, 1980.
【33】 Michael J. McCullagh and Charles G. Ross. Delaunay triangulation of a random data set for isarithmic mapping. The Cartographic Journal, 17(2):93-99, 1980.
【34】 Jan Terje Bjφrke. Digital Kartografi. Department of Surveying and Mapping, Norwegian Institute of Technology, University of Trondheim, 1991. Part three.
【35】 Lee, D.T., Lin A.K., Generalized Delaunay triangulation for planar graphs, Discrete and Computational geometry, 1, 1986, pp. 201-217.
【36】 CHEWL P. Constrained Delaunay Triangulation, in Proceedings of Third ACM Symposium on Computional Geometry. Waterloo,1987,216-222
【37】 WU Xiao-bo. A New Study of Delaunay Triangulation Creation. Acta
Geodaectia et Cartographica Sinica, 1999,28(1):28-35.
【38】 Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74-123, 1985.
【39】 Lee D T. Two Algorithms for Constructing a Delaunay Triangulation. Int J of Computer and Information Science, 1980,9(3):219-242
【40】 BOISSINNAT J D. Shape Reconstruction from Planar Sections. Comput Vision Graphics Image Process, 1988,44:1-29.
【41】 PIEGL L A.Algorithm and Data Structure for Triangulation Multiply connected Polygonal Domains Computer and Graphics, 1993, 17(5):563-574.
【42】 FLORIANI L D.An Online Algorithm for Constrained Delaunay Triangulation. CVGIP: Graphic Models and Image Processing, 1992
【43】 SLOAN S W.A Fast Alogrithm for Constructing Dlaunay Triangulation in the Plane. Advanced Engineering Software, 1987,9(1):34-55.
【2】 杜殿发，王志明，计算机绘制等值图的新方法，石油大学学报，第20卷增刊，122～125
【3】 王晓峻，吴鹏，王志坚，基于三角网的等值线生成及ActiveX实现，长江科学院院报，第18卷第4期，51～53
【4】 张梅华，梁文康，一个三角形网格上等值线图的绘制算法，计算机辅助设计与图形学学报，第9卷第3期，213～217
【5】 曾广鸿，张新长，邓良炳，折线式等值线的曲线化模型探讨，测绘通报，1999年第6期，15～18
【6】 胡卫明，吴兵，凌海滨，地图等高线自动内插算法，计算机学报，第23卷第八期，848～851
【7】 LAI Poh-Chin，黄培之，2D几何图形整体内插的一种方法，计算机学报，第22卷第2期，165～170页
【8】 徐建新，徐地保，段玉清，等高线内插数学模型的探讨，江苏测绘，第23卷，第4期，2000年12月
【9】 乔朝飞，陈军，李志林等，基于图论的等高线空间关系表达，中国矿业大学学报，第32卷，第3期
【10】 蒋红斐，詹振炎，利用三叉树构建三角网数模的生成算法研究，铁路航测，2000年第2期，1～3页
【11】 李军、林宗坚，一种图纸扫描图像新的阈值选取法，数据采集与处理，第12卷第2期，1997
【12】 刘海涛，秦其明，DEM生成等高线图的再研究，计算机与地图
【13】 龚有亮，何玉华，付子傲等，一种实用的等高线内插算法，测绘学院学报，第hh19卷第一期，35～37页
【14】 刘少华，程朋根，陈红华等，Delaunay三角网内插特征点算法研究，华东地质学院学报，2002年9月
【15】 徐庆荣，杜道生，黄伟，费立凡，计算机地图制图原理，武汉市，武汉测绘科技大学出版社，1993年6月
【16】 刘学军，龚健雅，约束数据域的Delaunay三角剖分与修改算法，测绘学报，vol．30 no．1，2001．2
【17】 李志林，朱庆，数字高程模型，武汉市，武汉测绘科技大学出版社，2000
年3月，52～53页
【18】 龚建雅，地理信息系统基础，北京市，科学出版社，2001年
【19】 郝向阳，地图信息识别与提取，北京：测绘出版社，2001
【20】 陈建春，Visual C++开发GIS系统，电子工业出版社，2001年10月
【21】 葛永慧，地形图图像要素分类和图形绘制技术的研究，博士论文，2001
【22】 傅仲良，地形图图纸技术读取的研究，博士论文，1996
【23】 郭虎，地形图扫描图像预处理，硕士论文，2002
【24】 张渝，数字地面模型的建立，硕士论文，2002
【25】 Leila De Floriani, Bianca Falcidieno, George Nagy, and Caterina Pienovi. A hierarchical structure for surface approximation. Comput. & Graphics, 8(2):183-183, 1984.
【26】 hiessen A H. Precipitation Averages for Large Areas, Monthly Weather Review, 1911(39):1082～1084
【27】 elaunay B. Sur la Sphere Vide, Bulletin of the Academy of Sciences of the USSR, Classe des Sciences Mathematiques et Naturelles, 1934(8):793～800
【28】 Franz Aurenhammer, Voronoi diagrams - a survey of a fundamental geometric data structure, ACM Computing Surveys, 23(3):345-406, 1991.
【29】 Rippa, S., Minimal roughness property of the Delaunay triangulation, Computer Aided Geometric Design, 1990, 7, pp. 489-497.
【30】 A. Mirante and N. Weingarten. The radial sweep algorithm for constructing triangulated irregular networks. IEEE Computer Graphics and Applications, 2(3):11-21, 1982
【31】 B.A. Lewis and J.S. Robinson. Triangulation of planar regions with applications. The Computer Journal, 21 (4):324-332, 1978
【32】 D.T. Lee and B.J. Schachter. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer and Information Sciences, 9(3):219-242, 1980.
【33】 Michael J. McCullagh and Charles G. Ross. Delaunay triangulation of a random data set for isarithmic mapping. The Cartographic Journal, 17(2):93-99, 1980.
【34】 Jan Terje Bjφrke. Digital Kartografi. Department of Surveying and Mapping, Norwegian Institute of Technology, University of Trondheim, 1991. Part three.
【35】 Lee, D.T., Lin A.K., Generalized Delaunay triangulation for planar graphs, Discrete and Computational geometry, 1, 1986, pp. 201-217.
【36】 CHEWL P. Constrained Delaunay Triangulation, in Proceedings of Third ACM Symposium on Computional Geometry. Waterloo,1987,216-222
【37】 WU Xiao-bo. A New Study of Delaunay Triangulation Creation. Acta
Geodaectia et Cartographica Sinica, 1999,28(1):28-35.
【38】 Leonidas Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4(2):74-123, 1985.
【39】 Lee D T. Two Algorithms for Constructing a Delaunay Triangulation. Int J of Computer and Information Science, 1980,9(3):219-242
【40】 BOISSINNAT J D. Shape Reconstruction from Planar Sections. Comput Vision Graphics Image Process, 1988,44:1-29.
【41】 PIEGL L A.Algorithm and Data Structure for Triangulation Multiply connected Polygonal Domains Computer and Graphics, 1993, 17(5):563-574.
【42】 FLORIANI L D.An Online Algorithm for Constrained Delaunay Triangulation. CVGIP: Graphic Models and Image Processing, 1992
【43】 SLOAN S W.A Fast Alogrithm for Constructing Dlaunay Triangulation in the Plane. Advanced Engineering Software, 1987,9(1):34-55.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |