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

1、第 28卷 第 4期贵州工业大学学报 ( 自然科学版 )V ol. 28 N o. 41999 年 8 月JO U RN AL O F GU IZHO U U N IV ERSI T Y O F T ECHN O LO G YAugust. 1999( Na tural Science Editio n)文章编号: 1009-0193( 1999) 04-0017-05基于散点及边建立数字地面模型的研究及实现夏建云1 , 邸 元2( 1. 深圳市天健集团股份有限公司 ,深圳 518034; 2. 北京大学力学与工程科学系 ,北京 100871)摘 要: 对构筑三角形网格建立数字地面模型进行了研

2、究 ,给出了基于散点和边建立 三角形网格模型的生成算法和数据结构 ,并根据这些理论和方法在 Auto CAD R14 fo r Window s95环境下 ,用 Microsoft Visual C / C+ + 4. 2开发研制了建立数字地面 模型的应用程序 AutoD TM。关键词: 数字地面模型; 三角形网格;计算机辅助设计; 软件中图分类号: P221; P236 文献标识码: A0 前 言数字地面模型是以数字的形式按一定的结构组织在一起、从离散数据结构出发构造相互 连接的网络结构 ,表示实际地形特征的空间分布 ,从而建立起相关区域内平面坐标与高程间的 映射关系。通过数字地面模型 ,可

3、以方便地得到有关区域内任一点的地形情况 ,获得等高线、断 面线、坡度图等 ,并用于计算其高程、计算区域面积和土方工程量、划分土地、绘制流水线图等。 因此数字地面模型广泛地应用于公路 CAD、城市规划及机场、水利、军事的地理信息系统中 , 其原理还将适用于水文、海洋、气象等数据的处理。地形表面不同于一般的数学曲面 ,它在形态上较为复杂 ,无法用某一确定的数学公式来表 达和处理 ,通常情况下都采用插值法 ,根据原有离散点的高程来插补未知点的高程。 数字地面 模型分为规则方格形网模型 RSG和不规则三角形网格模型 T IN 两类 ,其中特别是 Delaunay 三角形网格适用于各种数据分布密度 ,有

4、利于更新和直接利用各种地形特征信息 ,直接利用原 始数据、保持原有精度 ,并具有唯一性好、追踪绘制等高线算法简单、适应不规则形状区域等优 点 ,因而被认为最适宜表面逼近、建立数字地面模型。 构筑 Delaunay 三角形网格过程中 ,算法 和数据结构对构网速度有着重要的影响 ,本文对基于散点及边建立三角形网格地面模型和等 高线的绘制进行了研究 ,并且开发了相应的应用程序 ,使所研究的构网算法和数据结构得以实 现。1 数据结构及算法给定一个 d维的欧几里得空间 Ed 和其上的 N 个点 mi 的集 M ,那么与 M 关联的 1阶收稿日期: 1999-03-2618 贵 州 工 业 大 学 学 报

5、 (自然科学版 )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)条边。 根据自动或半自动摄影测量和遥感方式 ,或者其它野外测量的地面

6、数据信息 ,除了地面坐标、高程数据之外 ,重要的地形和地物的特征信息还包括地性线、山脊线、山谷线、断裂线等 ,这 些数据常以控制线段的形式引入不规则三角网地面模型的构网算法中。 设 S是 Ed 中点集 M 和线段端点集 L 的并 ,如果在 S形成的 Delaunay三角形网中的每一个三角形的外接圆范围内 不包含与该三角形顶点通视的其它点 ,而且三角形的边与 L中任何约束线段 Li 不相交或仅交 于端点 ,则该三角形网格为 Ed 上 S由 L 约束的 Delaunay 三角形网。根据以上定义可以导出 Delaunay 三角形网的以下特性: 在 Delaunay 三角形网中任一三 角形的外接圆范围

