分治插入整合算法ppt课件

1、分治插入整合算法分治插入整合算法 评价一个算法的优劣关键在于其对地形表评价一个算法的优劣关键在于其对地形表达的近似程度即数学精度和时间效率以及达的近似程度即数学精度和时间效率以及其占用系统资源的多少，前面表达的各种其占用系统资源的多少，前面表达的各种算法在这些方面均各有利弊，比如，分治算法在这些方面均各有利弊，比如，分治算法由于其数据的分块处置，大大地减少算法由于其数据的分块处置，大大地减少了每次数据遍历的搜索量，因此其时效性了每次数据遍历的搜索量，因此其时效性非常好，但由于是递归执行，需求较大的非常好，但由于是递归执行，需求较大的内存空间，占用较多的系统资源内存空间，占用较多的系统资源; ;

2、与些相反，与些相反，逐点插入法那么比较容易实现，占用内存逐点插入法那么比较容易实现，占用内存少，但其时效性差。少，但其时效性差。 为此人们也种提出过结合各种算法优点的为此人们也种提出过结合各种算法优点的相关算法，如文献武晓波，王世新，肖相关算法，如文献武晓波，王世新，肖春生春生.Delaunay.Delaunay三角网的生成算法研讨三角网的生成算法研讨J J. .测绘学报测绘学报1999.21999.2提出的合成算法等。提出的合成算法等。在对各种算法深化研讨的根底上，本文提在对各种算法深化研讨的根底上，本文提出并实现了一种在数据分块根底上，逐点出并实现了一种在数据分块根底上，逐点插入的算法，兼

3、顾了分治算法和逐点插入插入的算法，兼顾了分治算法和逐点插入算法的优点，经实验验证，获得了良好的算法的优点，经实验验证，获得了良好的效果，并将此算法命名为分治插入整合算效果，并将此算法命名为分治插入整合算法。法。1算法的根本过程算法的根本过程 一、数据集的分块划分子集一、数据集的分块划分子集 二、各子集二、各子集ViVi中三角网的构建中三角网的构建 三、一切子块的整合三、一切子块的整合一、数据集的分块划分子集一、数据集的分块划分子集 a.数据排序数据排序 根据数据点集根据数据点集V分布的情况对数据排序，分布的情况对数据排序，如以下图，当数据分布的外形为图如以下图，当数据分布的外形为图2. 4中的

4、中的1所示时，将数据按所示时，将数据按Y坐标的升序排序，假坐标的升序排序，假设数据的分布外形如设数据的分布外形如2所示，那么将数据按所示，那么将数据按X坐标的升序排序，以保证在数据分块时块坐标的升序排序，以保证在数据分块时块的外形更接近方形，从而提高分块构网的的外形更接近方形，从而提高分块构网的效率优化次数可更少。效率优化次数可更少。 b.子集子集Vi中数据点的数量确实定及子集中数据点的数量确实定及子集Vi的的划分划分 可以在程序中规定或以人机交互方式确定可以在程序中规定或以人机交互方式确定各子集各子集Vi所含的点数的最大值所含的点数的最大值Pmax和最小和最小值值Pmin,在系统运用在系统运

5、用N 的开方的开方N为总点数为总点数来确定并输入来确定并输入Vi中允许点数的最大中允许点数的最大Pmax和和最小最小Pmin,将数据集将数据集V分成点数近似相等的分成点数近似相等的i个子集个子集Vi i=1, 2,，n。二、各子集二、各子集ViVi中三角网的构建中三角网的构建 1、构建第一个三角形、构建第一个三角形 2、逐点插入生成新的三角形、逐点插入生成新的三角形 3、重生三角形的、重生三角形的LOP优化优化 4、其它子集构建初始三角网、其它子集构建初始三角网 1、构建第一个三角形、构建第一个三角形 任取三点构成第一个三角形不应共线，任取三点构成第一个三角形不应共线，否那么重新取点，顺序记录

6、此三角形的否那么重新取点，顺序记录此三角形的标识号，如标识号，如:T2_ 1，表示该三角形为第二子，表示该三角形为第二子集的第一个三角形，新插入的点为该三角集的第一个三角形，新插入的点为该三角形的第一个点，对其三个顶点按顺时针方形的第一个点，对其三个顶点按顺时针方向记录点号，并顺序记录三个顶点的对边向记录点号，并顺序记录三个顶点的对边所对应的三角形的标识号。所对应的三角形的标识号。 其数据构造如图。图表中的其数据构造如图。图表中的“一表示某点一表示某点对边所对应的三角形不存在，即其对边为对边所对应的三角形不存在，即其对边为子三角网的凸壳边。子三角网的凸壳边。数据的构造共有三个部分。数据的构造共

