全空间信息系统理论方法

多粒度时空对象空间关系的统一表达与计算

  • 萧声隽 , 1, 2 ,
  • 宗真 1, 2 ,
  • 项丽燕 1, 2 ,
  • 胡勇 , 1, 2, 3, *
展开
  • 1. 南京师范大学地理科学学院,南京 210023
  • 2. 南京师范大学 虚拟地理环境教育部重点实验室,南京 210023
  • 3. 南京师范大学计算机科学与技术学院,南京 210023
*通讯作者:胡 勇(1973-),博士,讲师,主要从事计算机算法研究。E-mail:

作者简介:萧声隽(1986-),男,博士生,主要从事GIS算法及其应用研究。E-mail:

收稿日期: 2017-05-23

  要求修回日期: 2017-08-11

  网络出版日期: 2017-10-09

基金资助

国家重点研发计划项目(2016YFB0502300)

国家自然科学基金项目(41571380)

The Unified Expression and Calculation of Spatial Relationships of Spatio-temporal Object of Multi-granularity

  • XIAO Shengjuan , 1 ,
  • ZONG Zhen 1, 2 ,
  • XIANG Liyan 1, 2 ,
  • HU Yong , 1, 2, 3, *
Expand
  • 1. School of Geographic Science, Nanjing Normal University, Nanjing 210023, China
  • 2. Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210023,China
  • 3. School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023, China
*Corresponding author: HU Yong, E-mail:

Received date: 2017-05-23

  Request revised date: 2017-08-11

  Online published: 2017-10-09

Copyright

《地球信息科学学报》编辑部 所有

摘要

空间关系表达了空间数据的相互约束,在空间查询语言、数据检索及空间分析中具有重要作用。当前关于空间关系的研究,多基于简单地理对象,或者只对某一种空间关系进行独立的算法设计,难以满足多粒度对象多种空间关系的统一表达与计算。为此,本文利用几何代数运算的对象无关性和维度无关性,构建简单对象空间关系计算算子,并将其推广到多粒度对象,实现全空间地理信息系统框架下多粒度对象三种空间关系的一体化表达与计算。最后,以三角网求交算法为例,证明了算法的可行性,为全空间GIS中空间关系的表达和计算提供了借鉴。

本文引用格式

萧声隽 , 宗真 , 项丽燕 , 胡勇 . 多粒度时空对象空间关系的统一表达与计算[J]. 地球信息科学学报, 2017 , 19(9) : 1178 -1184 . DOI: 10.3724/SP.J.1047.2017.01178

Abstract

Spatial relationships play an important role in spatial query language, data retrieval and spatial analysis. However, the current research of spatial relations are hard to realize the unified expression and calculation of spatio-temporal objects of multi-granularity. In this paper, the spatial relationships computing operators of the simple objects are designed based on the type-independence and dimension-independence characteristics of GA operators. The operators are then generalized to spatio-temporal objects of multi-granularity by the union operator. Lastly, we realized the unified expression and calculation of three kinds of spatial relationships for the spatio-temporal objects of multi-granularity under the framework of pan-spatial GIS. The triangulation intersection algorithm is raised as an example to prove the reliability of our methods. Our research also provides the reference for expression and calculation of spatial relationships in pan-spatial GIS.

1 引言

空间关系主要包括度量关系、方位关系、拓扑关系,是进行空间数据组织、顾及空间特征的查询、分析与推理的基础[1]。Egenhofer等、Clementini等在点集拓扑学基础上提出九交模型及维度扩张的九交模型[2-3];陈军等基于Voronoi图提出的V9I模型[4];廖士中等提出闭球模型等来描述空间拓扑关系[5];邓敏等提出顾及目标中心分布趋势的广义Hausdorff距离度量模型[6]。描述方位关系用得最多的是MBR(最小外接矩形)模型、CDR(三角)模型,但它们存在定义上的漏洞和计算结果的错误[1]
粒度是空间数据和时间数据的固有本质[7],随着GIS应用领域的不断扩大,单粒度对象已经不能满足人们对复杂现实时间从微观到宏观的表达需求。多粒度时空实体的提出就是源于时空实体在不同需求下的不同空间尺度表达,在计算机构建的信息世界中对多粒度时空实体的具体描述即为多粒度时空对象,是一种对现实世界的具体抽象方法[8]。针对全空间信息系统[9]中多粒度时空对象多元、多维度、多尺度、多参照系、多时态、多形态交叠的多模态特征[8],以上模型难以满足复杂的多粒度时空对象间空间关系的一体化表达与计算,难以满足现实复杂对象间空间关系分析需求。本文采用具有坐标无关性的几何代数方法[10-11],利用其基于多重向量对多维对象统一表达层次体系,实现全空间地理信息系统框架下多粒度时空对象维度信息与度量、拓扑与方位信息的统一描述与计算。

