TIN三角化网格法

1、TIN（不规则三角化）（不规则三角化）构建三角网格法构建三角网格法不规则三角网概述不规则三角网(TIN-Triangulated Irregular Network)通过用一系列互不交叉、互不重叠、连接在一起的三角面来逼近物体表面。TIN 三角网模型具有精度高、速度快、效率高和容易处理断线和空穴等特点。 在所有可能的三角网中, Delaunay三角网在形态拟合方面表现最为出色,因此常常被用于TIN的生成。当不相交的断裂线等被作为预先定义的限制条件作用于TIN的生成当中时,则必须考虑带约束条件的D三角网。 TINTIN 基本内涵： TriangulatedTriangulated：离散数据的三角

2、化过程即TIN的建立过程； IrregularIrregular：用于构建TIN的采样点的分布形式不规则性； NetworkNetwork：互不交叉、互不重叠连接在一起的三角形网。TIN的基本元素与类型TIN的基本元素：1 12 23 34 45 5T1T1T2T2T3T3T4T4T5T5E1E1E2E2E3E3E4E4E10E10E9E9E7E7E8E8E6E6E5E56 6 结点（Nodes） 边（Edges） 三角形（Triangles） 拓扑关系（Topology） TIN的类型： 无约束TIN：数据点不存在任何关系 约束TIN：部分数据点间存在联系，一般通过特征线（边界、内部特征线)

3、TIN的体系构成三角形划分准则三角形划分准则物体数据物体数据TINTIN模型模型算法与程序算法与程序数据组织与结构数据组织与结构TIN存储与组织结构：TIN是一典型的矢量数据结构，通过节点、三角形边和三角形面间的关系显示或隐式表达物体散点的拓扑关系，要求高效的TIN存储与组织结构。TIN的三角形划分准则：TIN 模型中三角形的几何形状直接决定TIN的应用质量。考虑物体的各向异性和空间的自相关性，加之实践证明：知道狭长的三角形的插值精度较之规则的三角形可信度要低；要求TIN中的三角形尽量接近正三角形、最近邻的点连接成三角形、三角形唯一。三角化算法与程序：前两者必须有高效的三角化算法与程序来实现。

4、算法的作用由其本身的性能和实现它的程序质量决定；而程序的性能依赖算法的原理。最短距离和准则：最短距离和准则：最短距离和就是指一点到基边两端的距离和为最小 。 张角最大准则：张角最大准则：一点到基边的张角为最大。 面积比准则：面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。 对角线准则：对角线准则：两个三角形组成的凸四边形的两条对角线之比，比值限定值须给定，即当计算值超过限定值才进行优化。 空外接圆准则空外接圆准则 ：在任意一个三角形的外接圆范围内不包含点集M中的任何其他点。最大最小角准则最大最小角准则：TIN中两个相邻三角形形成的凸四边形中，这两个三角形中的最小内角一定

5、大于交换凸四边形对角线后所形成的两三角形的最小内角。TIN的三角剖分准则空外接圆准则、最大最小角准则及张角最大准则是等价的，其余的则不然。三角形准则是建立三角形网的原则，应用不同的准则将会得到不同的三角形网络。构建过程应该从同一原则开始，尽量使之形成唯一三角网，也就是要求：在同一准则下由不同的位置开始建立三角形网络，其最终的形状和结构应是相同的。 （a a） （b b） （c c） （d d） （e e） （f f） (g)(g)(a/b):空外接圆准则；(c):最大最小角准则; (d):最短距离和准则；(e):张角最大准则；(f):面积比准则； (g):对角线准则；TIN的三角剖分准则Del

6、aunary三角网（简称D三角网）D 三角网为相互邻接且互不重叠的三角形的集合,每一三角形的外接圆内不包含其他的点（由空外接圆准则、最大最小角准则及张角最大准则形成的三角网都是D三角网）。形成D三角网的LOP法则：LOP是Lawson在1977年提出的D 三角网形成局部优化过程 Local Optimal Procedure。LOP的基本思想是：应用D 三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断，如其中一个三角形的外接圆中含有另外一个顶点，则交换四边形的对角线。l 空外接圆特性l 最大最小角特性 详解D三角网LOP准则空外接圆特性 (Circle准则 )：在任意一个三角形

7、的外接圆范围内不包含点集M中的任何其他点。 （a）在三角形内 （c）在三角形外接圆上(按最小边长标准判断对角线13更为可取) （b）在三角形外接圆内 （d）在外接圆外最大最小角特性：在TIN中的两个相邻三角形形成的凸四边形中，这两个三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角。局部最优方法(LOP - Local Optimization Procedure) ：交换凸四边形的对角线，可获得等角性最好的三角网 。(a)新点插入p (b)对角线交换 (c)结果三角网 TIN三角化方法分类和特点TINTIN算法类型算法类型不规则不规则数据分布数据分布规则规则数据分布数据