7、有三个部分。 第一部分记录了采样点的数量第一部分记录了采样点的数量FEATPOINTSFEATPOINTS和各点的点号、平面坐标和各点的点号、平面坐标及高程值。及高程值。 第二部分是三角网的拓扑构造，包含每一三角第二部分是三角网的拓扑构造，包含每一三角形的标识、顺时针组成该三角形的形的标识、顺时针组成该三角形的3 3个顶点点号，个顶点点号，及与各顶点对边相邻三角形的标识号。数据构及与各顶点对边相邻三角形的标识号。数据构造简单，但明晰地记录了三角形的顶点、边以造简单，但明晰地记录了三角形的顶点、边以及与相邻三角形的关系，并隐式地记录了组成及与相邻三角形的关系，并隐式地记录了组成此三角形的各边。经

8、过对各顶点的对边三角形此三角形的各边。经过对各顶点的对边三角形的标识号的记录，完好描画了三角网中三角形的标识号的记录，完好描画了三角网中三角形间的拓扑关系，便于数据处置。间的拓扑关系，便于数据处置。 第三部分记录了一条随机的外凸壳上的边，第三部分记录了一条随机的外凸壳上的边，如如:OUTESTTRI=T2 -6062, 3,:OUTESTTRI=T2 -6062, 3,表示标识号为表示标识号为T2-T2-2606226062的三角形的第三个顶点的对边为外凸壳边。的三角形的第三个顶点的对边为外凸壳边。由于三角形的点号记录顺序均是顺时针的，因此，由于三角形的点号记录顺序均是顺时针的，因此，经过记录

9、凸壳上的一条边就可以找到凸壳上的一切经过记录凸壳上的一条边就可以找到凸壳上的一切边。这样就便于新点的内插和子三角网的合并。边。这样就便于新点的内插和子三角网的合并。 外凸壳上的边的记录便于快速搜索，如不记录，外凸壳上的边的记录便于快速搜索，如不记录，也可经过对三角网进展遍历找出第一个凸壳边，但也可经过对三角网进展遍历找出第一个凸壳边，但显然降低了程序运转的效率。建立初始三角网第显然降低了程序运转的效率。建立初始三角网第一个三角形时，凸壳边记录该三角形的恣意一边。一个三角形时，凸壳边记录该三角形的恣意一边。 2、逐点插入生成新的三角形、逐点插入生成新的三角形 三角形内点的插入三角形内点的插入 三

10、角形外点的插入三角形外点的插入 重生成的三角形与其共边三角形的重生成的三角形与其共边三角形的LOP优化优化 反复以上步骤，直至该子集反复以上步骤，直至该子集Vi中一切的点均中一切的点均插入终了，即构成了该子集插入终了，即构成了该子集Vi的三角网的三角网 外凸壳上通视点的搜索外凸壳上通视点的搜索 三角形内点的插入 在子集中依次取一个新的插入点，首先查找所取的新插入点i所在的三角形。假设i位于一三角形内，那么分别衔接i与此三角形的三顶点将该三角形一分为三如图2. 6所示，标识3个新三角形，并按顺时针方向分别记录各三角形的三顶点的点号;将所在原三角形的拓扑关系传送给新三角形;依次对新三角形作与共边三

11、角形的能够存在的LOP优化;去除三角网中的原三角形。 三角形外点的插入三角形外点的插入 假设假设i i点不在任何三角形内，如图点不在任何三角形内，如图2. 72. 7，那么应先，那么应先按记录的外凸壳上的边，找呈现己构成的部分三按记录的外凸壳上的边，找呈现己构成的部分三角网的外凸壳上和角网的外凸壳上和i i点通视的各点，如图中点通视的各点，如图中a, b, a, b, c, dc, d和和e e点，并分别与点点，并分别与点i i衔接，以构成相应的三衔接，以构成相应的三角形，即角形，即a iba, a icb, a idca iba, a icb, a idc和和a ieda ied，这样，这样

