论文部分内容阅读
Delaunay三角网是数字高程模型(DEM)构建的基础。Delaunay三角网具有适用性强、分布灵活的特点,对于非规则离散分布的散乱数据的动态网格化的计算机造型、复杂构图研究、图像处理等许多应用领域有着广泛的用途;DEM已在测绘、遥感、农林规划、城市规划、土木水利工程、地学分析等各个领域都有了广泛的应用。数字高程模型的表示方法主要有规则格网模型、不规则三角网模型和等高线模型三种,而不规则三角网(TriangulatedIrregularNetwork,TIN)这种表示数字高程模型的方法,能减少规则格网方法带来的数据冗余,又同时在计算(如坡度)效率方面又优于纯粹基于等高线的方法。 本文在针对传统算法进行了对比和分析后,发现传统的算法构网速度很低,并且在实际应用中,部分散点之间常常存在着某种约束关系,如对象重建中模型边界、地表模型中的山脊线、山谷线、断裂线等,在对此种数据域进行三角剖分时,三角剖分结果应保持其原有的约束关系。因此,本文基于离散点的Delaunay三角网生成算法,建立论文有约束条件的约束三角网。主要的研究成果和内容如下:首先在离散点的Delaunay三角网生成方面,本文中在插入点算法的基础上,建立凸包和矩形包容盒,建立虚拟网格,对原始离散点进行一级格网自适应分块,并建立索引关系。在定位点所在三角形时引入了快速点定位算法以及简易的空外接圆及圆内测试公式。其次在约束Delaunay三角网理论基础之上,结合上面散点域的剖分方法,在已有的算法基础上进行改进,完成约束Delaunay三角网的构建。 本文在逐点插入法的基础之上,提出了一些新的细部改进的实现方法。局部优化操作和改进的算法实现使得对大容量离散点的三角网构建速度更快,效率更高;对约束条件的嵌入更接近实际情况,并且对约束线相切等特殊情形进行了处理,进一步提高了算法的稳健性。