一种三角网边界提取的方法

1、测绘科学sc ience of su rveying and m app ingvo l134 supp lo c t1第 34卷增刊2009年 10月一种三角网边界提取的方法于庆 , 王结臣 , 陈焱明(南京大学地理信息科学系 ,南京 210093 )【摘 要 】本文针对三角网数据 , 提出一种边界提取的新算法 。该算法需要先建立三角形 、边 、顶点两两之间的拓扑关系 , 而后通过递归方法实现边界的提取 。其实现思路是 : 该方法使用循环过程 , 首先在边集合中找到一条邻接三角形数量为 1的边 , 该边的两个端点分别作为多边形边界的前一点与当前点 。然后在当前点的邻接三角形中寻找邻接三角形数

2、量为 1的边且该边的两个端点有且只有一点与当前点或前一点重合 。端点中非重合端点作为 多边形边界的后续点 , 通过递归方法依次寻找边界其他后续点 , 直到与第一点重合时结束此次边界提取 。之后进入下一次循环提取下一条边界直至所有边界提取完毕 。笔者通过实验证明了该算法的正确性与合理性 , 具有较高的计算效率且易于实现 。【关键词 】边界 ; 不规则三角网 ; 拓扑 ; 多边形 ; 递归算法【文章编号 】1009 22307 ( 2009 ) 08 20082 203【中图分类号 】 p208【文献标识码 】a对此笔者设计了一种新的数据结构以便有效的组织三角形 、边 、顶点的拓扑关系 。1) 点

3、集以数组形式存储 , 数组中元素记录数据点的位置 、二维 x , y坐标值 、点的邻接三角形数量及所在数组中的位置 。2) 边集以边数组存储 , 数组中元素记录边的位置 、邻接三角形数量 、边的使用次数以及其两个顶点所在数组中的位置 。3) 三角形集以三角形数组形式存储 , 数组中元素记录三角形的位置 、三个顶点及其对边所在数组中的位置 、三角形是否位于多边形内 。 上述数据结构用 c语言描述如下 :struc t d isc re tedpo in t / /三角形顶点数据结构定义1 引言对多边形实现三角剖分是众多专家 、学者的研究热点 , 前辈们经过探索与研究提出了诸多算法 , 如基于边优

4、先的 任意多边形最优三角剖分法 1 、 kong切耳法 2 、基于二叉 树思想的多边形三角剖分法 3 、带特征约束的散列数据的 最优三角剖分法 4 等 。然而关注并对三角网中提取边界信 息并构建成面进行研究的人并不多 。目前已经提出的算法 有三角形集合的边界生成算法 5 , 该方法只是获取三角网 中边界线段集合 , 并没有将边界线段按顺序首尾连接生成 闭合边界 。张献颖等 6 提出的空间三角网格曲面的边界提 取方法能够实现三角网边界的提取 , 但该方法需要对三角 网中每个点进行边界点判断 , 计算量过大 , 算法的执行效 率不高 。为此 , 探索三角网边界提取方法有着一定的理论 意义和实际需求

5、 。考虑到拓扑关系在空间数据中的重要性 , 本文设计了一种有效的数据结构来存储三角形 、边 、顶点 两两之间的拓扑关系 , 而后通过递归方法实现边界的提取 。2 数据结构设计在数据结构设计中用到了邻接三角形的概念 , 点与边 同三角形的邻接关系描述如下 :设 t、 e、 p 分别为三角网中的三角 形集合 、边 集 合 、 点集合 。若 pi t, 则称 t为 pi 的一个邻接三角形 ; 若 ei t, 则称 t为 ei 的一个邻接三角形 ; 若 ei = ta tb ( ta t , tb t ) , 则称 ei 为内部边 , 否则为边界边 。本文算法的核心是利用拓扑关系进行多边形边界提取 ,

6、拓扑结构是明确定义空间结构关系的一种数学方法 , 在地理信息系统中 , 它不但用于空间数据的编辑和组织 , 而且 在空间分析和应用中都具有非常重要的意义 。拓扑数据清楚地反映出实体之间的逻辑结构关系 , 而且这种拓扑数据较几何数据有更大的稳定性 , 即其不随地图投影而变化 7 。doub le x, y;/ /顶点的 x, y坐标in t 3 indextrigan le;中的位置/ /邻接三角形在三角形集合in t trin um; 3 d ispo in ts;/ /邻接三角形数量/ /顶点集合struc t edgein t sta rt;in t end;/ /三角形边数据结构定义/

