基于散点及边建立数字地面模型的及实现_夏建云.pdf研究.doc

第 28卷 第 4期 贵州工业大学学报 ( 自然科学版 ) V ol. 28 N o. 4 1999 年 8 月 JO U RN AL O F GU IZHO U U N IV ERSI T Y O F T ECHN O LO G Y August. 1999 ( Na tural Science Editio n) 文章编号: 1009-0193( 1999) 04-0017-05 基于散点及边建立数字地面模型的 研究及实现 夏建云1 , 邸 元2 ( 1. 深圳市天健集团股份有限公司 ,深圳 518034; 2. 北京大学力学与工程科学系 ,北京 100871) 摘 要: 对构筑三角形网格建立数字地面模型进行了研究 ,给出了基于散点和边建立 三角形网格模型的生成算法和数据结构 ,并根据这些理论和方法在 Auto CAD R14 fo r Window s95环境下 ,用 Microsoft Visual C / C+ + 4. 2开发研制了建立数字地面 模型的应用程序 AutoD TM。 关键词: 数字地面模型; 三角形网格;计算机辅助设计; 软件 中图分类号: P221; P236 文献标识码: A 0 前 言 数字地面模型是以数字的形式按一定的结构组织在一起、从离散数据结构出发构造相互 连接的网络结构 ,表示实际地形特征的空间分布 ,从而建立起相关区域内平面坐标与高程间的 映射关系。通过数字地面模型 ,可以方便地得到有关区域内任一点的地形情况 ,获得等高线、断 面线、坡度图等 ,并用于计算其高程、计算区域面积和土方工程量、划分土地、绘制流水线图等。 因此数字地面模型广泛地应用于公路 CAD、城市规划及机场、水利、军事的地理信息系统中 , 其原理还将适用于水文、海洋、气象等数据的处理。 地形表面不同于一般的数学曲面 ,它在形态上较为复杂 ,无法用某一确定的数学公式来表 达和处理 ,通常情况下都采用插值法 ,根据原有离散点的高程来插补未知点的高程。 数字地面 模型分为规则方格形网模型 RSG和不规则三角形网格模型 T IN 两类 ,其中特别是 Delaunay 三角形网格适用于各种数据分布密度 ,有利于更新和直接利用各种地形特征信息 ,直接利用原 始数据、保持原有精度 ,并具有唯一性好、追踪绘制等高线算法简单、适应不规则形状区域等优 点 ,因而被认为最适宜表面逼近、建立数字地面模型。 构筑 Delaunay 三角形网格过程中 ,算法 和数据结构对构网速度有着重要的影响 ,本文对基于散点及边建立三角形网格地面模型和等 高线的绘制进行了研究 ,并且开发了相应的应用程序 ,使所研究的构网算法和数据结构得以实 现。 1 数据结构及算法 给定一个 d维的欧几里得空间 Ed 和其上的 N 个点 mi 的集 M ,那么与 M 关联的 1阶  收稿日期: 1999-03-26 18 贵 州 工 业 大 学 学 报 (自然科学版 ) 1999年 Vo ronoi 图为覆盖 Ed 的一个凸多边形序列 { V ( m1 ) , V ( m2 )… V ( mi )… V ( mN ) } ,其中 V ( mi )包 含了 Ed 中所有以 M 中的点 mi 为欧几里得距离最近点的点。于是 ,这 N 个凸多边形将 Ed 划分 成为一个凸网 ,记为 Vor ( M )。V or( M)的几何直线对偶构成了一个新的图 ,即在 Ed 中对 M 的 一个 Delaunay 三角形网格剖分。 可知 , Vo r( M )至多有 ( 2N - 5)个顶点和 ( 3N - 6)条边。 根据自动或半自动摄影测量和遥感方式 ,或者其它野外测量的地面数据信息 ,除了地面坐 标、高程数据之外 ,重要的地形和地物的特征信息还包括地性线、山脊线、山谷线、断裂线等 ,这 些数据常以控制线段的形式引入不规则三角网地面模型的构网算法中。 设 S是 Ed 中点集 M 和线段端点集 L 的并 ,如果在 S形成的 Delaunay三角形网中的每一个三角形的外接圆范围内 不包含与该三角形顶点通视的其它点 ,而且三角形的边与 L中任何约束线段 Li 不相交或仅交 于端点 ,则该三角形网格为 Ed 上 S由 L 约束的 Delaunay 三角形网。 根据以上定义可以导出 Delaunay 三角形网的以下特性: 在 Delaunay 三角形网中任一三 角形的外接圆范围内不会有其它点存在并与其通视 ,即空圆特性; 在构网时 ,总是选择最邻近 的点形成三角形并且不与约束线段相交;形成的三角形网总是具有最优的形状特征 ,任意两个 相邻三角形形成的凸四边形的对角线如果可以互换的话