2 空间关系定义

空间关系用于描述空间实体之间度量、方位、拓扑等方面的关系。拓扑关系描述的是空间实体之间的邻接、关联和包含关系。以区域连接演算(RCC)定义的8种可能的对象之间的基本拓扑关系为例,其拓扑关系包括:
(1)
任意对象之间的空间拓扑关系是上述8种基本拓扑关系的组合。面向多粒度时空对象的拓扑关系表达,可以定义更为精细的拓扑关系,利用多重空间关系表达模型实现Vst值域集合的拓展。对于给定的多粒度时空对象,其拓扑关系可用图1表示。
Fig. 1 The expression of multiple spatial relationships

图1 多重空间关系表达

空间方位关系将空间分为适用于所有空间实体的一组方向或角度。空间方位关系可以利用Frank基本方位演算(Cardinal Direction Calculus,CDC)来表示。基本方位演算将空间分为4个或者8个方位,并且引入了一个额外的“null”方位,代表2个空间实体之间没有方位信息,即两个空间实体在同一个位置或者距离非常近。方位关系的基本运算包括反演和组合。与RCC类似,基本方位演算(CDC)也可以将所有可能的组合运算映射到一个矩阵表中。表1为基本方位演算在二维空间中的8个基本方向之间的组合运算表,并且约定,大写字母表示精确的方位关系,小写字母表示近似的方位关系。
Tab. 1 The rule table of the inference of combination of the position relations

表1 方位关系的组合推理规则表

N NE E SE S SW W NW null
N N n ne null null null nw n N
NE n NE ne e null null null N NE
E ne ne E e se null null null E
SE null e e SE se s null null SE
S null null se se S s sw null S
SW null null null s s SW sw w SW
W nw null null null sw sw W w W
NW n n null null null w w NW NW
null N NE E SE S SW W NW null
度量关系是通过在空间中定义度量的基础上,采用某种度量指标来描述目标间的远近关系[12]。在几何空间中,度量空间主要有长度、面积等,以上度量关系一般可通过形式简单的数学公式求解。在GIS中,根据地理学研究的内涵,所关注的度量关系主要是两地理对象间的空间距离,可用Rsm(A、B、R)表示,其中R表示地理对象AB之间的距离。常用的如欧氏距离、曼哈顿距离、契比雪夫距离等。随着空间统计学的发展,斜交距离和马氏距离等具有显著统计学意义的度量关系也逐步得到重视[4]

3 地理对象空间关系的几何代数表达

在几何代数中,空间被定义为向量集合间的运算,空间维数直接由运算法则确定[13],几何代数通过blade和多重向量等基本元素表达简单几何对象,通过对上述简单对象的组合运算即可得到复杂对象的几何代数表达[14]。由于上述简单对象与复杂对象具有共通的表达结构、存储结构和属性特征,即可实现从基本元素到简单地理对象到复杂时空对象空间关系的推导,如图2所示。
Fig. 2 The derivation of spatial relations of simple object and complex object

图2 简单对象间和复杂对象间的空间关系推导过程

复杂时空对象可视为多个单维度简单地理对象的组合,则空间关系亦可视为多维对象各组分之间空间关系的一种组合表达。故而在简单对象间空间关系的几何代数表达基础上,可构建几何代数空间中对复杂时空对象空间关系的统一表达[15]

3.1 基于几何代数的空间关系求解