7、内不会有其它点存在并与其通视 ,即空圆特性; 在构网时 ,总是选择最邻近 的点形成三角形并且不与约束线段相交;形成的三角形网总是具有最优的形状特征 ,任意两个 相邻三角形形成的凸四边形的对角线如果可以互换的话 ,那么两个三角形 6个内角中最小的 角度不会变大 ;不论从区域何处开始构网 ,最终都将得到一致的结果 ,即构网具有唯一性。这些特性是建立 Delaunay 三角形网数字地面模型算法和数据结构的依据。基于散点建立 数字地面模型 ,常采用在 d维的欧几里得空间 Ed 中构造 Dela unay三角形网的通用算法 逐 点插入算法 ,具体算法过程如下:1. 遍历所有散点 ,求出点集的包容盒 ,得

8、到作为点集凸壳的初始三角形并放入三角形链表。2. 将点集中的散点依次插入 ,在三角形链表中找出其外接圆包含插入点的三角形 (称为该点的影响三角形 ) ,删除影响三角形的公共边 ,将插入点同影响三角形的全部顶点连接起来 , 从而完成一个点在 Delaunay 三角形链表中的插入。3. 根据优化准则对局部新形成的三角形进行优化 (如互换对角线等 )。将形成的三角形放入 Dela unay三角形链表。4. 循环执行上述第 2步 ,直到所有散点插入完毕。上述基于散点的构网算法理论严密、唯一性好 ,网格满足空圆特性 ,较为理想。由其逐点插 入的构网过程可知 ,在完成构网后 ,增加新点时 ,无需对所有的点

9、进行重新构网 ,只需对新点的 影响三角形范围进行局部联网 ,且局部联网的方法简单易行。同样 ,点的删除、移动也可快速动 态地进行。 但在实际应用当中 ,这种构网算法不易引入地面的地性线和特征线 ,当点集较大时 构网速度也较慢 ,如果点集范围是非凸区域或者存在内环 ,则会产生非法三角形。 为了克服基 于散点构网算法的上述缺点 ,特别是为了提高算法效率 ,可以对网格中三角形的空圆特性稍加 放松 ,亦即采用基于边的构网方法 ,其算法简述如下:1. 根据已有的地性线和特征线 ,形成控制边链表。2. 以控制边链表中一线段为基边 ,从点集中找出同该基边两端点距离和最小的点 ,以该点 为顶点 ,以该基边为边

10、 ,向外扩展一个三角形 (仅满足空椭圆特性 )并放入三角形链表。3. 按照上述第 2步 ,对控制边链表所有的线段进行循环 ,分别向外扩展。4. 依次将新形成的三角形的边作为基边 ,形成新的控制边链表 ,按照上述第 2步 ,对控制第 4期夏建云等: 基于散点及边建立数字地面模型的研究及实现 19边链表所有的线段进行循环 ,再次向外扩展 ,直到所有三角形不能再向外扩展为止。 实际工程项目中 ,建立数字地面模型使用的数据点可达数百万个 ,因此在确定数据结构和算法时要充分考虑计算机存储容量和算法效率。 本文构网算法中点、边、三角形三种实体的数 据结构如下:struct Point / / 描述散点的链

11、表ads point point;/ / 散点/ / 指向下一个散点的指针struct Point *pnex tpoint;struct Edge / / 描述边的链表char ty pe;/ / 边的类型struct Point *pfro mpoint;/ / 指向边起点的指针struct Point *ptopoint;/ / 指向边终点的指针struct Triang le *plefttriang le;/ / 指向边左测三角形的指针struct Triang le *prighttriang le;/ / 指向边右测三角形的指针struct Edge *pnex tedge;/

12、/ 指向下一个边的指针;struct Triang le / / 描述三角形的链表char ty pe;/ / 三角形的类型struct Edge *pedg e1;/ / 指向三角形第一条边的指针struct Edge *pedg e2;/ / 指向三角形第二条边的指针struct Edge *pedg e3;/ / 指向三角形第三条边的指针struct Triang le *pnex ttria ngle;/ / 指向下一个三角形的指针;由前述基于散点和边的构网算法可知 ,提高三角形、线段、点三种实体间拓扑关系的查询 效率 ,减少形成三角形时对点的判断次数 ,可以显著提高构网算法的速度。例