12、能保证所生成的三角网的外壳为凸壳。图中能保证所生成的三角网的外壳为凸壳。图中i i与与f f视为不通视。视为不通视。 重生成的三角形与其共边三角形的重生成的三角形与其共边三角形的LOPLOP优优化化 接着对以对应的原外凸壳边如接着对以对应的原外凸壳边如ba, cb, doba, cb, do和和eded为公共边的各对三角形进展为公共边的各对三角形进展LOPLOP优化以优化以获得最正确外形的三角形。在和的获得最正确外形的三角形。在和的LOPLOP优化过程中，优化会生成新的三角形，新优化过程中，优化会生成新的三角形，新三角形将继续与共边三角形进展三角形将继续与共边三角形进展LOPLOP优化，优化，

13、直到不能再优化为止。直到不能再优化为止。 反复以上步骤，直至该子集反复以上步骤，直至该子集ViVi中一切的中一切的点均插入终了，即构成了该子集点均插入终了，即构成了该子集ViVi的三角的三角网。网。 外凸壳上通视点的搜索外凸壳上通视点的搜索 如前所述，外凸壳边都是顺时针记录的，如前所述，外凸壳边都是顺时针记录的，从图从图2 .72 .7可看出，与外插点可看出，与外插点i i通视的点所生通视的点所生成的新三角形均为顺时针的，如成的新三角形均为顺时针的，如a iba, a a iba, a icb, a iedicb, a ied，断定三角形点序的时针方向，断定三角形点序的时针方向以代数面积计算法

14、确定。以代数面积计算法确定。 三角形的面积为三角形的面积为: : 即当插入点与某边构成的三角形的面积为即当插入点与某边构成的三角形的面积为负时，该边为通视边。相反，那么是不通负时，该边为通视边。相反，那么是不通视边。视边。 而外插点而外插点1 1与不通视的点构成三角形后，为与不通视的点构成三角形后，为逆时针方向的，如逆时针方向的，如a iafa iaf，该三角形不能作，该三角形不能作为新三角形参与到三角网中。为新三角形参与到三角网中。 此时三角形的面积为此时三角形的面积为: : 3、重生三角形的、重生三角形的LOP优化优化 其原理就是根据其原理就是根据D一三角网的性质对具有公共一三角网的性质对

15、具有公共边的三角形组成的四边形进展判别，假设其中边的三角形组成的四边形进展判别，假设其中的某三角形的外接圆包含该四边形的第四个顶的某三角形的外接圆包含该四边形的第四个顶点，那么将该四边形的对角线交换，生成以另点，那么将该四边形的对角线交换，生成以另一条对角线为公共边的两个三角形。此时一定一条对角线为公共边的两个三角形。此时一定满足空圆性质，得到满足空圆性质，得到D一三角形。同时对一三角形。同时对TIN的的数据记录进展更新，增添新的三角形标识号记数据记录进展更新，增添新的三角形标识号记录及其对应的顶点和顶点的对边三角形，删除录及其对应的顶点和顶点的对边三角形，删除被废弃的三角形。被废弃的三角形。

16、 4、其它子集构建初始三角网、其它子集构建初始三角网 反复上述步骤反复上述步骤1,2,3，对各子集构建三角网。，对各子集构建三角网。此时每一三角网均是凸壳的。此时每一三角网均是凸壳的。三、一切子块的整合三、一切子块的整合 1、确定相邻两个子三角网的外凸壳的下底线 如前所述，各子三角网的外壳为凸壳。凸壳上点和边均在TIN的数据构造中按顺时针方向记录，搜索凸壳下底线的过程如下。 设SL, SR分别表示左右两个凸壳。 首先在左凸壳SL上任取一凸壳点，按上述三角形面积断定法找出右凸壳上的第一条通视边的第一个凸壳点。假设无通视边，那么在SL上顺时针取下一点再作搜索判别，直到找到通视边。 以右凸壳SR上刚找到的点仍按面积断定法搜索左凸壳SL上最后一条通视边的第二个凸壳点。 反复以上两个步骤，在SL和SR上循环搜索，直到从SL上的凸壳点不再能找到SR上的通视边，目从SR上的凸壳点也不再能找到SL上的通视边。 此时，衔接在SL和SR上分别找到的最后的凸壳点，所连线即为左右凸壳的下底线。如图2. 10中的ac。 2、相邻两个子三角网的合并 找到左右两个了三角网的下底线后如图ac