在几何代数框架中对象表达内蕴几何特征,可直接利用算子计算对象间空间关系[14]。两对象blade表达内积的几何意义是两对象的距离,故而可利用内积运算进行度量关系的求解;对象的方位关系可转化为其在基准方位上的距离的投影,可通过距离运算变相求解;对象间的拓扑关系则可利用表达对象交关系的meet算子进行求解。将各算子的计算过程详细定义如下:
给定两点的几何代数表达PS,两点间的距离可通过内积求解 P S = p s - 1 / 2 s 2 - 1 / 2 p 2 = - 1 / 2 ( s - p ) 2 ,其中ps为两点的欧氏空间表达,(s-p2即为两简单几何对象欧氏距离的平方值。在GIS中,方位表示地理对象间的方位角,则方位算子为 cosθ = P · S P S , P S 分别为两对象的模,则式子表示用于求解几何代数对象间的夹角;如果定义P为基准方位,则通过式子可求得S与基准方位的夹角。对象间的拓扑关系可通过meet算子求解,meet算子的几何意义是两几何对象的交,即两对象间所共有的最大子空间,通过对该最大子空间的判断可得到对象间的拓扑关系[16]。给定两几何对象AB,其meet运算 M = A B 可通过式(2)定义:
x : [ x M = 0 ] x A = 0 x B = 0 (2)
根据拓扑关系的定义可知,可直接通过对求交结果的考查,得到对象间的拓扑关系。例如,假定AB为线对象和面对象,当M 2>0时,两对象相交;当M 2=0时,两对象相切;当M 2<0时,两对象相离[17]

3.2 复杂对象空间关系表达

在GIS应用中,几何对象多具有固定边界,空间关系的求解也需要顾及到所有的边界点。由于度量关系与方向关系本身的有序性,可通过一固定区间对其加以表达,而省略区间内部各边界点的度量和方位值;拓扑关系的求解则需要同时考虑对象边界间的相对关系。
(1)方位关系表达
对于复杂对象,其在空间关系运算中多表达为一个区域,如图3所示。点A与线段B1B2的空间方位关系可表示为一个区间: α ( A , B 1 B 2 ) = [ α ( A , B 1 ) α ( A , B 2 ) ] = [ α , β ] 。首先探讨点A与区域B方位关系的表达,对于点A而言,区域B只有折线B1B2,B1B7,B6B7部分是可视的,而点A与不可视部分的折线的方位角必将落在点A与可视区域折线方位角之内,即点A与不可视区域的点Bi连线必与可视区域折线相交。则点A与区域B的方位关系表示为式(3)。
Fig. 3 Orientation relationship of point and region

图3 点与区域的方位关系

α ( A , B 1 B 2 B n B 1 ) = [ α ( A , B 1 ) , α ( A , B 2 ) ] [ α ( A , B 2 ) , α ( A , B 3 ) ] [ α ( A , B n - 1 , α ( A , B n ) ] [ α ( A , B n ) , α ( A , B 1 ) ] = [ α , β ] (3)
区域AA1, A2, …, Am)与区域BB1, B2,…, Bn)的空间方位关系可按组分层级分解,区域与区域即可视为多点与区域空间方位关系的扩展。其方位关系可以表示为式(4)。
α ( A 1 A 2 A m , B 1 B 2 B n ) = α ( A 1 A 2 A m , B 1 ) α ( A 1 A 2 A m , B 2 ) α ( A 1 A 2 A m , B n ) = j = 1 n α ( A 1 A 2 A m , B j ) = [ α 1 , β 1 ] [ α 2 , β 2 ] [ α n , β n ] = j = 1 n [ α i , β j ] = [ α , β ] (4)
(2)度量关系表达
同理,得到点A与区域B1B2Bn的空间度量关系表示为式(5)。
(5)
区域与区域的度量关系亦可视为点与区域度量关系的一种拓展。如图4所示,图中区域A与区域B的度量关系,可用其各组分之间的度量关系来表达,一般用其最大值和最小值表示A1A2A3A4B的可视边界B1B2B5B6之间的空间度量关系,则它们的度量关系可表示为式(6)。
Fig. 4 Spatial relationship of region and region

图4 区域与区域的空间关系