13、如 ,基于边的构网 算法中 ,从点集中找出同某一基边两端点距离和最小的点的这一过程 ,并不需要对点集中所有 的点进行判断 ,仅对那些位于基边附近的点进行判断就可以了。 在本文核心算法实现中 ,将整 个点集所在的范围划分成为若干区域 ,位于该区域内的点以链表形式连接在一起 ,这些区域则 以一个二维数组来索引:struct Point m n / /m*n个区域内的散点链表数组2 等值线的绘制建立了数字地面模型之后 ,就可以进行等值点的追踪和等高线的绘制。设欲绘制的等高线 的高程为 z,对数字地面模型三角形链表中的每个三角形的三个边进行循环 ,由 z 的值进行 判别:z = ( z - z1 )

14、( z - z2 )20 贵 州 工 业 大 学 学 报 (自然科学版 )1999年其中 , z1、z 2 分别是三角形一条边两个端点的高程 ,两个端点的平面位置设为 ( x 1、 y1 )和 ( x 2、 y2 )。 如果 z> 0,则等高线不通过该三角形边; 如果 , z = 0,则等高线正好通过该三角形 边的端点; 如果 z < 0,则等高线通过该三角形边 ,由下式来计算边上等值点的平面位置 ( x ,y ):x =x 1 +x2-x 1( z - z1 )z2-z1y =y1 +y2-y1( z - z 1 )z 2- z1将三角形的两个边上等值点相连接 ,便得到了通过该三

15、角形的等值线段。依次可绘制出所 有指定高程的等值线。3 实例及结束语根据以上给出的生成算法和数据结构 ,本文采用 Micro soft Visual C /C+ + 4. 2为编程语 言 ,研制了在 AutoC AD R14 fo r Window s95环境下运行的基于散点和边建立数字地面模型的 程序 Auto DTM。 Auto DTM 根据实际工程数据构筑的实例如图所示 ,图 1是 Auto DTM构筑 的一三角形网地面模型实例的局部图 ,图 2是 Auto DTM 构筑的另一三角形网地面模型实例 和等值线的局部图 ,其中浅色线条表示三角形网格 ,深色线条表示绘制出的等值线。图 1 Au

16、to DTM 建立的一数字地面图 2 Auto DTM建立的一数字地面模型模型实例局部实例和等值线局部 AutoD TM 程序的具体应用情况表明:1. 基于边建立数字地面模型的算法和数据结构 ,对各种数据分布适应性强 ,便于更新和直接利用各种地形特征信息 ,保持原有数据精度 ,并具有追踪绘制等高线算法简单、适应不规则 形状区域等优点。2. 由于散点数据量大 ,数字地面模型技术往往受制于构网速度。本文前述的基于边建立数 字地面模型的算法和数据结构 ,构网速度快 ,算法效率高 ,可满足实际工程项目的需要。3. 采用 Microsoft Visual C /C+ + 4. 2为编程语言 ,在 Aut

17、o CAD R14 fo r Window s95环境下开发研制建立数字地面模型的应用程序 ,既利用了 Aut oCAD 强大的图形功能 ,又利用了第 4期夏建云等: 基于散点及边建立数字地面模型的研究及实现 21以 C+ + 为基础面向对象的开发环境和 Window s95所具有的丰富资源 ,便于所开发程序的维护 、更新及与最先进的软件技术同步发展。参 考 文 献 1 FrancoP. Prepar ata, Michael Ian Sha mos. Co mputa tio nal Geo metr yAn Intr oduc tion M . Spring erV er lag ,198

18、5. 2 J. M ar k W ar e. A Pr ocedure fo r Automatica lly Co rr ec ting Inva lid FlatT ria ng les Occur ring in T riang u-lated Co ntour Data J. Co mpute rs & Geosciences. 1998, 24( 2): 141 151. 3 方 铁. Auto CAD C语言高级编程 M .北京: 清华大学出版社 , 1995.Research and implementation of constructing digital terrain model using discrete points and edgesX IA Jia n-yuan1 , DI Yuan2( 1. Shenzhen To ng e Group Co.