[文学]DEM的表面建模-2.pptVIP

三 DEM的表面建模 1. Delaunay三角剖分 Delaunay三角剖分的其它算法 其它条件的三角网生成算法 2.格网生成算法简介 3.TIN与Grid比较 1. Delaunay三角剖分算法 渐次插入算法； 分治算法； 三角网生长算法 插入约束线段的算法 凸闭包生成算法 基本思想： 先将数据排序，分成互不相交的子集； 将每一子集建立三角网后，将子集合并生成最终的狄洛尼三角网； 设数据集V中含N个平面互不重叠的数据点，则： 1.将V按升序排列使(xi, yi) (xi+1, yi+1), 成立条件：(xi ≤xi+1且yi yi+1) ； 2.将V分为大小相等的两部分VL和VR，VL包含数据前一半点，VR包含剩余的点； 3.分别建立两部分数据的Delaunay三角网，并应用局部优化准则进行优化； 4.计算每一半数据的凸闭包，有哪些信誉好的足球投注网站上面部分与下面部分的公共切线（最终三角网的一部分）； 5.从下面的公切线开始，沿相邻边直至最上面的公共切线将两个三角网合并，合并过程中同时进行优化； 6.重复以上2-5直到三角网建立完毕。 分治算法 三角形生长算法 算法过程如下： 在数据集中任取一点，查找距离此点最近的点，相连后作为初始基线； 在初始基线右边应用Delaunay法则有哪些信誉好的足球投注网站第三点； 生成Delaunay三角形，并以该三角形的两条新边作为新的基线； 重复前面过程直至所有基线处理完毕； 这种算法大量的时间花费在符合要求的邻域点的有哪些信誉好的足球投注网站方面，为了减少有哪些信誉好的足球投注网站时间，许多学者提出了许多不同的方法，如将数据分块并排列，以外接圆的方式限定其有哪些信誉好的足球投注网站范围。 三角形生长算法 径向扫描算法： 查找离数据重心最近的点作为起始点； 计算中心点与所有其它点的距离和方位； 根据方位、距离等将所有其他点按升序排列； 径向扫描数据点，将中心点与径向点相连，连接相邻线段任意两连续端点，生成辐射状三角形； 由里向外，将辐射状三角形边界上的点连接，填充边界上的凹孔。 重复以上两步，直至数据的边界。 通过检查由一对相邻三角形形成的四边形两对角线的长度，从外部边界上的三角形开始由外向里顺序优化三角网 插入约束线段的算法 带约束条件的狄洛尼法则： 只有当三角形外接圆内不包含任何其他点，且其三个顶点相互可视时，此三角形才是一个带约束条件的狄洛尼三角形； 插入约束线段的算法 凸闭包(convex hull)生成算法 上面提到的算法都没有考虑当外围约束边界加入到三角网中时对三角网进行边界裁剪，因此这些算法对带约束边界的TIN构建来说是不完整的。边界裁剪或多边形裁剪对那种在限定区域内应避免等高线内插的应用是必须的，也是非常关键的。下面将给出一个同时处理平面点和限制条件，既能进行三角网构建也能进行边界剪切的完整算法。 完整的凸闭包插入算法 凸闭包插入算法包括如下几个步骤： ①将数据点分为N／K个块，也即N／K个等边的行与列段。此处K是每一块中点的平均数量，缺省值为4；（数据的初始划分） ②确定每一分块的凸闭包（凸闭包的计算）； ③应用狄洛尼法则建立凸闭包的狄洛尼三角网（凸闭包三角网）； ④反复插入不在凸闭包中的其他点，更新已有三角网（其他数据点的插入）； ⑤反复插入新的约束线段，更新已有三角网（约束线段的插入）； ⑥删除所有内部外围边界或外部外围边界以外的三角形（外围边界裁剪）。 （1）数据的初始划分 数据分块是为了加速邻域点有哪些信誉好的足球投注网站，提高算法效率； 目前在Voronoi和Delaunay 几何算法中广泛采用分块的方法； 分块一般采用二维空间的排序方法，一般采用递归排序法； （2）凸闭包的计算 平面点凸闭包的定义是包含这些平面点的最小凸多边形。 分块数据凸闭包的计算： ①搜寻分别对应x-y，x+y最大值及x-y，x+y最小值的各两个点。这些点为凸闭包的顶点，且总是位于数据集的四个角上，如右图（3-3-10(a)中的点7．9，12，6所示）。 ②将这些点以逆时针方向存储于循环链表中。 ③对链表中的点I及其后续点J调用递归子算法Convex(I，J)，以有哪些信誉好的足球投注网站线段IJ右边凸闭包上的所有点。 （2）凸闭包的计算 递归于算法Convex(I,J)： ①检查数据块中位于线段IJ上及其右边的所有点，计算对IJ有最大偏移量的点K，对IJ右边的点赋正的偏移值，IJ上的点赋0值，IJ左边的点赋负的值。 ②检测最大偏移值的符号： 如果值为正，将K插入到链表位于I与J之间的位置，继续调用函数Convex（I,K）和Convex(K，J)； 如果值为0，且K位于I，J之间，则将K插入到链表中I，J之间，调用函数Convex（I,K）和Convex(K，J)； 否则，终止对Convex函数的调用 （2）凸闭包的计算 （3）生成凸闭包三角网 假设凸闭包顶点