m ( A 1 A 2 A 3 A 4 A 5 , B 1 B 2 B 3 B 4 B 5 B 6 ) = m ( A 1 A 2 A 3 A 4 , B 2 B 1 B 6 B 5 ) = m ( A 1 A 2 A 3 A 4 , B 2 ) α ( A 1 A 2 A 3 A 4 , B 1 ) α ( A 1 A 2 A 3 A 4 , B 6 ) α ( A 1 A 2 A 3 A 4 , B 5 ) = m ( A 1 A 2 , B 2 ) m ( A 1 A 3 , B 2 ) m ( A 3 A 4 , B 5 ) = [ min ( , ) , max ( , ) ] = [ c ' , d ' ] (6)
(3)拓扑关系表达
对象AA1, A2,…,Am)与对象B(B1, B2,…, Bm)的空间拓扑关系亦可视为两对象各组分之间拓扑关系的扩展,表达为式(7)。
t ( A 1 A 2 A m , B 1 B 2 B n ) = t ( A 1 A 2 A m , B 1 ) t ( A 1 A 2 A m , B 2 ) t ( A 1 A 2 A m , B n ) = j = 1 n t ( A 1 A 2 A m , B j ) = i = 1 m j = 1 n t ( A i , B j ) (7)

3.3 复杂对象空间关系一体化表达

通过上述定义可知,复杂对象的空间关系可利用几何代数算子统一表达,则可定义复合算子实现不同类型空间关系的一体化表达。对于相同维复杂对象AB,定义AiBj分别为构成AB两对象中第ij个子对象,首先对各子对象之间的空间关系<Ai, Bj>进行计算,然后合并3种空间关系,即可利用算子的组合实现同维复杂对象间的空间关系的求解,形式化表达如式(8)所示。
< A , B > = < A 1 , B 1 > < A i , B j > < A m , B m > (8)
如果AB分别为mn维的两不同维度几何对象,则将多维对象按照不同维度分成0维、1维、2维、…、n维等子对象,AiBj分别为构成AB两对象中第ij个子对象,可求得各子对象之间的空间关系<{Ai,Bj}>,从而得到不同维复杂对象之间的空间关系结果,其形式化表达如式(9)所示。
< A , B > = < { A 1 , B 2 } > < { A i , B j } > < { A m , B n } > (9)

4 三维小区空间关系统一求解实例

基于三角形表达与运算的理论和算子,设计相关的数据结构与计算算法。首先将三维小区建筑数据转换到几何代数空间,需要进行维度映射与几何代数空间转换;然后利用区域对象几何代数求交方法[18-19],基于本文所提出的几何对象计算算子与关系判断算子进行空间关系的求解。
首先基于CGA的矢量数据模型,构造三维建筑物的表达模式,如图5所示。
Fig. 5 Expression of triangle mesh object based on the multiple vector

图5 基于多重向量形式的三角网对象表达

多重向量集合MVi可视为构成该三维建筑的多个三角形Ti的集合,利用几何代数对简单对象的表达,根据三角形Ti边界可将其约束分解为点、线段与三角形,实现层次组织。构建基于几何代数的对象表达模型后,给定两三维建筑对象A,B,其基于三角形的表达为式(10)。
A = T 1 + T 2 + T m B = T 1 ' + T 2 ' + T m ' (10)
其中Ti表示用于构建三维建筑对象的三角形,其共形几何代数表达为式(11)。
T i = [ A 1 B 1 C 1 e ] < A 1 , B 1 , C 1 > = A 1 B 1 C 1 e [ A 1 C 1 e ] < A 1 , C 1 > [ A 1 B 1 e ] < A 1 , B 1 > [ B 1 C 1 e ] < B 1 , C 1 > = S 1 l 11 l 12 l 13 (11)
根据三维建筑物对象中各三角形及其层次组分对象的几何代数表达,其三类空间关系可通过式(12)-(14)求解。为了简化表达,距离和角度均通过三维建筑物对象的质心求解。
(1)距离关系计算,给定两三维建筑对象,其质心分别为P1,P2则其距离关系为式(12)。
d ( P 1 , P 1 ) = - 2 P 1 P 2 (12)
P与点S的方位关系由方位算子 cosθ = P 1 P 2 P 1 P 2 ;
(2)角度关系计算,给定两三维建筑对象,其质心分别为P1, P2,则其相对角度关系为式(13)。
θ = arccos P 1 P 2 P 1 P 2 (13)
(3)拓扑关系计算,由于三维建筑具有层次构造结构,可将其拓扑关系的求解分为不同的层次,即首先对三维建筑所在的维度范围进行预判断,进而利用上述区域三角形求交的空间关系判定方法,构造相应的判定算子对其空间拓扑关系进行求解(式(14))。
(14)
基于三角形与直线的层次构建关系,可将上式改写为如下形式(式(15))。
A B = T 1 T 2 * { S 1 S 2 * [ S 1 l 21 * ( l 11 l 21 + l 12 l 21 + l 13 l 21 ) + S 1 l 22 * ( l 11 l 22 + l 12 l 22 + l 13 l 22 ) + l 22 S 1 * ( l 23 l 11 ) + l 23 l 12 + l 23 l 12 ] } (15)
式中:“*”为judge算子,用于连接两几何代数运算,其代数意义为:当“*”左侧满足一定要求时,右侧才进行运算。式(15)表明在求解过程中,可先利用求交算子的符号对其相交关系进行初步判断,筛选去除M 2<0的结果(见3.1节),然后利用上文所提出的区域求交的空间关系判定方法对其空间关系进行求解,最后求得三角形各要素的相交 情况。
图6为基于上述统一求解方法设计的空间关系求解算法的分析结果。图6(a)为用于参与计算的原始三维小区数据;图6(b)为进行空间关系计算的对象参数选择界面;图6(c)为计算得到的距离和角度结果,其中距离用蜘蛛图表示,角度用向量表达;图6(d)为拓扑关系计算结果,左图为meet计算结果,右图为最终求得的拓扑关系。
Fig. 6 Examples of spatial relations calculation based on the 3D housing estate data

