论文部分内容阅读
Delaunay三角剖分是地理信息系统(Geographical Information System,GIS)数据表达、管理和集成的一项重要内容,也是实现地形可视化的一种行之有效的方法和工具。由于其在科学计算可视化、地学分析、地图综合、虚拟现实和计算机视觉等领域有着重要的意义和举足轻重的作用,从而吸引了广大学者对其进行研究。然而,剖分效率仍然是制约Delaunay三角剖分的一个瓶颈。在不规则三角网(Triangulated Irregular Network,TIN)的建模中,Delaunay三角剖分具有空外接圆及最大化最小角的良好性质,被公认为是最优的三角剖分,它既可适应规则分布的数据,也可适应不规则分布的数据,能够灵活地处理特殊地形。本文对其传统算法进行了分析和对比,重点研究了插入点定位算法和Delaunay三角剖分的逐点插入算法,并在此基础上实现了Delaunay三角网的快速构建。论文的主要研究工作和取得的主要成果如下:(1)通过研究分析已有插入点定位算法的不足,针对目前仍然存在的主要问题,提出了一种新的插入点混合定位算法。将三角形面积坐标算法与直线行走算法相结合,在点定位过程中可大幅度缩短搜索路径,快速定位到插入点所在的目标三角形。(2)针对现有Delaunay三角剖分速度较慢的问题,提出了格网划分的Delaunay三角网快速生成算法。首先通过建立动态矩形包围盒;其次,结合格网划分技术对数据点集进行有效划分;进行Delaunay三角剖分时,引入文中提出的插入点混合定位算法实现目标三角形的快速定位;最后,用简易的空外接圆检测进行优化,使得Delaunay三角网的剖分更加高效。本文对改进后的算法进行了实验,结果表明改进后的算法简单高效,而且具有较好的实用性。