5TIN表面建模

第五讲、TIN表面建模方法主要内容TIN-地形表面重建原理与方法TIN-地形表面重建的个性问题二、TIN-地形表面重建原理与方法TIN-不规则三角网的主要概念TIN建模方法的分类和特点散点的无约束TIN建模方法基于等高线的TIN建模方法散点的约束TIN建模方法基于规则网的TIN建模方法不规则三角网建模概述数字地形建模中,不规则三角网(TIN-TriangulatedIrregularNetwork)通过用一系列互不交叉、互不重叠的连接在一起的三角面来逼近地形表面。TIN模型的优点是它能以不同层次的分辨率来描述地形表面。与格网数据模型相比,TIN模型在某一特定分辨率下能用更少的空间和时间更精确地表示更加复杂的表面，特别当地形包含有大量特征如断裂线、构造线时,TIN模型能更好地顾及这些特征从而能更精确合理地表达地表形态，也即三角网模型具有精度高、速度快、效率高和容易处理断裂线和地物等特点。在所有可能的三角网中,Delaunay三角网在地形拟合方面表现最为出色,因此常常被用于TIN的生成。当不相交的断裂线等被作为预先定义的限制条件作用于TIN的生成当中时,则必须考虑带约束条件的D_三角网。TIN的基本内涵：Triangulated：离散数据的三角化过程，TIN的建立过程;Irregular：用于构建TIN的采样点的分布形式不规则性；Network：互不交叉、互不重叠连接在一起的三角形网。TIN的基本元素与类型TIN的基本元素：12345T1T2T3T4T5E1E2E3E4E10E9E7E8E6E56结点（Nodes）边（Edges）三角形（Triangles）拓扑关系（Topology）TIN的类型：无约束TIN：数据点不存在任何关系约束TIN：部分数据点间存在联系，一般通过特征线（边界、内部特征线)TIN的体系构成三角形划分准则地形数据TIN模型算法与程序数据组织与结构TIN存储与组织结构：TIN是一典型的矢量数据结构，通过节点、三角形边和三角形面间的关系显示或隐式表达地形散点的拓扑关系，要求高效的TIN存储与组织结构。TIN的三角形划分准则：TIN模型中三角形的几何形状直接决定TIN的应用质量。考虑地形的各向异性和空间的自相关性，加之实践证明：知道狭长的三角形的插值精度较之规则的三角形可信度要低；要求TIN中的三角形尽量接近正三角形、最近邻的点连接成三角形、三角形唯一。三角化算法与程序：前两者必须有高效的三角化算法与程序来实现。算法的作用由其本身的性能和实现它的程序质量决定；而程序的性能依赖算法的原理。空外接圆准则：在任意一个三角形的外接圆范围内不包含点集M中的任何其他点。最大最小角准则：TIN中两个相邻三角形形成的凸四边形中，这两个三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角。TIN的三角剖分准则（a）（b）（c）（d）（e）（f）（h）(a/b)、空外接圆准则；(c)、最大最小角准则;(d)、最短距离和准则；(e)、张角最大准则；(f)、面积比准则；(g)、对角线准则；TIN的三角剖分准则（a）（b）（c）（d）（e）（f）（h）(a/b)、空外接圆准则；(c)、最大最小角准则;(d)、最短距离和准则；(e)、张角最大准则；(f)、面积比准则；(g)、对角线准则；最短距离和准则：最短距离和就是指一点到基边两端的距离和为最小。张角最大准则：一点到基边的张角为最大。TIN的三角剖分准则（a）（b）（c）（d）（e）（f）（h）(a/b)、空外接圆准则；(c)、最大最小角准则;(d)、最短距离和准则；(e)、张角最大准则；(f)、面积比准则；(g)、对角线准则；面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。对角线准则：两个三角形组成的凸四边形的两条对角线之比，比值限定值须给定，即当计算值超过限定值才进行优化。空外接圆准则、最大最小角准则及张角最大准则是等价的，其余的则不然。三角形准则是建立三角形网络的原则，应用不同的准则将会得到不同的三角形网络。建模应该从同一原则开始，尽量使之形成唯一三角网，也就是要求：在同一准则下由不同的位置开始建立三角形网络，其最终的形状和结构应是相同的。（a）（b）（c）（d）（e）（f）（h）(a/b)、空外接圆准则；(c)、最大最小角准则;(d)、最短距离和准则；(e)、张角最大准则；(f)、面积比准则；(g)、对角线准则；TIN的三角剖分准则Delaunary三角网（简称D_三角网）Delaunary三角网（简称D_三角网）D_三角网为相互邻接且互不重叠的三角形的集合,每一三角形的外接圆内不包含其他的点（由空外接圆准则、最大最小角准则及张角最大准则形成的三角网都是D_三角网）。形成D_三角网的LOP法则：LOP是Lawson在1977年提出的D_三角网形成局部优化过程－－LocalOptimalProcedure。LOP的基本思想是：应用D_三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断，如其中一个三角形的外接圆中含有另外一个顶点，则交换四边形的对角线。空外接圆特性最大最小角特性祥解D_三角网LOP准则(1)空外接圆特性(Circle准则)：在任意一个三角形的外接圆范围内不包含点集M中的任何其他点。（a）在三角形内（c）在三角形外接圆上(按最小边长标准判断对角线13更为可取)（b）在三角形外接圆内（d）在外接圆外祥解D_三角网LOP准则(2)最大最小角特性：在TIN中的两个相邻三角形形成的凸四边形中，这两个三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角。局部最优方法(LOP--LocalOptimizationProcedure)：交换凸四边形的对角线，可获得等角性最好的三角网。(a)新点插入p(b)对角线交换(c)结果三角网2.2、TIN建模方法的分类和特点TIN算法类型不规则数据分布规则数据分布沿等高线分布数据VIPs算法、循环迭代算法层次三角形算法特征线算法探测优化算法辐射扫描算法、模拟退火算法形态算法DT三角剖分直接DT间接DT分割合并算法逐点插入法三角形增长法基本思路：根据随机分布的原始高程点建立连续覆盖整个研究地区的不规则D_三角网(D_TIN)。分类：1)、分割合并算法2)、三角网生长算法3)、逐点插入算法根本问题：确定哪三个数据点构成一个三角形，即自动联结三角网。2.3、散点的无约束TIN建模方法2.3.1、D_三角网生成示例:分割合并算法分割合并算法的基本思想采用分而治之策略，将复杂问题简单化：先将数据点分割成易于三角化的点子集（如每子集3、4个点），后对每个子集分别三角化，并由LOP优化成D_三角网；之后对每个子集的三角网进行合并，形成最终的D_三角网。分割合并三角化算法－Divide&Conquerdelaunaytriangulationalgorithm.2.3.1、D_三角网生成示例:分割合并算法分割合并算法的：S1将数据集以横坐标为主、纵坐标为辅按升序排序。S2如数据集中点数大于阀值，则继续将数据集化为点个数近似相等的两个子集，并对每个子集做如下工作：①获取每子集的凸壳；②以凸壳为数据边界进行三角化，并用LOP优化成D三角网；③找出连接左右子集两个凸壳的底线和顶线；④由底线到顶线合并两个三角网。S3如数据集中点数不大于阀值，则直接输出三角剖分结果。祥解：数据点集采用递归分割快速排序法；子集凸壳的生成可采用格雷厄姆算法（见后）；子集三角化可采用任意方法，如子集最小到3或4个点则可直接三角剖分之；子网合并则需先找出左右子集凸壳的底线和顶线（算法见后），然后逐步合并三角剖分得到最终D三角网。凸壳生成算法凸壳生成的格雷厄姆算法：凸壳的定义：凸壳是数据点的自然极限边界，为包含所有数据点的最小凸多边形，连接任意两点的线段完全位于该凸多边形中，同时其区域面积达到最小值。S1找到点集中纵坐标最小的点P1S2将P1与其它点用线段连接，并计算这些线段的水平夹角S3按夹角大小对数据点排序；如夹角相同，则按距离排序，得到P1，P2，…，Pn.S4依次连接点，得到一多边形。循环删除多边形的非凸顶点得到点集的凸壳。2.3.1、D_三角网生成示例:分割合并算法两子网底线、顶线的查找两子网合并示意图2.3.2、三角网生长算法基本思路：先找出点集中相距最短的两点连接成为一条Delaunay边，然后按D-三角网的判别法则找出包含此边的D-三角形的另一端点，依次处理所有新生成的边，直至最终完成。基本步骤：S1以任一点为起始点（一般位于数据点几何中心附近）；S2找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线，按D-三角网的判别法则（即它的两个基本性质），找出与基线构成D-三角形的第三点；S3基线的两个端点与第三点相连，成为新的基线；S4迭代以上两步直至所有基线都被处理。2.3.3、逐点插入算法动态的构网过程:先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为D-三角网。1）、定义一个包含所有数据点的初始多边形(扩展三角形或外凸壳)；2）、在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点都被处理：a)、插入一个数据点P，在三角网中找出包含P的三角形t，把P与t的三个顶点相连，生成三个新的三角形（存在P在三角形顶点或边上等情况）；b)、用LOP算法优化三角网。3)、可能的外围三角形处理。基本思路：基本步骤：2.3.3、逐点插入算法初始包容多边形：点的插入与LOP处理：散点无约束TIN建模算法性能比较O(N2)O(N3/2)Macedonio和Pareschi(1991)O(N2)O(N3/2)Lee和Schachlter（1980）O(N2)O(N3/2)Watson（1982）O(N2)O(N3/2)Sloan（1987）O(N2)O(N5/4)Bowyer（1981）O(N2)O(N4/3)Lawson（1977）O(N2)O(N3/2)Mirante和Weigarten（1982）O(N2)O(N3/2)MaCullagh和Ross（1980）O(N2)O(N3/2)Brassel和Reif（1979）O(N2)O(N3/2)Green和Sibson（1978）O(NlgN)O(NlgN)Chew（1989）O(NlgN)O(NlglgN)Dwyer（1987）O(NlgN)O(NlgN)Lee和Schachlter（1980）O(N2)O(NlgN)Lewis和Robinson（1978）最坏情况一般情况算法分割合并算法逐点插入法三角形增长法任取一个点(设为O点)为基准点，计算其余点和之连线的方向，以方向角的大小进行排序；连接O点和其它点，并连接相邻点，形成最初扇形三角网；从扇形边的任一点开始，以逆时针进行凹边连接，如ｐ为当前点，沿逆时针方向搜索点ｓ和再下一个点ｑ，如ｑ在ps前进方向的左侧，当前点改为ｓ，从ｓ点继续搜索；如果ｑ在ps前进方向的右侧，则连接pq，生成一新三角形，再往下搜索，ｒ点在pq的右侧，连接pr，又生成一个三角形，下一个点ｔ在pr的左侧，当前点改为ｒ;从ｒ点继续搜索，直到把外边界变成凸多边形为止；利用LOP优化，得到D_三角网。2.3.4、DT生成的其它方法辐射扫描算法2.4、约束D_三角网建模方法尽管D_三角形构网的方法很多，满足最小角为最大的原则，可尽可能避免狭长三角形的出现。但Delaunay构网是对离散点集凸包的三角化，故在实际应用于DTM时会遇到以下几个须解决的问题：在DTM中有一些网格必须经过的特征线，如山脊线、断裂线、湖泊边缘线等；欲三角化的点集范围是非凸区域，甚至存在内环。约束D_三角网建模的目标T1T2为特征边，(a)为重构前三角化结果,(b)为重构后的三角化结果全局优化构网后,可能会有跨越内外边界、特征约束线等的非法三角形,必须对这些三角形进行约束处理。经处理后，数据点的内外边界和特征约束线中的每一个边（段）都应成为最终三角化结果中三角形的一条边。约束DT的三角化准则带约束条件的D_法则带约束条件的LawsonLOP交换只有当三角形外接圆内不包含任何其他点，且其三个顶点相互可视时，此三角形才是一个带约束条件的D_三角形。只有在满足带约束条件的D_法则的条件下,由两相邻三角形组成的凸四边形的局部最佳对角线才被选取。对数据点及作为约束条件的断裂线,可视图由互相可视的任意两点连接而成。在可视图中,除在断裂线的端点处外,连接线与任一断裂线都不相交。约束TIN--ConstrainedDelaunayTriangulation,简为CDT.带约束条件的D_三角网准则图示插入约束线段ab和bc后带约束条件的LawsonLOP交换的完成(a)新点p插入(b)对角线交换(c)结果三角网CDT构造算法约束图法分割-合并算法加密算法Shell三角化法两步法2.4.2、约束DTIN建模的两步法(1)是目前采用最多的CDT构建方法：先构建无约束三角网，后引入约束线段（调整过程）。Sloan采用连续的对角线交换法实现约束线段的嵌入；Floriani的算法则采用简单多边形D三角化的方式实现之。约束三角网的对角线交换迭代思想：基本术语：影响域：约束边所经三角形构成的区域；对角线：影响域内每一条边；起始点：约束边的一端点；目标点：约束边的另一端点；目标：从起始点出发，按照一定的规则逐步交换对角线，最终使起始点和目标点相连。基本思路：从起始点出发，对遇到的每条对角线的可交换性进行判断，可交换就交换，不可交换就判断下一条，到达最后一条对角线后，第一轮交换结束。然后从头再来，开始下一轮，直到约束边的加入。2.4.2、约束DTIN建模的两步法(2)约束三角网的对角线交换迭代算法步骤：S1形成初始D_三角网（可或不含约束线段的顶点，但有不同处理）。S2对每一约束线段，检查是否已是三角形的边；是则检查下一约束线段，否则找出与该约束线段相交的所有三角形边，存入相交边表中。S3交换相交边①如共用相交边的两三角形构不成严格的凸四边形，则该边仍放回相交边表中②构成严格的凸四边形，则交换对角线；检查新的对角线是否与当前约束线段相交，相交则放入相交边表中；不相交则放入不相交边表中；③对不相交边表中每条边进行局部三角网优化处理。2.4.2、约束DTIN建模的两步法(3)约束三角网的对角线交换迭代算法步骤：S1形成初始D_三角网（可或不含约束线段的顶点，但有不同处理）。S2对每一约束线段，检查是否已是三角形的边；是则检查下一约束线段，否则找出与该约束线段相交的所有三角形边，存入相交边表中。S3交换相交边①如共用相交边的两三角形构不成严格的凸四边形，则该边仍放回相交边表中②构成严格的凸四边形，则交换对角线；检查新的对角线是否与当前约束线段相交，相交则放入相交边表中；不相交则放入不相交边表中；③对不相交边表中每条边进行局部三角网优化处理。多对角线交换循环算法实例2.4.3、特征线的增点约束处理法首先，所有要删的线段都将被测试，看其中是否存在特征线，如果存在，则这条特征线将被对半划分，它的中点被插入DT网格，以图为例，若P2P3为特征线，其中点Q1将作为额外的附加点插入网格，由于P2P3先已被包含，故P2Q1和Q1P3必被包含，勿须检验。处理完所有的被删特征线后，回到原先插入Q1的现场，接着处理特征线C1C2。（a）用Q1对半划分特征线C1C2（b）特征线C1Q1被包含（c）用Q2对半划分Q1C2（d)最后的处理结果，其中我们假定P2P3为特征约束。2.4.4、边界的约束处理法对多边形边界来说，无论边界是外部还是内部，只要它们的边界线段存在于DT网格，则即使违反了圆规则，也勿需在其上增加新的附加点。ABCDEF为边界，CD段违反圆规则，即△CDE的外接圆包围了B点，但我们既不能取BE连接，也无必要在CD上插点。2.5、根据等高线生成三角网（1）等高线离散点直接生成TIN：直接将等高线上的点离散化,然后采用上面所讲的从不规则点生成TIN。(a)三角形与等高线相交－－三角形穿越等高线(b)三角形的三个顶点都位于同一条等高线上－－平高三角形两种无效三角形情况：2.5、根据等高线生成三角网（2）将等高线作为特征线的方法：将每一条等高线当做断裂线或结构线,并且规定在这些线上不能有三角形跨越－－避免三角形穿越等高线。自动增加特征点及优化TIN的方法：将等高线离散化建立TIN,但采用增加特征点的方式来消除TIN中的“平高三角形”,并使用优化TIN的方式来消除不合理的三角形比如三角形与等高线相交等;另外对TIN中的三角形进行处理以使得TIN更接近理想化的情况。使用手工方式增加特征点线,无论在效率方面,还是在完整性、合理性等方面都是很有限的。因此需要设计一定的算法来自动提取特征点。这些算法的原理大都基于原始等高线的拓扑关系。对TIN进行优化则需对三角形进行扫描判断并以一定的准则进行合理化的处理。2.6、规则数据生成三角网直接法：VIPS法、最大Z容差法等核心问题：从大量的格网点中提取表征地形特征的重要点集，如山顶点、山脊线点、山谷线点、鞍部点等。涉及问题：选点原则与终止条件（精度或循环次数）2.6.1、直接法的不同连接结果图以直接方式建立的三角网其实相当随意：(a)显示了根据正方形格网建立的双线性表面;(b)显示了此格网根据上图(a)中的对角线方向所分开的两三角形;(c)显示了对应(b)而生成的三角形;(d)则对应于(c),此时两对角线将格网分成四个顶点相对的三角形。尽管图中每个例子中的格网结点的高程值都相同,但根据(a)~(d)所显示的不同表面所内插出来的高程点其高程值将相差很大。网格剖分三角面的方法不好,会影响真实感图形的生成质量.将网格剖分成三角面,有上图所示的三种基本方法.实际应用中，三角面应沿着地形的走向剖分。若abs(Z4-Z2)>abs(Z3-Z1),则用上图(b)的剖分方法将此格子分成左上和右下两个三角面,在此格子内,地形走向是从左下到右上；若abs(Z4-Z2)