基于树的等高线空间关系表达与计算.pdf

第3 4 卷第5 期 “ 2 0 0 5 年9 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y V 0 1 ．3 4N o ．5 S e p ．2 0 0 5 文章编号1 0 0 0 1 9 6 4 2 0 0 5 0 5 - 0 5 7 0 0 4 基于树的等高线空间关系表达与计算 乔朝飞1 ，陈军2 ，赵仁亮2 ，陈云浩1 ，李京1 1 ．北京师范大学资源学院，北京1 0 0 8 7 5 ；2 ．国家基础地理信息中心，北京1 0 0 0 4 4 摘要地形图上等高线相互之间的空间关系是人们分析地形的重要依据，也是利用G I S 模拟人 类地形图认知能力的一个重要出发点．根据空间关系理论，将等高线空间关系分为多阶包含、并 列和多阶相离三类，认为这些空间关系用树结构表达最为适宜．利用等高线树中结点的道路长度 与层数之间的关联，设计了一种计算等高线三种空间关系的方法． 关键词等高线；空间关系；图论；等高线树；空间关系计算 中图分类号P2 0 8文献标识码A T r e e B a s e dR e p r e s e n t a t i o na n dC o m p u t a t i o no f S p a t i a lR e l a t i o n so fT o p o g r a p h i cC o n t o u rL i n e s Q I A OC h a o f e i l ，C H E NJ u n 2 ，Z H A OR e n l i a n 9 2 ，C H E NY u n h a 0 1 ，L IJ i n 9 1 1 ．C o l l e g eo fR e s o u r c e sS c i e n c ea n dT e c h n o l o g y ，B e i j i n gN o r m a lU n i v e r s i t y ，B e i j i n g1 0 0 8 7 5 ，C h i n a ； 2 ．N a t i o n a lG e o m a t i c sC e n t e ro fC h i n a ，B e i j i n g1 0 0 0 4 4 ，C h i n a A b s t r a c t T h es p a t i a lr e l a t i o n so ft o p o g r a p h i cc o n t o u rl i n e sp l a yi m p o r t a n tr o l e si nl a n d f o r ma n a l y s i s a n da r ea l s oak e yf a c t o r o fu s i n gt oG I Ss i m u l a t eh u m a n ’Sa b i l i t yo fc o g n i z i n gt o p o g r a p h i cm a p ． B a s e do ns p a t i a lr e l a t i o nt h e o r y ．t h es p a t i a lr e l a t i o n so fc o n t o u r1 i n e sa r ed e f i n e da sm u l t i o r d e r e n c l o s u r er e l a t i o n ，p a r a t a x i sr e l a t i o n ，a n dm u l t i o r d e rd i s j o i n t i n gr e l a t i o n ．T h ea u t h o r sh o l d t h a t t r e es t r u c t u r ei St h em o s ts u i t a b l et o o lf o rr e p r e s e n t i n gt h e s er e l a t i o n s ．B a s e do nt h ea s s o c i a t i o n b e t w e e nt h el e n g t ho ft h ep a t hf r o mo n en o d et oa n o t h e ra n dt h el e v e lo fn o d e s ．an e wm e t h o df o r c o m p u t i n gs p a t i a lr e l a t i o n so fc o n t o u rl i n e si sg i v e no u t ． K e yw o r d s c o n t o u rl i n e ；s p a t i a lr e l a t i o n ；g r a p ht h e o r y ；c o n t o u rt r e e ；c o m p u t a t i o no fs p a t i a l r e l a t i o n S 众所周知，等高线在人们阅读模拟地形图的过 程中发挥着重要作用．人类可以直接识别与记忆模 拟地形图上等高线的空间关系，但计算机却难以做 到，因为它是靠几何坐标来记忆、存贮空间实体的 位置．因此，研究如何在计算机环境下有效的描述、 表达等高线空间关系，并建立可执行的计算方法与 模型，从而使计算机能够模拟人们认知等高线空间 关系的能力，就成为发展数字地形图认知中所要面 对的一个重要课题[ 1 - 5 ] ．本文拟从地形图空间认知 收稿日期 基金项目 作者简介 通讯作者 的需求出发，探讨等高线空间关系的内涵、在计算 机中如何表达及计算等问题． 1等高线空间关系描述 在将等高线空间关系用计算机表达之前，首先 需对其进行描述和分类．等高线本身是线对象，然 而，其限定的面上亦提供一定信息量．事实上，人们 在阅读等高线图时，往往是不自觉地将其视为面， 利用它们之间的相互嵌套关系来分析地表形态．显 2 0 0 4 1 1 一0 5 国家杰出青年科学基金 4 0 0 2 5 1 0 1 ；国家自然科学基金 4 0 3 0 1 0 4 2 } 高等学校博士学科点专项科研基金 2 0 0 3 0 0 2 7 0 1 4 乔朝飞 1 9 7 4 一 ，男，河南省清丰县人，博士后，从事G I S 中空间关系理论及应用的研究． 陈云浩 c y h b n u ．e d u ．c n 万方数据 第5 期乔朝飞等基于树的等高线空间关系表达与计算 然，在分析等高线空间关系时，应该顾及人们对等 高线图认知的这一习惯．此外，等高线是以成组的 方式来表达地表形态的，具有群组特性．因此，研究 等高线空间关系就应该将其视为群目标处理．在深 入分析等高线的几何特性的基础上，笔者将等高线 空间关系分为三类多阶包含关系、并列关系和多 阶相离关系[ 1 ] ． 对于地形图上的两条等高线，如果二者包含的 区域有公共部分，且二者之间存在k 志一1 ，2 ，⋯ 条等高线，则称它们为五 1 阶包含关系，或称外围 等高线尼 1 阶包含内层等高线，称忌 1 为包含阶 数．当包含阶数为1 时，称二者为直接包含关系． 例如，在图1 中，共有1 3 条等高线．其中，等高 线厶位于最外围，包含其它等高线．然而，厶与其 它等高线之间的包含关系的阶数是不同的．其与等 高线L 。、厶、L 。为1 阶包含关系 直接包含关系 ， 与等高线厶、厶、L ，、L 。、上q ，则为2 阶包含关系． 图1 一幅等高线图 F i g ．1 O n ec o n t o u rm a p 4 0 0 ，5 0 0 为高程；L l ～L 1 3 为等高线标识号 一条等高线可能包含若干层等高线，我们称其 包含的首层等高线为此等高线的“子等高线”．这些 子等高线之间互为并列关系[ 2 ] ．具有并列关系的两 条等高线的特点是二者所包含的区域没有公共部 分，且同时被一条等高线1 阶包含．例如，在图1 中，等高线L 。的3 条子等高线L 。，厶，L 。之间均为 并列关系． 并列关系只存在于一条等高线的子等高线之 间，对于其它非并列和包含的等高线，其相互间具 有多阶相离关系，即如果两条等高线包含的区域没 有公共部分，且未同时被一条等高线l 阶包含，它 们之间至少有k 条等高线将其分隔，则称二者为k 阶相离关系，称k 为相离阶数．例如，在图1 中，等 高线厶和厶。之间有厶，L ，，和厶。隔断，因此为3 阶相离关系． 2 树型表达 显然，有经验的操作员可以较容易的识别上述 等高线空间关系．然而，若要让计算机来进行自动 识别，前提之一是须将等高线空间关系进行形式化 表达．综观现有文献，在许多基于等高线图的应用 中，通常是利用图论中的树结构来表达等高线空间 关系．等高线树 c o n t o u rt r e e 是由B o y e l l 和R u s t o n 首先提出睇] ，根据等高线图形的分布特点和高程信 息而建立的一种树形结构，反映了等高线之间的空 问关系及相对高差等信息∞1 ] ． 在确定等高线树的组成要素结点和边时， 不同的学者采用不同的策略．概括的讲，等高线树 可分三类表现形式u j 1 内部区域结点法等高线内部区域作为结 点，等高线作为边； 2 等高线加区域结点法等高线及其内部区 域均作为结点； 3 等高线结点法等高线及其包含区域作，为 结点、包含关系作为边． 在实际应用中，生成哪一类树结构要看具体的 需求．比较而言，第3 种形式显式地表达了等高线 空间关系，而且数据结构简单．对于图1 中的等高 线，其相互间的空间关系可用结点法表示如图2 ． 图2图1 中等高线空间关系的树结构表达 F i g ．2 T r e er e p r e s e n t a t i o no ft h es p a t i a lr e l a t i o n s a m o n gc o n t o u r ss h o w ni nF i g ．1 在图2 中，1 3 个结点分别代表1 3 条等高线． 其中，等高线厶为树的“根结点”，它有3 个孩子结 点 o f f s p r i n g s 等高线L 。，L 。，厶，这些结点彼此之 间为“兄弟结点 s i b l i n g s ”． 等高线树中任一结点的“度 d e g r e e ”是所有 与此结点相连的边的个数．结点秽的度记作d e g r e e 口 ．每个结点的度等于此结点的邻近结点个数． 以结点可为起点的边的数目叫做口的出度 o u t d e g r e e ，记作d e g 秽 ；以结点u 为终点的边 万方数据 中国矿业大学学报第3 4 卷 的数目叫做口的入度 i n d e g r e e ，记作d e g 可 ． 等高线树的一条“路径 w a l k ”是一个结点和 边的交替序列卢一u 。e l 可1 P 2 ⋯可。一1 如口。，使对1 ≤i ≤恕， 毋的端点是可卜1 和口，．口。和剐。分别称为路径卢的起 点和终点，∥中边的数目，z 称为它的长． 等高线树中任一结点的“层 1 e v e l ”是从根结 点到此结点的边的个数．结点口的层记作l e v e l v ． 3计算方法 3 ．1原理 地图要素空间关系必须在一定的计算模型中 被形式化，才能被计算机所“认知”[ 8 ] ．等高线作为 一类重要的地图要素，本质上是一种集群目标，在 计算其空间关系时，需充分考虑到这一特点．等高 线树是表达等高线空间关系的良好结构，将地形图 上的等高线全部联系起来，人们可从树中推导出任 意两条等高线之间的空间关系．因此，我们可以图 论为指导，在等高线树基础上发展等高线空间关系 的计算方法． 由于等高线空间关系计算模型将在树的基础 上构建，因此应从分析树中结点之间的关系人手． 我们以图1 和图2 中的等高线及其树结构为例进 行分析． 首先分析多阶包含关系．对比图1 和图2 可看 出，具有k 阶包含关系的等高线结点在树中具有如 下特点1 位于不同的层，且层数之差等于包含阶 数；2 结点之间的路径长度等于层数之差．如等高 线厶与厶。为4 阶包含关系，它们对应的结点位于 不同的层，层数差为4 ．同时，二者之间的路径长度 为4 ，等于层数之差．由此可以推知，如果等高线树 中两个结点之间的路径长度等于二者的层数之差， 则说明它们对应的等高线为多阶包含关系． 其次分析并列关系．在等高线树中，那些父结 点相同的结点之间即是并列关系．例如，从图2 ，L 。 与L 。互相为并列关系，二者位于树的同一层，而且 由于它们均和父结点之问有一条边相连，因此二者 之间的路径长度为2 ．由此，层数相等且路径长度 为2 即可作为判断并列关系的依据． 需指出的是，虽然具有并列关系的结点的层数 相等，但层数相等的结点之间却并不一定是并列关 系，只有那些父结点相同的结点之间才是并列关 系．例如，L 。与L 。，的层数相等，但是它们的父结点 不同，因而不是并列关系，事实上，那些层数相等但 是父结点不同的结点之间是多阶相离关系． 最后分析多阶相离关系．首先，具备多阶相离 关系的等高线之间的路径长度都大于2 ，否则二者 就为直接包含关系或并列关系．其次，它们的层数 可能相同 如L 。和L 。。 ，也可能不同 如上。和 L ，。 ．当层数相同时，层数之差为0 ，而显然它们之 间的路径长度不等于0 ．当层数不同时，它们之间 的路径长度亦不等于层数之差．因此，路径长度不 等于层数之差可作为判断多阶相离关系的一个必 要条件． 最后，需判断相离阶数的大小．根据定义，等高 线A 和B 之间的相离阶数是它们之间所间隔的等 高线的个数．设两条等高线4 和B 具备多阶相离 关系，它们虽然未被同一等高线所直接包含，但是 总能找到一条等高线c ，同时包含4 和B ．在通过 计算路径长度来计算A 和B 的相离阶数时，路径 经过结点C ，长度为2 ，显然，这一个值是应该去除 的．即A 到B 的路径长度比A 和B 之间的相离阶 数多2 ．由此可知，具备多阶相离关系的结点的相 离阶数等于它们之间的路径长度减去2 ． 3 ．2 算法 综上所述，我们可以利用等高线树中结点的2 个参数结点之间的路径长度与层数，设计计算3 种等高线空间关系的算法，如图3 所示． 图3 判断等高线树中2 个结点关系的流程 F i g ．3 F l o wc h a r to fc o m p u t i n gs p a t i a lr e l a t i o n s o fc o n t o u rl i n et r e e 本文中所设计的运用等高线树计算等高线空 间关系的算法，可以很容易的在计算机中编程实 现，应用于需计算等高线空间关系的各种地形分析 中． 从方法的使用效率看，基于树结构的计算方法 仅仅需要计算结点的2 个参数结点之间的路径长 万方数据 第5 期乔朝飞等基于树的等高线空间关系表达与计算 5 7 3 度 即连接结点的最少的边的个数 与层数．一旦等 高线树生成，这2 个参数的求取十分简单．因而基 于树结构的计算方法效率很高． 4结j 论 地形图上等高线相互之间的空间关系是人们 分析地形的重要依据，也是利用G I S 模拟人类地 形图认知能力的一个重要出发点．本文首先分析了 等高线空间关系的语义，将等高线空间关系划分为 多阶包含、并列和多阶相离三类．指出这些空间关 系用树结构表达最为适宜，在此基础上，总结了具 备不同空间关系的等高线结点的路径长度与层数 之间的关联，基于此设计了可在计算机中执行的等 高线三类空间关系的计算方法． 参考文献 E 4 3 E s ] [ 6 ] [ 1 ]乔朝飞．等高线空间关系的树表达研究[ D ] ．北京中 国矿业大学资源与安全工程学院，2 0 0 4 ．，．、 I ／l E 2 3 [ 3 ] 郭庆胜．建立等高线层次结构的智能化途径E J 3 ．武汉 测绘科技大学学报，19 9 5 ，2 0 增刊 6 9 7 5 ． G u oQS ．T h ei n t e l l i g e n tm e t h o do fb u i l d i n g h i e r a r c h i c a ls t r u c t u r eo fc o n t o u r s [ J ] ．J o u r n a lo f W u h a nT e c h n i c a lU n i v e r s i t y o f S u r v e y i n g a n d M a p p i n g ，19 9 5 ，2 0 s u p p 6 9 7 5 ． 王涛，毋河海．等高线拓扑关系的构建以及应用 [ 8 ] [ J ] ．武汉大学学报信息科学版，2 0 0 4 ，2 9 5 4 3 8 4 4 2 ． W a n gT ，W uHH ．C o n s t r u c t i o na n da p p l i c a t i o n so f t o p o l o g i c a l r e l a t i o n a m o n gc o n t o u rl i n e s [ J ] ． G e o m a t i c sa n dI n f o r m a t i o nS c i e n c e o fW u h a n U n i v e r s i t y ，2 0 0 4 ，2 9 5 4 3 8 4 4 2 ． 郝向阳．地图信息识别与提取技术E M 3 ．北京测绘出 版社，2 0 0 1 ． 张登荣，刘绍华，毛天露，等．等值线自动建立拓扑关 系算法与快速填充应用[ J ] ．中国图象图形学报， 2 0 0 1 ，6 A 3 2 6 4 2 6 9 ． Z h a n gD R ，L i uSH ，M a oTL ，e ta 1 ．A na l g o r i t h m o fa u t o m a t i cc r e a t i o no ft o p o l o g i c a lr e l a t i o na n di t s a p p l i c a t i o no ff a s t c o l o rf i l lb e t w e e nc o n t o u r s [ J ] ． J o u r n a lo fI m a g ea n dG r a p h i c s ，2 0 0 1 ，6 A 3 2 6 4 2 6 9 ． B o y e l lR ．R u s t o nH ．H y b r i dt e c h n i q u e sf o rr e a l t i m e r a d a rs i m u l a t i o n [ A ] ．I n P r o c ．o ft h eF a l lJ o i n t C o m p u t e rC o n f e r e n c e F C ] ．L a sV e g a s ，19 6 3 ，4 5 4 5 8 ． F r e e m a nH ，M o r s eSP ．O ns e a r c h i n gac o n t o u rm a p f o ra g i v e nt e r r a i ne l e v a t i o np r o f i l e [ J ] ．J o u r n a lo { t h e F r a n k l i nI n s t i t u t e ，1 9 6 7 ，2 4 8 1 1 - 2 5 ． C r o n i nT ．A u t o m a t e dr e a s o n i n gw i t hc o n t o u rm a p s [ J ] ．C o m p u t e r s G e o s c i e n e e s ，1 9 9 5 ，2 1 5 6 0 9 6 】8 ． 责任编辑李成俊 万方数据