基于离散点生成等高线图算法的研究与实现

发布时间：2018-03-26 02:49

本文选题：数字高程模型　切入点：离散点　出处：《山西农业大学》2014年硕士论文

【摘要】：随着计算机软硬件技术发展,从上世纪50年代末至今,数字高程模型构建算法一直是地学经典研究领域之一,经过诸多学者们的不断努力,格网模型、不规则三角网模型、等高线模型等一系列成熟的模型应运而生,在模型构建方面,也产生了一些比较成熟的思想。诸多数字高程模型(DEM)中以TIN较为常用,因此其生成的相关算法一直备受关注。本文对传统不规则三角网生成算法和基于DTIN追踪生成等值线原理进行概述,对它们主要特点进行分析,结合传统方法对整个过程进行研究。算法实现涉及四个方面：离散点三角形剖分建立不规则三角网(D-TIN),基于D-TIN内插生成等值点集合,开闭两类等高线同时绘制,等值线适度光滑和标注。关于离散点剖分生成D-TIN的过程,通过对传统方法的对比,采用了一种相对实用的三角网生长算法,它以三角网生成的一般算法为基础,对于生长算法来说减少最邻近点查找次数、降低计算复杂度是两个主要的改进方向,本生长算法扩展的内容是多边形,而不是三角形,但就三角形而言,每个三角形仅有两条边进行拓展,而不是三条边,在以基线为基础的最邻近点判断上,进行细化,将离散点以基线(有向线段)为分界分为左右两个点集(刚好落在直线上的离散点与基线无法构成三角形,所以不考虑),使用所需要的点集进行判断,一定程度减少了最邻近点判断次数,只用判断夹角是否最大,不用判断是否位于左侧(右侧),以上是对一般算法的较大改良。值得一提的是在D-TIN数据结构设计上,吸收传统数据结构,以ArcEngine提供的PointClass、LineClass两个类为基础补充一些新属性,分别自定义相应的CoordinatePoint、Edge、Triangle类,提出新的储存点、边线的新结构,更加有利于等值点的计算和后续等高线的追踪。传统等高线追踪过程是分开等高线和闭等高线分别进行的,本文对等值点计算和等高线追踪模式进行了新的尝试,首先进行等值点的计算,将计算结果存储到一个集合中,然后解析等值点集合,同时进行开闭等高线追踪(等高线采用ArcEngine提供的PolylineClass类对象进行渲染)。采用PolylineClass类的Smooth函数对等高线进行光滑,该方式简便快捷,可以直接将组成等高线的折线段集按照对应参数转换成相对平滑的贝塞尔曲线。最后使用ArcEngine提供的方法对等高线图层进行标注。经过测试,离散点生成D-TIN的实用算法在一定程度上提高了构网速度,具有很强实用性;同时也对新追踪模式进行验证,结果也是可靠的。
[Abstract]:With the development of computer software and hardware technology, from the late 1950s to the present, digital elevation model construction algorithm has been one of the classical geoscience research fields. Through the continuous efforts of many scholars, grid model, irregular triangular network model, A series of mature models, such as contour models, emerge as the times require, and some mature ideas have been produced in the construction of models. In many digital elevation models, TIN is commonly used, so the related algorithms have been paid more attention to. In this paper, the traditional algorithm of irregular triangulation generation and the principle of generating contours based on DTIN tracing are summarized, and their main characteristics are analyzed. Combined with the traditional method, the whole process is studied. The algorithm involves four aspects: establishing irregular triangular mesh by dividing discrete points into triangles, generating equivalent points set based on D-TIN interpolation, drawing two kinds of contour lines simultaneously. On the process of generating D-TIN by dividing discrete points, by comparing the traditional methods, a relatively practical algorithm of triangulation is adopted, which is based on the general algorithm of generating triangulation. For the growth algorithm, reducing the number of nearest neighbor lookups and reducing the computational complexity are the two main directions of improvement. The extension of this algorithm is polygon, not triangle, but for triangles, Each triangle has only two sides to expand, rather than three, to refine the judgment of the nearest point based on the baseline. The discrete points are divided into two sets of left and right points by the boundary of the baseline (the directed line segment). The discrete points that fall on the line and the baseline can not form a triangle, so the necessary set of points is used to judge the discrete points without considering the point set. To some extent, the number of nearest points is reduced, only the maximum angle is judged, and the left side is not determined (right side, above is a great improvement on the general algorithm. It is worth mentioning in the design of D-TIN data structure. Absorbing the traditional data structure and adding some new attributes based on the two classes of Point Class LineClass provided by ArcEngine, the corresponding coordinate Point Edge-Triangle class is defined, and a new storage point and a new structure of edge line are proposed. The traditional contour tracing process is carried out separately from the contour line and the closed contour line. In this paper, a new attempt has been made to calculate the equivalent point and track the contour line. First, the equivalent points are calculated, the results are stored in a set, and then the set of equivalent points is analyzed. At the same time, the contour is traced (the contour is rendered by PolylineClass object provided by ArcEngine. The contour is smoothed by the Smooth function of PolylineClass class. This method is simple and fast. The curve set composed of contour line can be directly converted into a relatively smooth Bezier curve according to the corresponding parameters. Finally, the contour layer can be annotated by using the method provided by ArcEngine. The test results show that the practical algorithm for generating D-TIN from discrete points improves the speed of network construction to a certain extent and has strong practicability. The new tracing mode is also verified and the results are reliable.
【学位授予单位】：山西农业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：P208

【参考文献】