图6 基于三维小区数据的空间关系计算案例

5 结论

度量关系、拓扑关系与方位关系是最基本的空间关系,它们从不同角度相互制约约束,共同刻画了空间关系的特性。本文探讨了基于几何代数形式化表达的空间关系运算的构建流程,简化了现有GIS空间关系运算的结构复杂性,提升了GIS空间关系运算的多维统一性与自适应性,实现了复杂时空对象间三类空间关系的统一描述与计算,提高了对复杂地理对象空间关系描述的计算精度。构建的空间关系算子集和算法库,设计空间关系运算逻辑表达,完善和改进现有空间关系计算方法,地理对象表达与关系计算结合的新途径可为多粒度时空对象的建模与分析提供借鉴。并通过基于三维场景中建筑物的空间关系计算案例表明,在几何代数统一框架下,可以实现对多维复杂地理对象的空间关系表达与求解,且逻辑结构清晰,运算简洁高效,可为多粒度时空对象建模表达,对象间空间分析统一求解提供借鉴,为全空间地理信息系统的发展提供新的理论基础。

The authors have declared that no competing interests exist.

[1]
廖楚江,杜清运.GIS空间关系描述模型研究综述[J].测绘科学,2004,29(4):79-82.空间关系是GIS的重要理论问 题之一,在GIS数据建模、空间查询、空间分析、空间推理、制图综合、地图理解等过程中起着重要作用。目前国际上对空间关系的研究主要集中在空间关系的语 义问题、空间关系描述、空间关系表达、基于空间关系的查询分析等方面。而其中对空间关系的描述更是见人见智。本文主要论述了空间关系描述的研究进展和成 果。

DOI

[Liao C J.Review on models of the description of GIS spatial relationship[J]. Science of Surveying and Mapping, 2004,29(4):79-82. ]

[2]
Egenhofer M J, Herring J R.Categorizing binary topological relationships between regions, lines and points in geographic data bases[A]. In: A Framework for the Definition of TopologicalRelationships and An Approach to Spatial Reasoning within this Framework[C]. Santa Barbara,CA,199l:1-28.

[3]
Clementini E, Di F P, Oostemm P V.A small set of formal topologicaI relationships suitable for end-user interaction. In: D.Abel and B.C.Ooi(eds). Advances in Spatial Databases[C]. NewYork:Springer-Verlag, 1993:277-295.

[4]
陈军,赵仁亮.GIS空间关系的基本问题与研究进展[J].测绘学报,1999,28(2):95-102.空间关系是GIS的重要理论问题之一,在GIS空间数据建模,空间查询,空间分析,空间推理,制图综合,地图理解等过程中起着重要的作用。目前国际上对空间关系的研究主要集中在空间关系的语义问题,空间关系描述空间关系表达,基于空间关系的分析等方面。

[Chen J, Zhao R L.Spatial relations in GIS: A survey on its key issues and research progress[J]. Acta Geodaetica et Cartographica Sinica, 1999,28(2):95-102. ]

[5]
廖士中,石纯一.拓扑关系的闭球模型及复合表的推导[J].软件学报,1997(12):894-900.

