《郭薇陈军》由会员分享，可在线阅读，更多相关《郭薇陈军（6页珍藏版）》请在金锄头文库上搜索。
1、第26卷 第2期测 绘 学 报Vol . 26, No. 2 1997年5月ACTA GEODA ET ICA et CARTOGRA PH ICA SI N ICAM ay, 1997 基于点集拓扑学的三维拓扑空间关系 形式化描述 郭 薇 陈 军 (武汉测绘科技大学测绘遥感信息工程国家重点实验室, 430070) THE FORMAL DESCRIPTI ON OF TOPOLOGICAL SPATIAL RELATI ONSHIP IN 3D BASED ON PO INT SET TOPOLOGY Guo W ei, Chen Jun (W uhan T echnical U niver
2、sity of S urvey ing and M app ing, 430070) Abstract Practical need in GIS have let to the investigation of formalmethod of describing spatial relationships . A fter an introduction to the basic ideas and notions of topological relationship, an extension of geometric point2set approach by taking the
3、di mension of the intersections into account is presented.This results in a very large number of different topological relationships in 3D for Point, L ine, Surface, and Body features .Then we propose to group all possible case into a few meaningful topological relationships and discuss their exclus
4、iveness and completenessw ith respect to the point2set approach. Key words 3D GIS, Point set topology, Topological spatial relationship, The formal description 摘 要 本文阐明了研究空间关系理论的必要性,分析了拓扑空间关系描述方法的研究进展及存 在问题,以点集拓扑理论为基础,运用维数扩展的方法,提出了三维拓扑空间关系完善和形式化的 描述框架,在此基础上,对三维空间目标中存在着的拓扑空间关系进行了分类,定义了五种基本的 拓扑空间关系,并且
5、给出了三维拓扑空间关系最小集的互斥性与完备性证明。 关键词 三维GIS 点集拓扑 拓扑空间关系 形式化描述 分类号 O 18 1 引言 三维GIS作为一种描述和分析现实世界的工具,在城市规划、 地质、 矿山、 建筑学等诸多 领域具有广阔的应用前景,因此,研究三维GIS是非常必要的。由于GIS不仅关心空间目标自 身的几何特征及物理属性,还必须能够处理其与所处环境间的关系。因此,目标及其目标间拓 扑空间关系完备和形式化的描述与表达即成为设计三维GIS空间数据库的重要基础,同时, 它也是有效地实现空间关系查询和进行空间分析的基本前提。 收稿日期: 1996207208,截稿日期: 199621022
6、6 国家教委霍英东青年教师奖励研究基金资助项目 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 拓扑空间关系理论的研究已引起了学术界的高度重视。 人们从各自的研究领域出发,探讨 空间关系的本质与判定机理,寻求空间关系形式化描述,表达和操作的方法与途径,以完善和 发展拓扑空间关系理论。 本文以点集拓扑学理论为基础,探讨了运用维数扩展法对三维拓扑空 间关系进行形式化描述的方法并得出相应结论。 2 点集拓扑学的理论基础 所谓度量空间即为在抽象集合中引进了度量,设有任意元素(点)的集合R,对于集合的任 意两
7、点x,y确定了它们间的距离p(x,y)并满足如下度量空间的公理: (1)p(x,y) 0,当xy;p(x,x )= 0 (2)p(x,y )= p(y,x) (对称公理) (3)p(x,y )+ p(y,z)p(x,z) (三角形不等式) 则集合R就形成了度量空间。 所谓拓扑空间即为满足下列条件的元素(点)的集合X,对于R的每一元素(点)x选定了 一个以X的子集为成员的非空组,这个子集叫作x的一个邻域,并且满足下列拓扑空间公理: (1)x在它自己的每个领域里; (2)x的任意两个邻域的交集为x的一个邻域; (3)若N是x的邻域,U为X的子集合包含N,则U是x的邻域; (4)若N是x的邻域,并且
8、若N 表示集合zNN是z的邻域,则N 是x的邻域,集 合N 叫作N的内部。 邻近的集合理论使得邻近的度量概念一般化,由R的某一度量d得到的一个关于R的拓 扑称为由d定义的度量拓扑。由此可见,每一个度量空间也是拓扑空间,但是相反的提法却是 不准确的,即存在这样的拓扑空间,它不可能使成为度量空间。 拓扑空间X的子集N的余是一个集合xxX且x ?N,表示为XN。点X称为集合 N的边界点,如果它既不是集合N的内部点又不是它的余集XN的内部点,所有边界点的 集合称为集合N的边界,记为 9N。 设X与Y是拓扑空间,映射f:XY为连续,假如对于X的每点x,以及f(x)在Y内的 任意邻域N,集合f - 1(N
9、 )为x在X内的邻域,则映射f:XY叫作是一个同胚。若此映射为 一对一之连续满射并且有连续的逆映射,则称X同胚于Y,或X拓扑等价于Y。在同胚下拓扑 空间的特性得以保持,即一个特性为某个拓扑空间所具有时它也为每一个同胚的空间所具有, 这种特性就称为拓扑不变量。拓扑空间关系即指拓扑变换下的拓扑不变量。 3 拓扑空间关系描述的研究进展及存在问题 在拓扑空间关系描述方面,人们已经作了许多工作。 如: Guting(1988)根据点集的定义,运 用集合运算= ,给出了以下相等(equal ), 不相等(unequal ), 包含(inside ), 相离 (outside)和相交(intersect)等
10、拓扑空间关系的定义: x=y : = points(x)= points(y ), xy : = points(x)points(y) xinsidey : = points(x)points(y ), xoutsidey : = points(x)points(y )= xintersecty: = points(x)points(y) 这种定义的缺陷是这个关系集即不具有唯一性,也不具有完备性。例如:相等和包含均被相交 321第2期 郭薇等:基于点集拓扑学的三维拓扑空间关系形式化描述 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All
11、 rights reserved. 的定义所覆盖。 Pullar(1988)将点集方法加以扩充,运用拓扑学理论中点集的边界(boundary)和内部(in2 terior)的概念,给出了覆盖(overlap)和相邻(neighbor)两个关系定义: xoverlayy: = boundary(x)boundary(y)and interior(x)interior(y) xnieghbory: = boundary(x)boundary(y)and interior(x)interior(y )= W agner(1988)在此基础上,采用更细化的方法,通过比较边界和内部是否相交,定义了四 种
12、拓扑空间关系: 相邻: 边界相交,内部不相交; 相离:边界不相交,内部也不相交; 严格包含:边界不相交,但内部相交; 相交:边界相交,内部也相交; 这两种方法均采用单一或结合的方式来描述拓扑空间关系,但它并不完备。例如,它无法区分 相交和相等,因为,就这两种关系而言,均存在边界相交,内部也相交的情况。 Egenhofer和Franzosa(1991)根据点集拓扑学的基本理论,提出了更为形式化的拓扑空 间关系描述方法。 通过定义两个空间目标边界与边界,内部和内部,边界和内部,内部和边界的 交,建立了一个四元组表达的拓扑空间关系描述框架: 9A 9B 9AB A 9B A B 上述这个矩阵中,每个
13、元素要么为空,要么非空,故有16种情形。 通过进一步分析,可得出八种 可实现的拓扑空间关系。 与以上几种方法相比,这种方法是一种较好的形式化方法,但是,按此 描述框架,许多情形将无法区分。如两个多边形交于一点或交于一直线。 在此基础上, Egenhofer(1993)引进了点集的余,构造了一个由点集的边界,内部,余之间 的交集组成的九元组,以此作为描述两个点集间拓扑空间关系的框架。 这种方法改进了四元组 描述框架的部分不足,但它仅仅用空集和非空集两种结果来区分两个空间目标内部,边界和余 之间的交集,因此,该方法仍然具有一定的局限性。 Clementini等人(1993)在Egenhofer所定
14、义的四元组基础上,运用维数扩展法(dinension extended method ), 即用两个空间目标内部与边界之间交集的维数,作为描述两个点集间拓扑 空间关系的框架,进一步,他们给出了二维拓扑空间关系的最小集。这种方法形式化地描述了 二维空间目标之间的拓扑空间关系,但它仅仅局限于二维情形。 纵观以上分析方法,可以看出,拓扑空间关系描述的研究尚处在初级阶段,还存在着一些 实质性的问题有待解决。本文将Clementini等人所定义的维数扩展法加以了扩充,提出了形 式化地描述三维空间目标之间拓扑空间关系的方法,并在此基础上,定义了描述三维拓扑空间 关系的最小集。 4 三维拓扑空间关系的形式化
15、描述 GIS中所涉及的空间是度量空间,由于每一个度量空间也是拓扑空间,因此,本文在三维 拓扑空间中,给出三维空间目标及目标间拓扑空间关系的形式化定义及描述。 在三维拓扑空间X中,根据空间目标的自由度,可分为四种空间目标,即点状目标、 线状 目标、 面状目标和体状目标。 点状目标只有位置而无空间扩展,所以将其定义为零维目标;线状 421测 绘 学 报 26卷 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 目标只能沿着其线段方向作一维扩展,所以将其定义为一维目标;依据这种原理进行划分,面 状目标被定义
16、为二维目标;体状目标被定义为三维目标。 在此,我们仅考虑简单目标,即所有目 标均为闭集,且所有目标均为连通。 运用维数扩展法,将三维空间目标点、 线、 面、 体间边界与内部交集的维数作为空间拓扑关 系的描述框架。 其中点的边界总是为空;线的边界为线的两个端点,但当线为闭曲线时,线的边 界为空;面的边界由包含所有面的极值点的闭曲线构成;体的边界由包含所有体的极值点的闭 曲面构成。若将三维空间目标A的边界记为 9A,内部记为A,则存在关系式:A=A-9A。 设S为一个点集,定义函数din如下: din(S )= 0 1 2 3 S=; S 不包含线,面,体等,但至少包含一个点; S 不包含面,体等,但至少包含一条线; S 不包含体等,但至少包含一个面; S 至少包含一个体; 设有两个空间目标A和B,其边界与内部的交集分别用以下四个集合表示: S1=9A9B S2=9AB S3=A 9B S4=A B 其中Si(
