分治插入整合算法课件

1、分治插入整合算法 评价一个算法的优劣关键在于其对地形表达的近似程度即数学精度和时间效率以及其占用系统资源的多少，前面叙述的各种算法在这些方面均各有利弊，比如，分治算法由于其数据的分块处理，大大地减少了每次数据遍历的搜索量，因而其时效性非常好，但由于是递归执行，需要较大的内存空间，占用较多的系统资源;与些相反，逐点插入法则比较容易实现，占用内存少，但其时效性差。为此人们也种提出过结合各种算法优点的相关算法，如文献武晓波，王世新，肖春生.Delaunay三角网的生成算法研究(J).测绘学报1999.2提出的合成算法等。在对各种算法深入研究的基础上，本文提出并实现了一种在数据分块基础上，逐点插入的算

2、法，兼顾了分治算法和逐点插入算法的长处，经实验验证，取得了良好的效果，并将此算法命名为分治插入整合算法。1算法的基本过程一、数据集的分块(划分子集) 二、各子集Vi中三角网的构建三、所有子块的整合b.子集Vi中数据点的数量的确定及子集Vi的划分可以在程序中规定或以人机交互方式确定各子集Vi所含的点数的最大值Pmax和最小值Pmin,在系统应用N 的开方(N为总点数)来确定并输入Vi中允许点数的最大Pmax和最小Pmin,将数据集V分成点数近似相等的i个子集Vi (i=1, 2,，n)。二、各子集Vi中三角网的构建1、构建第一个三角形2、逐点插入生成新的三角形3、新生三角形的LOP优化4、其它子

3、集构建初始三角网其数据结构如图。图表中的“一”表示某点对边所对应的三角形不存在，即其对边为子三角网的凸壳边。数据的结构共有三个部分。 第一部分记录了采样点的数量(FEATPOINTS)和各点的点号、平面坐标及高程值。 第二部分是三角网的拓扑结构，包含每一三角形的标识、顺时针组成该三角形的3个顶点点号，及与各顶点对边相邻三角形的标识号。数据结构简单，但清晰地记录了三角形的顶点、边以及与相邻三角形的关系，并隐式地记录了组成此三角形的各边。通过对各顶点的对边三角形的标识号的记录，完整描述了三角网中三角形间的拓扑关系，便于数据处理。第三部分记录了一条(随机的)外凸壳上的边，如:OUTESTTRI=T2

4、 -6062, 3,表示标识号为T2-26062的三角形的第三个顶点的对边为外凸壳边。由于三角形的点号记录顺序均是顺时针的，因此，通过记录凸壳上的一条边就可以找到凸壳上的所有边。这样就便于新点的内插和子三角网的合并。 外凸壳上的边的记录便于快速搜索，如不记录，也可通过对三角网进行遍历找出第一个凸壳边，但显然降低了程序运行的效率。建立初始三角网(第一个三角形)时，凸壳边记录该三角形的任意一边。2、逐点插入生成新的三角形三角形内点的插入三角形外点的插入新生成的三角形与其共边三角形的LOP优化重复以上步骤，直至该子集Vi中所有的点均插入完毕，即构成了该子集Vi的三角网外凸壳上通视点的搜索 三角形内点

5、的插入 在子集中依次取一个新的插入点，首先查找所取的新插入点i所在的三角形。如果i位于一三角形内，则分别连接i与此三角形的三顶点将该三角形一分为三(如图2. 6所示)，标识3个新三角形，并按顺时针方向分别记录各三角形的三顶点的点号;将所在原三角形的拓扑关系传递给新三角形;依次对新三角形作与共边三角形的可能存在的LOP优化;去除三角网中的原三角形。新生成的三角形与其共边三角形的LOP优化接着对以对应的原外凸壳边如ba, cb, do和ed为公共边的各对三角形进行LOP优化以获得最佳形状的三角形。在和的LOP优化过程中，优化会生成新的三角形，新三角形将继续与共边三角形进行LOP优化，直到不能再优化

6、为止。重复以上步骤，直至该子集Vi中所有的点均插入完毕，即构成了该子集Vi的三角网。外凸壳上通视点的搜索如前所述，外凸壳边都是顺时针记录的，从图2 .7可看出，与外插点i通视的点所生成的新三角形均为顺时针的，如a iba, a icb, a ied，判定三角形点序的时针方向以代数面积计算法确定。而外插点1与不通视的点构成三角形后，为逆时针方向的，如a iaf，该三角形不能作为新三角形加入到三角网中。 此时三角形的面积为:3、新生三角形的LOP优化其原理就是根据D一三角网的性质对具有公共边的三角形组成的四边形进行判别，如果其中的某三角形的外接圆包含该四边形的第四个顶点，则将该四边形的对角线交换，

7、生成以另一条对角线为公共边的两个三角形。此时一定满足空圆性质，得到D一三角形。同时对TIN的数据记录进行更新，增添新的三角形标识号记录及其对应的顶点和顶点的对边三角形，删除被废弃的三角形。4、其它子集构建初始三角网重复上述步骤1,2,3，对各子集构建三角网。此时每一三角网均是凸壳的。三、所有子块的整合1、确定相邻两个子三角网的外凸壳的下底线 如前所述，各子三角网的外壳为凸壳。凸壳上点和边均在TIN的数据结构中按顺时针方向记录，搜索凸壳下底线的过程如下。 设SL, SR分别表示左右两个凸壳。 首先在左凸壳SL上任取一凸壳点，按上述三角形面积判定法找出右凸壳上的第一条通视边的第一个凸壳点。若无通视

8、边，则在SL上顺时针取下一点再作搜索判断，直到找到通视边。 以右凸壳SR上刚找到的点仍按面积判定法搜索左凸壳SL上最后一条通视边的第二个凸壳点。 重复以上两个步骤，在SL和SR上循环搜索，直到从SL上的凸壳点不再能找到SR上的通视边，目从SR上的凸壳点也不再能找到SL上的通视边。 此时，连接在SL和SR上分别找到的最后的凸壳点，所连线即为左右凸壳的下底线。如图2. 10中的ac。2、相邻两个子三角网的合并 找到左右两个了三角网的下底线后如图(ac)中的，就可从下底线ac开始向上分别在SL上找到a的上一个凸壳点b，在SR上找到c的下一个凸壳点d。对四边形acdb通过LOP优化新生两个三角形 abc和bdc。 将