四叉树高效Delaunay三角网生成算法  

An Algorithm for Building Delaunay Triangulation of High Efficiency

作　　者：石松[1] 朱泉锋[1] 唐丽玉[1] 

机构地区：[1]数据挖掘与信息共享教育部重点实验室福州大学福建省空间信息工程研究中心,福州350002

出　　处：《计算机工程》2005年第18期87-89,共3页Computer Engineering

基　　金：国家"973"重大基础前期研究基金资助项目"分布式虚拟地理环境与森林遥感建模研究"(2002CCC01900)

摘　　要：实现了一种以地形为应用背景的大规模离散点快速生成TIN的算法,该算法首先对大规模离散点按一定的阈值进行四叉树分割,然后对四叉树的每个叶子块分别以凸壳技术构三角网,而后再自底向上合并具有相同父亲节点的块,最后进行全局优化,生成Delaunay三角网。经实际地形数据验证结果表明:同样的算法,采用四叉树分块比采用平均分块策略有着更高的执行效率。An algorithm for building delaunay of high efficiency on the ground of terrain application is presented. At first, the large scale discrete points are divided by quad tree with a special scope. Secondly,for the every child block whose attribute is leaf type to construct the triangulation net based on convex technology, then the child blocks which have the same parent are combined. Lastly, through optimizing the triangulation net, the triangulation has been to delaunay triangulation, result indicates between the policy of quad tree and the policy of average to divided the points, the former has the higher efficiency in the same algorithm.

关 键 词：不规则三角网 DELAUNAY三角网 凸壳 四叉树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]