《拓扑多边形自动构建的一种快速算法》由会员分享，可在线阅读，更多相关《拓扑多边形自动构建的一种快速算法（5页珍藏版）》请在金锄头文库上搜索。
1、2 浙 江 测 绘 2 0 0 1 年 拓扑多边形 自动构建的一种快速算法 闫浩文祝方雄 ( 宁波市测绘设计研 究院 宁波 3 1 5 0 4 1 ) 摘要： 本文提 出了一种基 于方位角计算的多 边形快速构建算法， 很好地解决了拓扑 多边形构建 及“ 岛屿” 与“ 飞地” 处理问题。整个算法结构清晰 ， 简单易懂， 程序设计易于实现。 关键字： 方位角 多边形算法 1 前言 拓扑关系的存在是空 间数据区别于其它 数据的一个重要特征。空间数据拓扑关系的 构建是空 间数据库建立 的一项关键技术 ， 而 弧段一多边形拓扑关 系的建立又是其 中的难 点 ， 2 ， 。弧段一多边 形拓 扑关系 的建
2、立通 常有两种方法 ： 一是人工构建 ， 如美 国人 口调 查局的 DI ME系统 ； 二是 自动构建 ， 当前 GI S 开发多采用这种方法_ 5 ， 。 对拓扑多边 形的 自动构建算法 ， 学者们 的研究侧重点各异 ， 但基本都是从 自动化程 度、 时间效率 和算 法的复杂性 出发进行优化 与改进。早期的算法一般都离不开人工干预 ( 如输入内点 、 多边形编码等) ， ， ， 这对全 自动成图是不利的。文献 2 、 3 提 出 Qi 算 法在时间效率上 有了较大的改进 ， 自动化程 度也较高， 但时间效率仅体现在把 t g - 1 ( X ) 的 计算置换为 Q i 函数值 的计算 ， 而
3、多边 形搜 索 、 多边形拓扑关 系的确定基本沿用原来的 方法 。 本文提出了一种基于方位角定义的多边 形 自动构建方案 ， 其基本思路是 ： ( 1 ) 弧段邻 接关系的确定 ； ( 2 ) 弧段方位角计算 ； ( 3 ) 多边 形搜索 ； ( 4 ) 拓扑关系确定。该算法较之其它 算法的特点是 ： ( 1 ) 只进行 2 N( N为弧段数 ) 次方位角计算， 籍此就可以搜索出所有的多 边形 ； ( 2 ) 多边形拓扑关系的确定摈弃 了面积 的计算 ， 而借 助点与多边形 的包含关 系进行 判定； ( 3 ) 内点生成简便易行。实验及应用研 究表明， 该算法的时间效率较高 ， 思路清晰易 懂
4、 ， 程序实现的工作量较小。 2 方位角的计算方法 、 、 O 图1方位角及夹角计算 坐标 方位角 是测量 学 中的一个基 本 概 念 ， 是指从坐标 北方 向起顺 时针旋转 到某 一 射线的角度 。此处借用该 概念并规定 ： 把从 平面直角坐标系的 X轴正半轴起逆时针旋转 到某 一射线 的角度称 为该射线 的坐标 方位 角 ， 其取值范围为 0 。 一3 6 0 。 。 如有射线 A B， 其首端点为 A( x A ， Y A ) ， 其 上另一点 B( x B ， Y B ) ， 坐标方位角用 U A B 表示 ， 则 a A B 可按照下式计算 ： Dx - =XBXA； D = Y B
5、 Y A； 2期 闰浩文等 ： 拓扑 多边形 自动构建的一种快速算法 3 1 ) 若 D =0 ， Dv 0则 a A B =9 0 。 ； 2 ) 若 D x = 0 ， D y 0 ， D y =0则 =a r c t g ( D D , ) ； 4 ) 若D x 0 ， D y =q 2 ， 2 ：Q l e t 2 ； 若 a l x P 1 且 X P XP 2 ， n u m不变 ； 否则 n u m加 1 。 表3 修正后的弧段与多边形拓扑关联表 弧段号 多边形编号 -1 ， 3， 2 1 2 ，一5 ，4 2 -3 ，一6 ，5 3 -7 4 图5 多边形包含关 系判断示例 (
6、 3 ) 多边形 与 内点 的拓 扑包含关 系的确 定 内点是在多边形内填充颜色、 图案 、 符号 的根据。若数字化时已为多边形生成 了内点 文件 ， 则按 照铅 垂线 内点 匹配法建立 多边形 与内点 的拓扑包含关系表 。否则 ， 要 用程序 自动生成 内点 。用程序 自动生成 内点 的方法 是 ： 在多边形上任取一条线段的中点 P ( XY) 。 然后生成 四点 ： P 1 ( x一1 ， Y) ， P 2 ( X十1 ， Y) ， P 3 ( x， Y一1 ) ， 1 4 ( x， Y+1 ) ， 用铅垂线 内点法判 断 ， 至少有一点在 多边 形 内。此点 即为多边 形的一个 内点。
7、6 试验与结论 多边形的构建是地理数据拓扑关 系建立 ( 下转第 1 0页 ) 1 0 浙 江 测 绘 2 0 0 1 正 幅地形 图， 用户 可以根据需要提取 任何 区域 任何形状的地形 图打印输出。 7 结束语 通过对杭州市滨江地 区航测数字化地形 图的转换和入库， 证明该系统采用的技术路 线是切实可行的。系统的建成进一步提高了 我院在数字化地形 图的生产、 管 理的开发应 用等各个方面的技术水平和能力 ， 同时也大 大提高了工作效率。 在将基础地形 图入库 的基 础上， 根据我 ( 上接第 5页) 的难点之一 ， 其算法的 自动化、 速度和复杂性 一直制约着 GI S与 电子地 图中有关
8、模块 的设 计开发。由上 述可知 ， 本 文提出 的基 于方位 角计算的多边形构建算法较之与常规法有下 面的优点 ： ( 1 ) 不用人工干预 ， 实现 了完全 自 动化 ； ( 2 ) 只进行 2 N( N为弧段个数 ) 次角度 计算 ， 其它基本为加减运算和逻辑运算 ， 故速 度较快 ； ( 3 ) 对弧段拓扑邻接关系表进行一次 搜索即生成 2 N个多边形， 消除多余多边形后 可方便地确定了多边形拓扑关系， 这样使“ 岛 屿” 与“ 飞地” 问题得到解决， 并使整个算法结 构简单 清晰。本 算 法在 Wi n d o ws 9 5支持 的 B o r l a n d C+ +( V 5 0
9、 ) 下编 程实现。实 验证 明， 对于有 7 4个单元 的某省行政 图， 构 建多 边形约需 4秒种 ， 对 于有 3 1个单元的某 国行 院生产的实际需要还将进一步把杭州市管线 数据和地质数据叠加 到该 系统上 ， 充分发挥 该系统的功能 ， 以创造 出更大 的社会效益和 经济效益。 参考文献 1 城市地理信息系统 ， 修文群等编著， 北京 希 望出版社 ， 1 9 9 9年。 2 J ( OI S地理信息系统原理和方法 ， 边馥苓主 编 ， 测绘 出版社 ， 1 9 9 6年。 3 省、 市、 县区域规划与管理信息系统规范化 研究 ， 黄杏元等著。 政略图， 构建多边形约需 2秒钟。 参
10、考文献 ： 1 陈春 张树文 徐佳芬 GI S中多边形图拓扑 信息生成的数学基础 测绘学报 ， 1 9 9 6 ， 2 5 ( 3 ) ： 2 6 6 2 7 1 2 】 齐华 刘文熙 建立结点上弧弧拓扑关系 的 Q ； 算法 测绘学报， 1 9 9 6 ， 2 5 ( 3 ) ： 2 3 3 -2 3 5 3 齐华 自动建立多边形拓扑关系算法步骤的 优化与改进 测绘学报 ， 1 9 9 7 ， 2 6 ( 3 ) ： 2 5 4 -2 6 0 ( 4 杜清运 地图数据库中多边形数据的自动组 织 测绘学报 ， 1 9 8 9 ， ( 3 ) ： 2 0 2 2 1 2 5 张超 陈丙咸 邬伦 地理信息系统 北京： 高 等教育出版社 ， 1 9 9 5 ： 1 1 0 ( 6 J 徐庆荣 杜道生 黄伟等 计算机地图原理 武 汉： 武汉测绘科技大学出版社。 1 9 9 3 ： 1 5 5 1 6 5 7 杨海宏 李天宏 薛安 利用双邻点判断法优 化拓扑关系自动生成算法， 中国图象图形学报， 1 9 9 8 ( 7 ) ： 5 8 4 5 8 7