7、/边的起点在数组中位置/ /边的终点在数组中位置in t tricoun t; / /邻接三角形数量boo l u sed; / /提取边界时 , 判定边是否使用过 3 edge s;/ /边集合struc t triangle_ n e t / /三角形数据结构定义in t p1;in t p2;in t p3;in t edgep1; in t edgep2; in t edgep3; 3 trin e ts;/ /顶点 p1在数组中位置/ /顶点 p2在数组中位置/ /顶点 p3在数组中位置/ /顶点 p1对应的边在数组中位置/ /顶点 p2对应的边在数组中位置/ /顶点 p3对应的边在

8、数组中位置/ /三角形集合作者简介 : 于庆 ( 19842) , 男 , 硕 士 研究生 , 主要研究领域为地理信息系统 。e2m a il: yq0451 1631com3 边界提取算法311 生成拓扑关系在用本文算法进行三角网边界提取之前需要完成多边形三角剖 分 及 三 角 形 、边 、顶 点 之 间 的 拓 扑 关 系 的 建 立 。文献 1 24 中 介 绍 了 三 角 剖 分 的 详 细 过 程 , 这 里 不 再 敖收稿日期 : 2009 207203形集合中的位置 。这样便建立了三角形 、边 、点之间的拓织边界数据结构 , 在边界提取过程中建立最小外包矩形如扑关系 。312 边

9、界提取算法三角网形态如图 1 所示 , 其中内部的边具 有两个邻接三角形 , 而位于边界的边有且只有一个邻接三角形 。三角网中边的这个性质对边界提取有着至关重要的作用 。我们 在三角形边的数据结构中使用 tricoun t属性记 录边的邻接三角形数量 。算法的主要思路 : 该方法使用循环过程 , 首先在边集合中找到一条邻接三角形数量为 1 的边 , 该边的 两个端点分别作为多边形边界的前一点与当前点 。在当前点的邻接三角形中首先寻找满足条件 tricoun t = 1 的边且该边的两个端点有且只有一点与当前点或前一点重合 。端点中非重合端点作为多边形边界的后续点 , 因该边已被使用 一次 ,

10、故改写 u sed 成员为 true, 表明该边的使用情况以便于减少后续判断 , 其次通过递归方法依次寻找边界其他后续点 , 直到与第一点重合时结束此次边界提取 , 之后进入 下一次循环提取下一条边界直至所有边界提取完毕 。完整流程描述如下 :图 3所示 , 将复杂的边界包含关系判断转换成简单的矩形之间的包含判断 。我们在数据结构中用 x_ m in, x_ m ax, y_ m in, y_m ax 记录了整条边界的坐标范围 , 其中外边界的 x_ m in、y_ m in最小 , x_ m ax、 y_ m ax最大 。这种边界范围对比的 方法易于实现 , 况且记录 的各边界的坐标范围 在

11、 很 多 g is操作中非常实用 , 例如图层显示时经常根据边界范围与应用程序显示区之间的空间关系决定是否进行边界绘制 。4 实例与分析为测试算法的性能 , 我们进行了一些实验 。测试计 算 机配 置 为 : pen tium 4 1173 g cpu , 210 g 内 存 , 操 作 系 统 w indow s x pp rofe ssiona l。图 4 为 测试图件 之 一 , 该 图 基 本 信息如下 : 共有 2条边界 , 节点总数 26个 , 剖分后生成 25 个三角形构成三角网 (如图 5 ) , 对剖分后生成的三角网进行 边界提取 , 多边形形态如图 6 所示 , 与剖分前的

12、多边形 形 态完全吻合 。采用本文方法进行边界提取过程中 , 提取时间与多 边形节点数量相关与多边形边界数量无关 。这是由于边界提取过程实质是根据当前点与前一点寻找后续点 , 因此后续点越多消耗 时 间 越 长 ; 在 边 界 提 取 过 程 中 采 用 循 环 过 程 ,每循环一次 完 成 一 条 边 界 的 提 取 。而 在 边 界 提 取 过 程 中 ,寻找边界后续点时利用了三角网中三角形与边 、三角形与顶点 、顶点和边之间的拓扑关系 , 只需在当前点邻接三 角形中寻找满足条件的边 , 提取边的节点 , 过程简单大大 加 快了边界提取速度 , 况且利用本方法在从三角网提取边界过程中不受边

