【《数字地面模型中无约束离散点的Delaunay三角网建立案例分析》2100字（论文）】

数字地面模型中无约束离散点的Delaunay三角网建立案例分析目录TOC\o"1-3"\h\u8711数字地面模型中无约束离散点的Delaunay三角网建立案例分析 1307731.1Delaunay三角网 1218801.1.1Voronoi图 1247591.1.2Delaunay三角网性质 3201181.2经典Delaunay三角网生成算法 4112841.2.1三角网生长法 4236761.2.2分治算法 5302201.2.3逐点插入法 6227061.3建立TIN模型的方法比较 7不规则三角网可以很好的描述地形和高程信息，并且可以避免缓冲区溢出，因此成为一种关键的建模方法。作为一种标准的三角剖分算法，Delaunay三角剖分算法可以尽可能地避开细长的三角形。此外，它可以保证构建的三角网的唯一性，促使许多专家学者将重点放在将Delaunay三角网算法转化为Delaunay三角网算法的科学研究。1.1Delaunay三角网1.1.1Voronoi图Voronoi图，又叫做泰森多边形，由连续的多边形组成，这些多边形之间相邻点之间由其垂直平分线连接而成[18]。1908年，俄国学者G.Voronoi从数学上定义了每个观点所能代表的空间范围，并用Voronoi图在二维平面上表示了它的几何意义：假设P={p1，p2，...，pnd（p，q）=（则任意点pi的Voronoi图定义为Vp（如图3-1所示）：Vp泰勒多边形为点线面之间进行生成，所以需要严格遵循[18]：多边形内通常都有一个生成元；多边形内的点到生成元的距离最短；边界上的点到各此边界点之间的距离相同；泰勒多边形的特性为空间分析和模型提供了一个很好的方法，生成泰勒多边形主要使用矢量法和栅格法[16]。相邻Voronoi多边形是指具有公共边的Voronoi多边形，而Delaunay三角网是全部的Voronoi多边形的生长中心相互连接形成的三角网，它是由互不相同且相互不叠加、相互毗邻的三角形拼合而成，和Voronoi图是相互对偶的[16]。在形成的Delaunay三角网中，所有三角形的外接圆都不含有点集中的其他点，图3-2表示Delaunay三角网和Voronoi图的相互关系，关系图中实线表示Voronoi图，虚线表示Delaunay三角网。图3-2Delaunay三角网和Voronoi图1.1.2Delaunay三角网性质Delaunay三角剖分具有非常关键的特性，即唯一性、空外接圆特性、最大最小内角性以及局部性等[16]，如下：（1）唯一性随机点集的Delaunay三角剖分是唯一存在的，即对于随机点集，无论以哪一点作为起点和终点，最后的Delaunay三角剖分都是唯一存在的，如图3-3所示。图3-3三角剖分图（2）空外接圆性Delaunay三角网中每个三角形的外接圆不包括点集中的所有其他点，这是Delaunay三角网的创建的基本原理，如图3-4所示。图3-4空外接圆（3）最大最小内角性对于不规则三角网，根据两个相邻的三角形形成的凸四边形，最小内部这两个相邻三角形的角度必须大于替换直线后的角度。局部最优法在背景下于1977年由Lawson提出，Lawson提出的局部最优法的根据是通过替换凸四边形的对角线，进而得到三角网。如图所示。图3-5LOP优化（4）局部性在生成三角网的过程中，若对点进行插入或删除等操作，Delaunay三角剖分也随之发生区域性的变化，即点的插入或删除等操作只会对部分区域有损害[16]。1.2经典Delaunay三角网生成算法现今，以生成Delaunay三角网的过程不同为依据，生成三角网的算法主要包括有三角网生长法、分治法及其逐点插入法等。而分治法和逐点插入法以及两种融合算法为当前普遍使用的算法[16]。1.2.1三角网生长法三角网成长法主要是先进行随机选取一个初始点，之后找到最近点，连接作为初始基准线[16]，从该直线找到最近的点从而获得一个初始三角形，之后利用三条边再按照之前的方法找取最近点构成三角形，之后再进行不停重复，直到解析完所有的离散点。三角网生长法比较简单，网络建设的高效率较弱，现在已经很少使用了。如今改进的三角网生长方法都在寻找第三点。图3-6三角网生长算法步骤1.2.2分治算法分治算法是不断的对数据进行对等分割，最终获得的子三角网中点数不大于4之后进行合并获得三角网的一种算法。该算法采用递归来实现，其概念相对简单，运算速度快，所使用的时间基本上与离散点的数量成正比。但是在数据大时需要计算机有足够的内存。[19]。图3-7分割合并算法图解1.2.3逐点插入法Lawson在1977年提出建立一个大的边界多边形或者三角形来容纳所有数据，之后进行逐点插入，利用局部优化进行获得三角网，这种算法叫做逐点插入法。这种算法对空间没有要求，容易实现，但是时间效率比较低。[20]。其步骤如下：建立一个大的多边形，可以将所有的点包含在内；从离散点中选取一点，进行初始三角网的插入，并与三角形顶点相连，构成三个新的小三角形[16]；（3）LOP优化；（4）重复（2）、（3），直至插入完所有离散点。 图3-8包含P的三角形和该三角形的初始三角剖分1．把包含P的三角形的三个邻接三角形T1、T2、T31．把包含P的三角形的三个邻接三角形T1、T2、T3放入堆栈中2．从堆栈中弹出三角形T33．检查P点是否在T3外接圆中，如果在则交换对角线，反之弹出下一个三角形4．如果交换对角线，则把原来与T3相邻的三角形T7、T8压入堆栈5．重复2~4，直到堆栈为空，则P点的插入过程结束图3-9逐点插入法图解1.3建立TIN模型的方法比较上述三种建立TIN模型的方法及的比较见表3-1。表3-1建立TIN模型的方法及比较建模方法方法描述比较分治算法排序数据，分成两个子集后分别建立三角网并合并。算法比较复杂并且对计算机的要求也比较高，较难实现。三角网生长算法先进行随机选取一个初始点，之后找到最近点，连接作为初始基准]，从该直线找到最近的点从而获得一个初始三角形，之后利用三条边再按照之前的方法找取最近点构成三角形，之后再进行不停重复，直到解析完所有的离散点。该算法的大部分时间花费在搜索符合要求的