c语言拓扑多边形自动生成,拓扑多边形自动构建的一种快速算法.pdf

c语言拓扑多边形自动生成,拓扑多边形自动构建的一种快速算法.pdf

拓扑多边形自动构建的一种快速算法

2 浙 江 测 绘 2001年

拓扑多边形 自动构建的一种快速算法

闫浩文 祝方雄

(宁波市测绘设计研究院 宁波 315041)

摘要：本文提 出了一种基于方位角计算的多 次方位角计算，籍此就可以搜索出所有的多

边形快速构建算法，很好地解决了拓扑多边形构建 边形；(2)多边形拓扑关系的确定摈弃了面积

及 “岛屿”与 “飞地”处理问题。整个算法结构清晰， 的计算，而借助点与多边形的包含关系进行

简单易懂，程序设计易于实现。 判定；(3)内点生成简便易行。实验及应用研

关键字：方位角 多边形 算法 究表明，该算法的时间效率较高，思路清晰易

1 前言 懂，程序实现的工作量较小。

拓扑关系的存在是空间数据区别于其它 2 方位角的计算方法

数据的一个重要特征。空间数据拓扑关系的

构建是空间数据库建立的一项关键技术，而

弧段一多边形拓扑关系的建立又是其 中的难 、

点[，2，。弧段一多边形拓扑关系的建立通

常有两种方法：一是人工构建，如美 国人 口调

查局的DIME系统；二是 自动构建，当前GIS ＼

开发多采用这种方法_5，。

＼ 、

对拓扑多边形的 自动构建算法，学者们 O

的研究侧重点各异，但基本都是从 自动化程

度、时间效率和算法的复杂性出发进行优化

图1方位角及夹角计算

与改进。早期的算法一般都离不开人工干预

(如输入内点、多边形编码等)[，·，，这对全

自动成图是不利的。文献[2]、[3]提出Qi算 坐标方位角是测量学中的一个基本概

法在时间效率上有了较大的改进 ，自动化程 念 ，是指从坐标北方 向起顺时针旋转到某一

度也较高，但时间效率仅体现在把 tg-1(X)的 射线的角度 。此处借用该概念并规定：把从

计算置换为 Qi函数值的计算，而多边形搜 平面直角坐标系的X轴正半轴起逆时针旋转

索、多边形拓扑关系的确定基本沿用原来的 到某一射线的角度称为该射线的坐标方位

方法 。 角，其取值范围为 0。一360。。

本文提出了一种基于方位角定义的多边 如有射线AB，其首端点为A(xA，YA)，其

形 自动构建方案，其基本思路是：(1)弧段邻 上另一点B(xB，YB)，坐标方位角用UAB表示，

接关系的确定；(2)弧段方位角计算；(3)多边 则 aAB可按照下式计算：

形搜索；(4)拓扑关系确定。该算法较之其它 Dx-=XB—XA； ’

算法的特点是：(1)只进行 2N(N为弧段数) D =YB—YA；

2期 闰浩文等：拓扑多边形 自动构建的一种快速算法 3

1)若D=0，Dv>0则aAB=90。； 段构成了一个多边形。同样，从 A1的0端开

2)若Dx=0，Dy<0则 =270。； 始，并把它作为中止弧段，把与它拓扑关联的

3)若Dx>0，Dy>=0则 =arctg