13、界数量影响 。5 结束语本算法利用了三角网中边界边有且只有一个邻接三角 形的特性 , 通过设计合理的数据结构 , 在三角网生成过 程 中建立三角形 、边 、顶点之间的拓扑关系 , 直接遍历三 角 网边界集合中各边的邻接属性 , 采用递归方法完成了边界 点的排序 、实现了边界线的提取 , 并解决了复杂多边形 中 内边界与外边界的判断 。通过实验证明该方法稳定性强并 易于实现 , 可应用于从不规则三角网的数字地面模型中快 速获取地物轮廓线信息 , 同时也为三角网边界提取提供了 一种思路和途径 。参考文献图 1 三角网形态初始化 , 对三角网边界集合数组 edge s进行初始化 , 将u sed属性

14、设为 fa lse。循环过程 , 遍历 三 角 网 的 边 集 合 , 找 到 一 条 tricoun t属性值为 1的任意边 , 判断其端点邻接三角形数量 , 若为 1则作为当前点 , 另一端点作为前一点 , 通过当前点寻找后续点 。1) 遍历当前点的所有邻接三角形 , 找到满足如下条件的边 。邻接三角形数量为 1; 在多边形边界提取过程中该 边未被使用过 , 即 u sed属性值为 fa lse; 与前一点和当前点构成的边有且只有 1个交点 。2) 将该边中不与当前点重合的一端设为后续点 , 重新设置前一点与当前点 , 令前一点指向当前点 、当前点指向 后续点 , 并将该边的 u sed属

15、性设置为 true。如闭合则转入步骤 3 ) , 否则转入步骤 1 ) 。3) 保存追踪所得的结果边界 , 必要时进行边界数据压 缩等后处理 。此次循环结束 , 转入下一次循环 。输出追踪结果的边界集合 , 过程结束 。313 多边形构建复杂多边形通常包含 “洞 ”, 其形态如图 2所示 。要完 成该类多边形的建立首先要判定边界之间的包含关系 , 确定多边形的外边界与 “洞 ”。 1 翟仁健 , 武芳 , 薛本新 1 基于边优先的任意多边形最 优 三 角 剖 分 j . 测 绘 科 学 , 2008, 33 ( 1 ) :12221251x ian shu kong, h1eve re tt,

16、 godfried tou ssa in t1the graham scan triangu la te s simp le po lygon s j . pa tte rn r ecogn ition l e tte rs, 1990 , 11 ( 11 ) : 713 27161刘强 , 李德仁 1 基于二叉树思想的任意多边形三角剖分递归算法 j . 武汉大学学报 (信息科 学版 ) ,2002 , 27 ( 5 ) : 52825331(下转第 88页 ) 2 3 88测绘科学第 34卷m e sse rli b , and ive s j d1moun ta in s of the w

17、o r1da 3 globa lp rio rity m .the pa rthenon pub lish inggroup1n ew yo rk andlondon, 19971p rice m f, and n b u tt ( ed s1 ) fo re sts in su sta inab le moun ta in deve lopm en t repo rt fo r 2000 r . cab in te r2 na tiona l, w a lling2fo rd, u k: 4291南京大学 , 等 1 地理学词典 m . 北京 : 商务印书馆 , 19821肖克 非 1 中

18、国 山 区 经 济 学 m . 北 京 : 大 地 出 版社 , 19881徐樵利 , 谭传凤 1 山地地理系统综论 m . 南京 :华中师范大学出版社 , 19941程鸿 1 我国山地资源的开发 j . 山地研究 (现 山地学报 ) , 1983, 1 ( 2) : 1271赵 松 乔 1 我 国 山 地 环 境 的 自 然 特 点 及 其 开 发 利 用 j . 山地研究 (现山地学报 ) , 1983 , 1 ( 3 ) : 1291周启鸣 , 刘学军 1数字地形分析 m . 北京 : 科学出版社 , 2006: 59 2601汤国安 , 杨昕 1a rcg is地理信息系统空间分析试验

