Delaunay三角网的算法详述及其应用发展前景.pdf

第 29 卷第 6 期 测绘科学 Vol 28 No6 2004 年 12 月 Science of Surveying and Mapping Dec DELAUNAY 三角网的算法 详述及其应用发展前景 ① ① ② ① 邵春丽 , 胡 　鹏 , 黄承义 , 彭 　琪 ( ①武汉大学资源与环境科学学院 ,武汉 　430079 ; ②青岛环海海洋工程勘察研究院 , 山东 青岛 　266033) ( ) 【摘 　要】在 GIS 应用领域中 , Delaunay 三角网通常被用于生成不规则三角网 TIN 模型 , 并用于描述地表形态。本 文详细叙述改进了的现有国内外 Delaunay 三角网的生成算法 , 并发现 Delaunay 三角网不但在描述地表形态上有很 大的优势 , 而且在图像处理、模式识别领域也将有很大的优势。而且国内外已经有部分学者专家作出一定的尝 试 , 并且取得了较好的效果。所以作者进一步提出将 Delaunay 三角网用于地图符号信息识别 , 将是一个很有发展 前景的应用方向。 【关键词】Delaunay 改进算法 ; TIN ; 地图模式识别 ( ) 【中图分类号】P208 　　　　 【文献标识码】A 　　　　 【文章编号】1009 2307 2004 06 0068 04 ( 三个 V 多边形的生长中心而生成的 Delaunay 三角网和 1 　引 　言 Voronoi 图的关系如图1) , 这个公共顶点就是形成的 Delaunay 虽然目前关于Delaunay 三角网的文章有很多 , 但是大多 三角形外接圆的圆心。 都只介绍了算法的主要思想 , 并没有介绍其详细生成算法 , 给参看这类文章的读者带来了很大的不便。所以笔者针对该 不足 , 详细介绍了改进的分割归并法、逐点插入法和三角网 生长法。可以根据不同的实际情况选用不同的算法。并在此 基础上发现了如果能把 Delaunay 三角网应用于地图信息识 别 , 将是一个很有发展前景的方向。 2 　相关概念 21 　TIN ( Triangulated Irregular Net) 即不规则三角网 , 图 1 　实线为 Delaunay 三角网 , Delaunay 三角网是其中的一种表现形式 , 也是一种主要的 虚线为 Voronoi 图 DTM 表示法[1 ] 。 ( ) 由于 TIN Delaunay 三角网 本身的这些特点 , 决定了它 22 　Delaunay 三角网的定义 : 它是一系列相连的但不 在现代地理科学与计算机科学中的不可忽视的地