[Liao S Z, Shi C Y.Closed ball model and composition table derivation for topological relations[J]. Journal of Software, 1997,12:894-900. ]

[6]
邓敏,李志林,陈晓勇.GIS空间目标的广义Hausdorff距离模型[C]// 中国测绘学会第八次全国会员代表大会暨2005年综合性学术年会论文集, 2005:641-645.

[Deng M, Li Z L, Chen X Y.A generalized Hausdorff distance model for spatial objects in GIS[C]. Geomatics and Information Science of Wuhan University, 2005:641-645. ]

[7]
李阳东,韩震,童小华.一种顾及多粒度的时空数据模型[C]// 2009国际信息技术与应用论坛论文集(下), 2009.

[Spatio-temporal data model of multi-granularity[C].2009 International Forum on Information Technology and Applications, 2009. ]

[8]
华一新. 全空间信息系统的核心问题和关键技术[J].测绘科学技术学报,2016,33(4):331-335.分析了空间信息系统的研究现状和存在问题,阐明了全空间信息系统的基本概念和基本特征;提出了基于多粒度时空对象构建全空间信息系统的技术路线,明确了需要研究解决的科学问题和关键技术;提出了全空间信息系统与智能设施管理的主要研究内容,指出预期的研究效益。

DOI

[Hua Y X, The core problems and key technologies of pan-spatial information system[J]. Journal of Geomatics Science and Technology, 2016,33(4):331-335. ]

[9]
周成虎. 全空间地理信息系统展望[J].地理科学进展,2015,34(2):129-131.地理信息系统作为一门空间科学,以其独特的空间观点和空间思维,从空间相互联系和相互作用出发,揭示各种事物与现象的空间分布特征和动态变化规律。本文从地理信息系统所研究的空间对象出发,对地理信息系统发展新方向提出思考:①从地球空间拓展到宇宙空间,需要构建宇心坐标系和宇宙GIS、月球GIS等;②从室外空间延伸到室内空间,需要发展室内GIS,并拓展到水下空间和地下空间;③从宏观到微观空间,可以发展面向游戏的体育GIS、面向生命健康管理的人体GIS等;④面向大数据时代,发展大数据空间解析的理论和方法,贡献于大数据科学的发展。

DOI

[Zhou C H, Prospects on pan-spatial information system[J]. Progress in Geography, 2015,34(2):129-131. ]

[10]
Yu Z, Luo W, Yuan L, et al.Geometric algebra model for geometry-oriented topological relation computation[J]. Transactions in GIS, 2015,20(2):259-279.Abstract Classical topological relation expressions and computations are primarily based on abstract algebra. In this article, the representation and computation of geometry-oriented topological relations (GOTR) are developed. GOTR is the integration of geometry and topology. The geometries are represented by blades, which contain both algebraic expressions and construction structures of the geometries in the conformal geometric algebra space. With the meet , inner , and outer products, two topology operators, the MeetOp and BoundOp operators, are developed to reveal the disjoint/intersection and inside/on-surface/outside relations, respectively. A theoretical framework is then formulated to compute the topological relations between any pair of elementary geometries using the two operators. A multidimensional, unified and geometry-oriented algorithm is developed to compute topological relations between geometries. With this framework, the internal results of the topological relations computation are geometries. The topological relations can be illustrated with clear geometric meanings; at the same time, it can also be modified and updated parametrically. Case studies evaluating the topological relations between 3D objects are performed. The result suggests that our model can express and compute the topological relations between objects in a symbolic and geometry-oriented way. The method can also support topological relation series computation between objects with location or shape changes.

DOI

[11]
Yuan L, Yu Z, Luo W, et al.Multidimensional-unified topological relations computation: A hierarchical geometric algebra-based approach[J]. International Journal of Geographical Information Science, 2014,28(12):2435-2455.This article presents a geometric algebra-based model for topological relation computation. This computational model is composed of three major components: the Grassmann structure preserving hierarchical multivector-tree representation (MVTree), multidimensional unified operators for intersection relation computation, and the judgement rules for assembling the intersections into topological relations. With this model, the intersection relations between the different dimensional objects (nodes at different levels) are computed using the Tree Meet operator. The meet operation between two arbitrary objects is accomplished by transforming the computation into the meet product between each pair of MVTree nodes, which produces a series of intersection relations in the form of MVTree. This intersection tree is then processed through a set of judgement rules to determine the topological relations between two objects in the hierarchy. Case studies of topological relations between two triangles in 3D space are employed to illustrate the model. The results show that with the new model, the topological relations can be computed in a simple way without referring to dimension. This dimensionless way of computing topological relations from geographic data is significant given the increased dimensionality of geographic information in the digital era.