19、教程 m . 北京 :科学出版社 , 2006: 3452346汤国安 , 陈正江 , 赵牡丹 , 等 1a rcv iew地理信息系统 空 间 分 析 方 法 m . 北 京 : 科 学 出 版 社 ,2005: 1691陈加 兵 , 励惠国 , 郑达贤 , 等 1 基于 d em 的 福 建省小流域 划 分 研 究 j . 地 球 信 息 科 学 , 2007, 9( 2 ) : 74 2951 4 5 6 7 5 结束语山地的准确定义 、山地范围的界定 、山地的精确分类一 直以来都是山地科学研究的一个难点 。本研究在地理信息系 统 ( g is)技术支持下 , 基于水文分析模型 , 通过

20、 d em 数据自 动提取山地相对高程的方法 , 对山地概念的定义 、山地分 类 、山地范围的界定等等有极其重要的借鉴作用 。目前 , 该 方法是提取山地相对高程最快 , 完全摆脱了人为因素的最有 效的方法 。该方法的科学性 、合理性和能否推广有待于对山 地本身形成机制作进一步研究以及实地验证和对比分析 。参考文献 8 9 10 11 12 1 祝 国 瑞 1 地 图 学 m . 武 汉 : 武 汉 大 学 出 版 社 ,2003: 42024211 13 江晓波 1中国山地范围界定的初步意见学报 , 2008, 26 ( 2 ) : 12921361 2 j . 山地re sea rch o

21、n ca lcu la t ion of m oun ta in re la t ive e leva t ion ba sed on hydro log ica l ana ly s isa b stra c t: moun ta in re la tive e leva tion is so sign ifican t in the ea rth system sc ience1a lso, its ca lcu la tion and extrac tion is an im 2 po rtan t sub jec t abou t geograp h ic info rm a tion

22、 sc ience, moun ta in sc ience and m app ing1b a sed on g is, th is p ap e r extrac ted moun ta in re l2 a tive e leva tion u sing d em da ta by the mode l of hyd ro logica l ana lysis1r e su lts show tha t th is m e thod no t on ly can extrac t moun ta in re la2 tive e leva tion ea sily and qu ick

23、ly, bu t a lso the re su lts a re sc ien tific and rea sonab le1 it is mo re impo rtan t tha t it p rovide s a new m e thod fo r ca lcu la ting and extrac ting moun ta in re la tive e leva tion and it is extrem e ly impo rtan t fo r defin ition of moun ta in range, the defin ition,c la ssifica tion

24、and con struc tion of d igita l moun ta in1key word s: moun ta in, moun ta in re la tive e leva tion, d em , g is, hyd ro logic ana lysisx ion g b o , ch en x ue2hua , l iu yan 2feng ( in stitu te of moun ta in h aza rd s a nd environm en t, ch ine se a cadem y of sc ience s chengdu 610041 , ch ina;

25、 gradua ted u n ive rsity of ch ine se a cadem y of sc ience s, b e ijing 100041, ch ina; chengdu ca rtograp h ic pub lish ing hou se ( ccph ) chengdu 610100 , ch ina; s ichuan bu reau of su rveying and m app ing, chengdu 610041, ch ina; sichuan p rovinc ia l comm ittee of po litica l sc ience and l

26、 aw, chengdu 610041 , ch ina)(上接第 83页 )杜丹蕾 , 陈学工 1 三角网中三角形集合的边界生成算法 j . 现 代 计 算 机 (专 业 版 ) , 2007 , 8: 18 219 , 261张献颖 , 周明全 , 耿国华 1 空间三角网格曲面的边 界 提 取 方 法 j . 中 国 图 像 图 形 学 报 , 2003, 8( 10 ) : 1223212261 6 卢朝阳 , 吴成柯 1任意多边形内带特征约束的散列数据的最优三角剖分 j . 计算机辅助设计与图形学学报 , 1997 , 9 ( 4 ) : 30223081 4 7 5 黄杏元 1地理信

27、息系统概论 m .出版社 , 20011北京 : 高等教育a m e thod of boun da ry ex tra c t ion for tr ian g le m e sha b stra c t: a cco rd ing to the triangu la tion da ta, the au tho r p ropo sed a new m e thod fo r bounda ry extrac tion1the p ropo sed a lgo rithm needed to bu ild the topo logica l re la tion sh ip be twee

28、n triangle s, ve rtice s and edge s, and then rea lized bounda ry extrac ting by u sing re2 cu rsion m e thod1the app roach rea lized like th is: th is m e thod u sed cyc lic p roce ss, firstly find ing an edge wh ich had on ly one ad jacency triangle in edge se t1the two extrem e po in ts of the edge we re u sed a s p reviou s and cu rren t po in t of po lygona l bounda ry1f ind