全 文 ：第 5 卷 第 4 期
1 9 9 2 年 S JJ
林 业 科 学研 究
FO R E S T R E S E A R C ll
V o l
。
}
A u g
. ,
,
N o
.
4
1 9 9 2
, 二二 一二二二丁 二二二 二二二二二二二二二二二二亡 : 二 = :
地理信息系统中多边形叠合算法的研究 ”‘
高显连 杨国勇 孟献策 田永林
(中国林业科学研究院资源信息研究所 )
摘要 本文探讨的多边形叠合算法是在开发牡 丹江林管局信息管理系统时提出并完成的 。 结
果表明 : 采用将两幅专题图并成一张新图 , 重建空 间数据之问的拓扑关系 , 重新生成多边形 , 重
新 生成 标 志 点 , 并利用标志点进行属性回填的方法 , 可圆满解决专题图叠 合后拓扑关系复杂 、
属性不易 回填的问题 , 成功地实现两幅专题地图的叠合 。
关 . 词 地理信息系统 多边形受合 多边形 生成 标志点判别 属性 回填
地理信息系统 又称空间数据管理 系统 , 是目前因际 上计算机应用领域中较为 活 跃 的 部
分 , 广泛应用于地质 、 地理 、 环境等科学领域 , 及林业 、 农业 、 水利等国民经济部门 。 在资
源清杏 、 城 乡规划 、 灾害监测 、 宏观决策 、 地籍管理等方面 , 地理信息系统 已得到十分成功
的应用 。 地图图形信息的采集、 存贮、 处皿在地理信息系统和专题制图中有着重要的作用。
地理信息系统通过图形数字化 , 将森林分布 、 土地利用现状、 _ f. 壤类型、 行政区划 、 水系、
道路 、 居民点等专题图形信息变成计算机的内部表示 , 在此基础上进行图形的多种操作 , 如
把相邻的两幅相 !司专题类型的图拼接成一幅图 , 对某一区域进行剪裁 , 或进行多 条 件 查询
等 。 本文重点讨论图形操作中的多边形叠合操作的算法。
1 空间数据的数据结构和文件结构
一专题地图所表示的空间实体可分为三种形式 : l衍状 、 线状 、 点状 。 例如林相图是面状要
素 , 叮称之为多边形结构的专题图 。 交通或水系图为线状结构的专题图 , 居民点等为点状结
构的专题图 。 各种空间图形要素之 间均存在拓
扑关系, 这主要指 :
拓扑邻接 : 指存在于空间图形的同类元素
之间的拓寸卜关系。 例如结点邻接关 系 N , / N Z ,
N
,
/ N
‘,
N
3
/ N
‘⋯ ⋯ 。
拓扑关联 : 存在于空间图形的不 同元素之
间的拓扑关系 。例如结点与弧段的关联关系 N ;
/ C
, 、
C
s 、
C
。 ,
N
Z
/ C
: 、
C
: 、
C
。, ⋯ ⋯ 。
拓扑包含 : 存在寸“空介d图形的同类 、 似不
同级的元素之 间的拓于卜关系 , 如 P Z 包含 尸‘ 等 。 图 1 空 间敌据的拓扑关系
19 9 2 一 0 3 一 2 0收稿 。
仁l: 林改 己代1甲J ri守 王见 l一长入 少二{了J 研它 {} Ii] 女练 店公听 声、 工 智能宝全体卜l仁 l白大力支打 , 在此丧示子谢 L
4 期 高显连等: 地理信息系统中多边形叠合算法的研究
在具体实现中 , 对不同的空间实体作分层次存贮 , 对点状图记录其地理位置 和 属 性 信
息。 对线状图记录线的起始点和终止点 , 线段起点和终点之间的多个中间点(称为折点 )。 线
段起点或终点又称为结 点, 每个结点的图形信息包括该点的地理位置 , 与谈结点相连接的线
段 。 对线状图还要记录各线的属性信息。 对面状图除了记录线状图的图形信息外 , 还要包括
每个多边形的组成线段 , 多边形的属性信息 , 多边形的面积 , 多边形中线段的左右多边形信
息 , 多边形的标志点(内点) , 以及多边形内包含的子多边形(岛多边形 )等图形信息。
由丁实际中的一幅专题图可能包含点线面的全部信息 , 所以要对依层次存贮的图形进行
叠合 , 不同类型的专题图之间有时也需要叠加 , 例如林相图与土壤图的叠合。 各种叠合操作
包括 : 点与点 , 线与线 , 面与面 , 点与线 , 点与面 , 线与面等 , 其中最复杂的操作是面与面
(多边形与多边形 )的叠合。
2 面状图与面状图的叠合操作
叠合操作的前提 , 是两幅图控制在相 同的地理范围内 , 如果两幅图的比例尺不一样 , 应
先进行预处理 , 使两幅图的数据得到匹配 。 叠合算法的基本思想是 : 假设有两幅 图(图 形 1
与图形 2 ), 先将两幅图的数据组织到一张新图上 , 然后建立新图的拓扑关系 , 重新生成多边
形和标志点(内点) , 利用标志点进行属性回填 。 现将该算法分别解释如下 。
2
.
1 新图的建立
(1) 将图形 1 的数据复制到新图 。
(2 ) 以(l) 建立的新图为基本图 , 将图形 2 的数据作相应的处理 。 如图形 2 中 , 表示线段
起始位置的数据需加以改变 , 同时由于图形 2 与图形 1 的结点可能重合 , 所以还应做结点的
重合处理。 将处理后图形 2 的数据添加到新图中。
2
.
2 新图重建拓扑关系
由于图形 1 与图形 2 各自的拓扑关系在叠合前 已经建立 , 故只需考虑图形 1 与图形 2 之
间可能产生的新拓扑关系即可。 图形 1 与图形 2 之间拓扑关系的建立 , 可简化为图形 1 中的
一条线段与图形 2 建立拓扑关系的重复 。 判断图形 1 的一条线段可能与图形 2 的哪些线段相
交 , 一条线段的所有点(结点 , 折点 )的最大最小(x , 砂坐标确定了该线段的范围 , 因为两条
线段相交的必要条件是它们的范围必须重叠 , 所以利用线段范围的比较 , 可以排除大部分无
关的线段 。 图 2 中A B 线段为图形 1 中的线段 , CD 为图形 2 中的线段 , 当两条线段 相交时
交点为 O , 则在图形 1 中 AB 由A O 取代 , 同时添加 O B 线段 , 即将 A B 分成 AO 与O B 两条
线段 , 图形 2 中的 C D 线段也作相应的处理 。 两条线段相交 , 产生了 4 条线段 和 1 个结点。
AO 线段继续与图形 “中的线段比较 , 井过程一直重复下去 , 直到图形 1 中的所有线 段都处理完 , 新的拓扑关系建立完毕 。 可能出现的复杂情况是相交的两条线段有重叠(图 3 ) , 处理
的方法是将 AB 分成A E 、 刀尸、 FB , 将 C D 分成 CE, 、 E, F, 、 F, D 。 由于 刀F 与 E’F’ 是 两条
重叠的线段 , 所以删掉其中的一条线段 E, F, , 则 A B 与 c 刀 相交 , 最 终 产 生 了 A E 、 EF 、
FB
、
CE,
、
F, D S条线段和 2 个结点。 这一步只是建立了点线之间的拓扑关系 , 涉及到面的
拓扑关系则 由下一步骤完成。
2
.
3 多边形生成的算法
所谓多边形的生成就是而的生成 , 生立与面有关的拓扑关系。 将顺时针方向定为多边形
林 业 科 学 研 究 5 卷
少< ’
l月2 线段相交 图 3 相交的两条线段有重亚
的方向 , 对某一线段递归地求其后继线段 , 直到某线段的后继线段为最初的开始线段 , 就得
到一个多边形及其组成线段的图形信息。 与每条线段相连的后继线段有两条 , 一是与该线段
的起点相连的线段 , 另一条是与该线段的终点相连接的线段 。 对一幅专题图的所有线段都作
上述处理后 , 新图中涉及到面的拓扑关系也就建立起来了 。 对于岛多边形要做一 些 特 别 处
理 , 不但要生成该岛的多边形 , 还要生成包括该岛的主多边形 。 包围该岛的多边形中最里面
的一个多边形定义为该岛的主多边形 (图 4 )。算法的具体过程是 : ¹ 对每个结点所连的线段 ,
按其出入该点时与x 轴的夹角从小到大排序。 º 求每条线段的后继线段 , 即线段 起 点 或 终
点上 , 比该线段方位角大的线段中方位角最小的一个线段 。 » 对每条线段 , 递归地求其后继
线段 , 得到组成一个多边形的所有边 。 ¼处理岛多边形的情况 , 求多边形面积 , 填写多边形
文件 , 并填写线段的左右多边形信息。
2 . 4 标志点生成的算法
标志点是指多边形内的一点 , 它具有如下性质 : 如果一个点是某一多边形的标志点 , 则它
就不是另一多边形的标志点 , 因此标志点只能在多边形内 , 而不可能在边界上 。 2 。 3节中生成
的多边形包含多边形的范围信息 , 设 尸为生成的某个多边形 , M a x , 为 p 中坐标点(x , 妇的 ,
最大值 , M i n 梦为 P 中坐标点( x , 夕) 的 , 最小值 , 作水平线 y = M i n 夕 + l / 2 (M a x 刀一 M i n 夕) ,
则该线必与 p 有两个交点 (图 5 ) , 令 x = x ; + l/ 2( x 2 一 x : ) , 则 (x , 妇即为多边形 p 的标志点。
O 交、
、、 、_ ~
,产 / 、
盯一 月X 、
·分户钾 1尸 ,图 4 岛多边形 图 5 求多边形的标志点
较 为复杂的情况是所作的水平线可能与多边形的一条或几条线段重叠 , 或者与多边形有多个
交点 , 但对算法稍做细化 , 问题即可解决 。 图 6 表示了几种较复杂的情况 。
2 · s 标志点的列别算法
判断一个点是否为 一多边形的标志点 , 可先判断该点是否在组成该多边形的线段上 , 即是
否在该多边形的边界_ L 。 如果在多边形的边界土 , 则该点不是该多边形的标志点。在判别时 ,
盛期 高显连等 : 地理信息系统中多边形叠合算法的研究
/ 一、
’ 火一2 爪八{⋯图 6 标志点的特例情况
利用线段范围来确定线段是否可能与该点重合 , 可大大减少判别工作量 。 当确定该点不在多
边形边界上时 , 可用图 7 所示的铅锤线法来判别 。 具体做法是: 作通过该点的 Y 轴平行线 ,
计算出该线段与要判别多边形的交点 , 如交点为偶数, 则不是该多边形的标志点 , 如果是奇
数 , 则是该多边形的标志点。 要考虑的复杂情况是可能出现线段的重叠 , 或交点与多边形的
凸凹有关的情况 。
2. ‘ 月性回坟
所谓属性回填是指建立起来的新图应具有图形 l与图形 2 的属性 。 例如土壤图与森林分
布图叠合 , 生成新图的任一个多边形应同时具有土壤种类和树种的信息。 图形 1 中的一个多
边形与图形 2 中的一个多边形叠合到一起 , 假设其相交生成了三个新面(图 8 ) , 这三个新面
的属性可通过判断标志点来确定。 例如A 多边形与 B 多边形相交生成 A, 、 了 、 O 三个面 , 在
判断 A ‘面时 , 如 A 尹 的标志点也可以作 A 的标志点 , 则 A ‘应包含A 的属性信息 , 当 A 产的标
志点也可以作 B 的标志点时, 则 A 产中也应包含 B 的属性信息。 对新图中所有的多边 形 都作
上面的处理后 , 则可将图形 1 与图形 2 中所有信息都回填到新图中去 , 至此 , 图形 1 与图形
2 相叠合所产生的一张新图就建立起来了。
皿
目 7 用铅睡线法进行标 志点到别 困 8 面相交
3 分析与讨论
评价地理信息系统中算法的优劣 , 主要是看运用算法解决实际问题时所占用的时间与空
间资源的多少 。 本文所讨论的算法 , 实际运行中只增加了叠合后的新图数据文件所占用的空
间, 及少量临时文件所占用的空间, 故在此不讨论算法的空间参数 , 只 对 时 间参 数 进 行
分析 。
专题图叠合所耗费的时间主要是对数据文件进行读写操作的时间。 现假设图 形 1 包 含
m : 条线、 , : 个结点、 s : 个多边形 ; 图形 2 包含 m : 条线、 。: 个结点、 s : 个多边形 ; 新图包含
“ 6 林 业 科 学 研 究 5 卷
。 : 条线 、 , 3 个结点、 : 3 个多边形 , 现对算法的各步骤分别讨论如下 :
(1) 建 立 新图时 , 必须先调整图形 2 的线段号和结点号 , 需要对图形 2 的线段文 件 和
结点文件各遍历两次 , 即要访问2 二 : 条线段记录和 Z n : 条结点记录 。 处理结点重合时 , 对图
形 1 的每个结点都要进行考虑 , 最差情况是对图形 2 的结点文件遍历 : , 次 , 即共要访问 : : +
” , X ”2 条记录 。
(2) 重建拓扑关系时 , 如果最终建立的新 图有 二 : 条线段 , 那么图形 1 与图 形 2 相 结合
就要新产生 m 。 一 。 : 一 二 : 条线段 。 设图形 1 产生了 K : 条新线段 , 图形 2 产生了 kZ 条 新线段 ,
则 否1 + 无2 = 。。一 。 , 一 。 : , 那么至少要访问(k , + 二 , ) K (1 + k : + m : )条线段记录 。 对 侮个产生的
新结点 , 要考虑是否是旧结点的情况 , 因此要对新图结点文件进行访问。
(3) 生成多边形时 , 先对结点文件所连线段进行排序 , 需访问2 。 : 条线段记 录 和 n , 条
结点记录 。 每条线段均存在左右多边形 , 当多边形生成完时 , 每条线段又被访间了 2 次 , 同
时要生成多边形文件和多边形的组成边文件 , 相当于对这两个文件各遍历一次。
(4) 生成标志点时 , 对每个多边形的组成边 , 均要访问一次 , 同时对每相应边 (可 能 与
水平线相交的边 )的坐标文件也要进行访问 , 以求出水平线与多边形的两个交点, 总共 要 访
问2二 : 条线段记录和 s : 条多边形记录 。
(5) 判断一个点是哪个多边形的标志点, 要访 问多边形文件 , 平均要访问1 / 2s : 条多边形
记录 。 若可能是某一多边形的标志点, 则要访 间该多边形的所有边以便判断 , 对符合范围要
求的边还要访问坐标文件 , 以便确定交点。
(6 ) 回填属性时 , 由于新图的每个多边形的属性均要回填 , 即要判断出每个多边形在图
形 1 与图形 2 内的属性情况 , 平均要访问1 / Zs3 x (s : + s : + 2) 条多边形记录 。
S to d 夕 o n A lg o r is 。: jo r P o l夕夕。 , : O v e r la夕 i, :
G e o g r a Phie In fo
r ,二a tio n
.兮夕s te 。, (G l , g )
G a o X ia n lia zl Y a n g G u o y o n g M e n g X ia n e e T ia n Y o n g lin
T he R es e a r e h I o s rfr: : te o f F
o r e s t R e s o u r e e s l , f
o r m a tio , T e c h 。‘, u o C A F )
A b strac t T his Pa Pe r d is e u ss e s the a lg o r ism fo r Po lyg o t o v e r la y
.
T h e
r e su lt sh o w s : T h e P r o b le m o f e o m P lie a te d to Po lo g y r e la t io n a fte r e o v e r a g e
o ve r lay a n d d iffie u lty o f fe a tu r e a t tr ib u te r efillin g e a n e a s ily be r e s o lve d
in the w a y o f m e rg in g tw o m a P in to a n ew o n e
, r e g e n e r a tin g the to Po lo g y
r e la tio n o f sPa tia l d a ta
, r e g e n e ra t in g Po lyg o n s
, r e g e n e r a t in g la b e l Po in t3
:、n d r e fillin g fe a tu r e a t tr ib u te w ith lab e l Po in ts 。 T he e o ve r a g e o v e r lay e a n
b e im Plem e n te d s u e e e s sfu lly
。
K e y w o r d s g e o g r a Ph ie in fo rm a t io n sys tem Po ly g o n o v e r la y Po lyg o n
g e n e r a tio n la b e l Po in t ju d g in g fe a tu r e a tt r ibu te fillin g