8、分布沿等高线沿等高线分布数据分布数据VIPsVIPs算法、循环迭代算法算法、循环迭代算法层次三角形算法层次三角形算法特征线算法特征线算法探测优化算法探测优化算法辐射扫描算法、模拟退火算法辐射扫描算法、模拟退火算法数学形态算法数学形态算法DTDT三三角剖角剖分分直接直接DTDT间接间接DTDT分割合并算法分割合并算法逐点插入法逐点插入法三角形增长法三角形增长法基本思路：根据随机分布的原始点建立连续覆盖整个形体区域的不规则的 D三角网(D - TIN)。 分类：1)、分割合并算法2)、三角网生长算法3)、逐点插入算法根本问题：确定哪三个数据点构成一个三角形，即自动联结三角网。散点的无约束TIN三角

9、化方法D三角网生成示例：分割合并算法 分割合并算法的基本思想采用分而治之策略，将复杂问题简单化： 先将数据点分割成易于三角化的点子集（如每子集3、4个点），后对每个子集分别三角化，并由LOP优化成D三角网；之后对每个子集的三角网进行合并，形成最终的D三角网。 分割合并算法的步骤：S1 将数据集以横坐标为主、纵坐标为辅按升序排序。S2 如数据集中点数大于阀值，则继续将数据集化为点个数近似相等的两个子集，并对每个子集做如下工作： 1 获取每子集的凸壳； 2 以凸壳为数据边界进行三角化，并用LOP优化成D三角网； 3 找出连接左右子集两个凸壳的底线和顶线； 4 由底线到顶线合并两个三角网。S3 如数

10、据集中点数不大于阀值，则直接输出三角剖分结果。详解：数据点集采用递归分割快速排序法；子集凸壳的生成可采用格雷厄姆算法；子集三角化可采用任意方法，如子集最小到3或4个点则可直接三角剖分之；子网合并则需先找出左右子集凸壳的底线和顶线，然后逐步合并三角剖分得到最终D三角网。凸壳生成算法 凸壳生成的格雷厄姆算法：凸壳的定义： 凸壳是数据点的自然极限边界，为包含所有数据点的最小凸多边形，连接任意两点的线段完全位于该凸多边形中，同时其区域面积达到最小值。S1 找到点集中纵坐标最小的点P1S2 将P1与其它点用线段连接，并计算这些线段的水平夹角S3 按夹角大小对数据点排序；如夹角相同，则按距离排序，得到P1

11、，P2， ，Pn.S4 依次连接点，得到一多边形。循环删除多边形的非凸顶点得到点集的凸壳。D三角网生成示例：分割合并算法 两子网底线、顶线的查找两子网合并三角网生长算法基本思路： 先找出点集中相距最短的两点连接成为一条Delaunay边，然后按D三角网的判别法则找出包含此边的D三角形的另一端点，依次处理所有新生成的边，直至最终完成。 基本步骤：S1 以任一点为起始点（一般位于数据点几何中心附近）； S2 找出与起始点最近的数据点相互连接形成D-三角形的一条边作为基线，按D-三角网的判别法则（即它的两个基本性质）找出与基线构成D-三角形的第三点； S3 基线的两个端点与第三点相连，成为新的基线；

12、 S4 迭代以上两步直至所有基线都被处理。 逐点插入算法 动态的构网过程:先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法确保其成为D-三角网。 1）定义一个包含所有数据点的初始多边形(扩展三角形或外凸壳)；2）在初始多边形中建立初始三角网，然后迭代以下步骤，直至所有数据点都被处理： a)插入一个数据点P，在三角网中找出包含P的三角形t，把P与t的三个顶点相连，生成三个新的三角形（存在P在三角形顶点或边上等情况）； b)用LOP算法优化三角网。 3) 可能的外围三角形处理。基本思路：基本步骤：初始包容多边形：点的插入与LOP处理： 任取一个点(设为O点) 为

13、基准点，计算其余点和之连线的方向，以方向角的大小进行排序； 连接O点和其它点，并连接相邻点，形成最初扇形三角网； 从扇形边的任一点开始，以逆时针进行凹边连接，如为当前点，沿逆时针方向搜索点和再下一个点，如在ps前进方向的左侧，当前点改为，从点继续搜索；如果在ps前进方向的右侧，则连接pq，生成一新三角形，再往下搜索，点在pq的右侧，连接pr，又生成一个三角形，下一个点在pr的左侧，当前点改为;从点继续搜索，直到把外边界变成凸多边形为止； 利用LOP优化，得到D_三角网。其它方法辐射扫描算法辐射扫描算法约束D三角网方法尽管D三角形构网的方法很多，满足“最小角为最大”的原则，可尽力避免狭长三角形的