DOI

[12]
景黎. 空间区域拓扑、度量关系结合方法的研究[D]. 长春:吉林大学,2007.

[Jing L.Research on the combination method of topological relations and metric relations of spatial regions[D]. Changchun: Jilin University, 2007. ]

[13]
袁林旺,俞肇元,罗文,等.多维统一GIS构建与实现的几何代数方法[J].地理研究,2013,32(5):974-983.

[Yuan L W, Yu Z Y, Luo W, et al.Geometric-algebra based construction and implementation methods for multi-dimension-unified GIS[J]. Geographical Rsearch, 2013,32(5):974-983. ]

[14]
Yuan L W,Yu Z Y, Luo W, et al.A 3D GIS spatial data model based on conformal geometric algebra[J]. Science China Earth Sciences, 2011,54(1):101-112.We propose a new Geographic Information System (GIS) three-dimensional (3D) data model based on conformal geometric algebra (CGA). In this approach, geographic objects of different dimensions are mapped to the corresponding basic elements (blades) in Clifford algebra, and the expressions of multi-dimensional objects are unified without losing their geometric meaning. Geometric and topologic computations are also processed in a clear and coordinates-free way. Under the CGA framework, basic geometrics are constructed and expressed by the inner and outer operators. This expression combined geometrics of different dimensions and metric relations. We present the structure of the framework, data structure design, and the data storage, editing and updating mechanisms of the proposed 3D GIS data model. 3D GIS geometric and topological analyses are performed by CGA metric, geometric and topological operators using an object-oriented approach. Demonstrations with 3D residence district data suggest that our 3D data model expresses effectively geometric objects in different dimensions, which supports computation of both geometric and topological relations. The clear and effective expression and computation structure has the potential to support complex 3D GIS analysis, and spatio-temporal analysis.

DOI

[15]
宗真. 基于几何代数的空间关系表达与计算模型研究[D].南京:南京师范大学,2013.

[Zong Z.Study on the expression and calculation models of spatial relation based on geometry and algebra[D]. Nanjing: Nanjing Normal University, 2013. ]

[16]
罗文. 基于几何代数的GIS计算模型研究[J].测绘学报,2014,43(9):990-990.

DOI

[Luo W.The Study on GIS computational model based on geometric algebra[J]. Acta Geodaetica et Cartographica Sinaca, 2014,43(9):990-990. ]

[17]
Eduardoe R.Operaciones de Cómputo Gráfico en el Espacio Geométrico Conforme 5D usando GPU[D]. Venezuela: Universidad Simón Bolívar, 2011.

[18]
宗真,袁林旺,罗文,等.三角网求交的共形几何代数算法[J].测绘学报,2014,43(2):200-207.lt;p>针对传统三角网求交计算方法逻辑结构复杂,维度上不统一等不足,本文基于几何代数理论,从对象表达、关系运算相统一的角度,构建了基于meet算子的自适应三角网求交算法。利用共形几何代数中与Grassmann分级结构一致的对象外积表达,建立了三角网的几何代数表达;基于meet算子构建空间三角网求交算法,探讨了该算法对几何对象及维度的自适应性;最后基于南极冰盖模拟数据对上述算法进行案例验证。结果显示,本文算法可以很好的支撑三角网的求交运算,在简化了算法结构的同时提升了算法的多维适用性,可为基于几何代数的多维融合空间分析算法构建提供借鉴。</p>

[Zong Z, Yuan L W, Luo W, et al.Triangulation intersection algorithm based on conformal geometric algebra[J]. Acta Geodaetica et Cartographica Sunica, 2014,43(2):200-207. ]

[19]
王建超. 基于CGA的多维统一曲面求交算法及其应用研究[D].南京:南京师范大学,2012.

[Wang J C.Multi-dimensional unified surface intersection algorithm and its application research based on the CGA[D]. Nanjing: Nanjing Normal University, 2012. ]

文章导航

/