14、出现。但Delaunay构网是对离散点集凸包的三角化，故在实际应用于D三角网格时会遇到以下几个须解决的问题： 在DT中有一些网格必须经过的特征线，如脊线、断裂线、边缘线等； 欲三角化的点集范围是非凸区域，甚至存在内环。 约束D三角网的目标T1、T2为特征边，(a)为重构前三角化结果, (b)为重构后的三角化结果全局优化构网后，可能会有跨越内外边界、特征约束线等的非法三角形，必须对这些三角形进行约束处理。经处理后数据点的内外边界和特征约束线中的每一个边（段）都应成为最终三角化结果中三角形的一条边。约束DT的三角化准则带约束条件的D法则 带约束条件的Lawson-LOP交换 只有当三角形外接圆内不

15、包含任何其他点，且其三个顶点相互可视时，此三角形才是一个带约束条件的D三角形。 只有在满足带约束条件的D_法则的条件下,由两相邻三角形组成的凸四边形的局部最佳对角线才被选取。 对数据点及作为约束条件的断裂线。可视图由互相可视的任意两点连接而成。在可视图中,除在断裂线的端点处外,连接线与任一断裂线都不相交 。约束TIN：Constrained Delaunay Triangulation,简称CDT.带约束条件的D三角网准则图示插入约束线段ab和bc后带约束条件的Lawson-LOP交换的完成 (a)新点p插入 (b)对角线交换 (c)结果三角网 CDT的两步法目前采用最多的CDT构建方法：先构

16、建无约束三角网，后引入约束线段（调整过程）。Sloan采用连续的对角线交换法实现约束线段的嵌入；Floriani的算法则采用简单多边形D三角化的方式实现之。约束三角网的对角线交换迭代思想：基本术语：影响域：约束边所经三角形构成的区域；对角线：影响域内每一条边；起始点：约束边的一端点；目标点：约束边的另一端点；目标：从起始点出发，按照一定的规则逐步交换对角线，最终使起始点和目标点相连。基本思路：从起始点出发，对遇到的每条对角线的可交换性进行判断，可交换就交换，不可交换就判断下一条，到达最后一条对角线后，第一轮交换结束。然后从头再来，开始下一轮，直到约束边的加入。约束三角网的对角线交换迭代算法步骤

17、：S1 形成初始D三角网（可或不含约束线段的顶点，但有不同处理）。S2 对每一约束线段，检查是否已是三角 形的边；是则检查下一约束线段，否 则找出与该约束线段相交的所有三角形边，存入相交边表中。S3 交换相交边 如共用相交边的两三角形构不成 严格的凸四边形，则该边仍放回相交边表中 构成严格的凸四边形，则交换对角线；检查新的对角线是否与当前约束线段相交，相交则放入相交边表中；不相交则放入不相交边表中； 对不相交边表中每条边进行局部三角网优化处理。规则数据生成三角网直接法：VIPS法、最大Z容差法等核心问题：从大量的格网点中提取表征物体特征的重要点集，如顶点、脊线点、鞍部点等。涉及问题：选点原则与

18、终止条件（精度或循环次数）直接法的不同连接结果图以直接方式建立的三角网其实相当随意：(a)显示了根据正方形格网建立的双线性表面;(b)显示了此格网根据上图(a)中的对角线方向所分开的两三角形;(c)显示了对应(b)而生成的三角形;(d)则对应于(c),此时两对角线将格网分成四个顶点相对的三角形。尽管图中每个例子中的格网结点1、2、3、4的坐标都相同,但由(a)(d)所显示的不同表面所内插出来的点其结果相差很大。 网格剖分三角面的方法不好，会影响真实感图形的生成质量。将网格剖分成三角面，有上图所示的三种基本方法。实际应用中，三角面应沿着物体的走向剖分。 若abs(Z4-Z2)abs(Z3-Z1)

19、,则用上图(b)的剖分方法将此格子分成左上和右下两个三角面,在此格子内,物体走向是从左下到右上； 若abs(Z4-Z2)abs(Z3-Z1),则用上图(c)的剖分方法将此格子分成左下和右上两个三角面,在此格子内,物体走向是从左上到右下； 若abs(Z4-Z2)=abs(Z3-Z1),则外看一层,以与该格子相邻的格子的物体走向作为该格子的物体走向,如果外看一层仍无法判断物体的走向，则按上图(d)的剖分方法将此格子分成4个三角面. 直接法合理连接的准则通过比较计算个网点的重要性，保留重要的格网点。将格网坐标值与8个邻点坐标的内插值进行比较，保留差分超过某个阙值的格网点或保留前N个重要点。算法思想：P点的重要性度量指标: dAE =HP-HP , HP=(HA