基于共形几何代数的GIS三维空间数据模型.

中国科学:地球科学2010年第40卷第12期:1740~1751引用格式:YuanLW,YuZY,LuoW,etal.A3DGISspatialdatamodelbasedonconformalgeometricalgebra.SciChinaEarthSci,2010,doi:10.1007/s11430-010-4130-9《中国科学》杂志社SCIENCECHINAPRESS论文基于共形几何代数的GIS三维空间数据模型袁林旺*,俞肇元,罗文,周良辰,闾国年†南京师范大学虚拟地理环境教育部重点实验室,南京210046*联系人,E-mail:[e-mail];†同等贡献,E-mail:[e-mail]收稿日期:2010-08-18;接受日期:2010-11-02国家高技术研究发展计划专项课题(编号:2009AA12Z205、国家自然科学重点基金(批准号:40730527和国家自然科学青年基金(批准号:41001224资助摘要利用共形几何代数(CGA多维表达的统一性、几何意义的明确性及运算的坐标无关性等优势,构建了基于其上的GIS三维空间数据模型:通过建立不同维度地理对象与Clifford代数基本要素(Blades的映射,实现代数空间中不同维度、不同类型地理对象统一表达与运算,并基于内积、外积实现了内蕴不同维度层次构建及度量关系的几何形体构建;构建了基于CGA的三维GIS空间数据模型整体架构、数据存储结构和编辑、更新机制,并基于CGA几何与拓扑运算基本算子,实现面向对象的三维GIS几何和拓扑分析功能;某小区三维数据的实例演示表明,基于CGA的三维GIS空间数据模型可有效表达不同维度的复杂几何形体,且几何和拓扑关系运算具有简明、高效等特点,具备支撑三维乃至时空GIS数据模型的潜力.关键词共形几何代数三维空间数据模型三维度量三维空间关系由二维GIS向三维GIS以及时态GIS拓展是GIS发展的必然趋势.三维空间数据模型是三维GIS的基础,也是现阶段GIS研究的重点和热点问题之一[1].学术界对三维空间拓扑模型[2~5]、空间关系表达框架[6~8]、三维空间可视化[9~14]、三维空间数据集成[15~17]以及三维空间数据库[18~20]等方面进行了较为广泛的探讨[21,22],所发展的三维空间数据模型已在数字城市[23~28]、数字海洋[29]以及数字矿山[30,31]等领域得到了应用.但总体上,现有数据模型在支撑复杂地理对象表达、多维空间关系和地学分析以及对地理模型多维运算支撑仍显不足[1,32].因此,构建可支撑多维复杂地理对象统一表达与运算的三维数据模型,提升对复杂空间分析及地理分析模型的支撑能力,是现阶段GIS数据模型研究的主要方向.GIS处理对象从二维到三维乃至高维的转变,在数据量极大增大的同时,也导致了不同对象类型和空间关系的改变,因而对几何对象表达、几何与拓扑分析的多维统一表达与运算提出了更高的要求,现有的数据模型多基于欧氏几何框架,在维度扩展时可能导致空间语义的多义性、空间查询信息的不完备性、空间特征的模糊性和不确定性以及空间模拟与推理的复杂性等问题[33,34].因而三维GIS的发展需要从数据处理流程乃至系统体系结构上进行改造.从底层数学基础上进行创新,建立能够支撑不同维度的统一表达和计算的理论框架,进而发展可支撑复杂地理对象的表达、分析、建模与模拟的GIS空间分析方法是现阶段GIS数据模型创新的可能途径.共形几何代数(ConformalGeometricAlgebra,中国科学:地球科学2010年第40卷第12期1741CGA是Clifford代数的一种[35,36],它将维度运算作为几何运算的基础,现有基于计算几何、射影几何的相关算法经过简单的变换即可统一到CGA框架下[37].其优越的几何计算能力和时空表达能力,已被广泛应用于相对论物理学、计算机视觉和机器人学等领域[37~39].因此从基础理论和方法支撑层面,CGA均具备了发展以多维融合为特征的新型GIS数据模型的潜力.本文将CGA引入GIS数据模型研究,基于多维统一分析框架,构建了可支撑复杂几何形体的多维统一表达、度量及空间关系运算的三维GIS数据模型,并进行了系统实现与案例数据分析.1共形几何代数与基本几何体表达1.1Clifford代数及多维统一的数学表达给定两个向量a和b,Clifford积可表达为ab=a·b+a∧b.其中:a·b为a和b的内积,运算结果为一个标量;a∧b为外积,其结果为一个二重矢量(Bivector.两者分别与向量代数中点积和叉积类似,但不仅限于三维空间.外积与内积的维度运算与几何意义表现在:内积为降维操作,当a·b=0时,非零向量a,b正交;外积为升维操作,且当a∧b=0时,a,b平行.类同于复数同时包含了实部与虚部运算,Clifford积实现了标量运算与矢量运算、维度运算和几何运算的统一,且可实现坐标无关的几何关系运算及维度变换运算,从而可有效地简化基于其上的几何对象、几何变换以及几何关系的表达与运算[40].多重向量(Multivector是Clifford代数空间中可同时包含多个不同维度的基本数据结构之一,通过将不同维度对象(如标量(scalar、向量(vector、二重矢量(bivector、三重矢量(trivector等用“+”号进行连接,实现对不同维度对象的统一表达与运算.此处“+”号仅用于连接不同维度对象,而并不进行数值运算.Clifford代数通过定义标定其基本元素及符号,使得不同维度间运算相互正交,进而实现不同维度对象的统一表达与运算.而多重向量的阶数(Grade运算则可有效解析出其中不同维度的对象.以三维多重向量A为例,其数学表达为=+++++++0112233121223233131123123,Aaaeaeaeaeaeaeae(1其中a0为标量,Grade为0;a1e1,a2e2和a3e3为向量,Grade为1;a12e12,a23e23和a31e31为二重矢量,Grade为2;a123e123为三重矢量,Grade为3.上述8个对象也被称为Blade,是构成三维Clifford代数空间Cl3,0的基本单位.1.2CGA及其内、外积的几何意义在三维欧氏空间中,外积和内积对不同维度的运算结构与几何层次间不具有统一性.欧氏几何空间的Grassmann分级结构并不对应于几何体的分级结构.如欧氏空间中点表示从原点出发到该点的向量,但2点的外积并不表示过这两点的直线,而是表示过原点和这两点的平面.Li等[35,36]在欧氏空间基础上,通过共形变换将欧氏空间嵌入共形空间,构建了共形几何代数,使得代数空间的Grassmann分级结构完全对应于几何体的分级结构,即不同维度几何形体构建可直接通过外积表达,而内积则用于表征距离和角度[40].因而CGA有效降低了基本几何形体构建的难度,并实现了同时包含几何造型与几何关系运算的多维统一表达与分析框架[40].CGA对欧氏空间的嵌入保持了原有欧氏空间的表达形式,且其嵌入的射影空间特性保证了新增的射影维度的系数变化不影响所嵌入的欧氏空间表达.CGA可为包括欧氏几何、双曲(非欧几何、球面几何、投影几何、仿射几何等提供统一和简洁的齐性代数框架.在CGA中,所有的几何关系都包含于Clifford积,各种维度的平面和球的几何度量与其几何构造对偶,几何上的交和扩张对应于Cayley代数交和并[41].各种几何变换可以用旋量和转量显式表示[41].同时CGA的坐标无关性,也使得其处理几何问题的过程和结果具有内蕴性,具有直观的几何解释.1.3CGA框架下基本几何体表达在CGA框架下可分别基于内积和外积进行几何形体表达和构建.基于外积的几何形体表达主要反映了不同层次几何形体间相互构建关系,而内积形式的几何形体表达则是通过以距离、角度等表征参数构建形成的参数方程.两者的有效结合使得CGA可同时实现基于几何层次关系以及几何位置与度量关系的几何形体表达与建模.常见的基本几何形体的内、外积表达见图1.CGA中基于外积和基于内积的几何形体表达均具有简洁性,且几何意义明确.多袁林旺等:基于共形几何代数的GIS三维空间数据模型1742图1基本几何形体的内积与外积表达数几何形体在表达形式及其几何意义上还具有统一性.如直线和圆、平面和球面的外积表达在结构上具有一致性,因而直线和圆可分别看作是包含了无穷远点的圆和球.考虑到内、外积的几何意义,多数几何对象内、外积表达间可以通过对偶运算进行统一与转换,从而有效简化几何形体的建模、几何变换与关系运算.2基于CGA的三维空间数据模型构建2.1基于CGA的三维空间数据模型面向对象的空间数据模型是描述三维空间对象的一种理想模型,在地理对象表达上具有明显优势[42].然而,地理数据对象的多样性与复杂性、数据模型底层数学理论支撑不足使得现有面向对象的三维数据模型仍面临数据存储量大、空间拓扑关系维护、空间数据的操作与检索困难以及对空间分析支持能力不足等问题[21,34].CGA可同时有效表征不同几何形体间的层次关系与度量关系,多重向量则可以有效实现不同维度、不同类型几何对象的有效融合与统一表达.从而为构建具有严密数学理论支撑的面向对象数据模型提供了基础.根据上述思路可构建基于CGA的三维空间数据模型(图2.由于Clifford积直接内蕴了维度运算,且CGA中不同维度的几何形体可以通过外积进行相互转化与表达.在数据模型构建中,对三维空间中复杂地理对象的组织可以按其组成对象的维度进行层次划分.通过将复杂几何对象抽象成为点、线、面、体四大几何要素类,该类要素类可看作是基本几何要素形体的复合(复形.对上述复合几何要素类进行拆分,形成可用CGA直接表达的基本几何形体(单形集合,从而实现复杂几何形体的表达与建模.除常用的点、线、平面和四面体四类基本几何单形外,增加点对、圆环以及球三类几何单形,从而在与现有数据模型的兼容性、复杂形体表达有效性及CGA表达与运算简明性间取得较好的平衡.为充分发挥CGA在不同维度几何形体表达与分析上的优势,提高数据模型在存储及拓扑关系维护等方面的效率,并降低其表达与运算复杂度.借鉴Clifford代数对不同维度基本几何要素Blades表达的思想,将不同维度上的几何单形与对应维度的Blades相关联.利用几何单形的外积表达,将不同维度几何中国科学:地球科学2010年第40卷第12期1743图2基于CGA的三维空间数据模型体均表达为共形空间中空间点集的参数方程,进而以地理对象为单位构建多重向量.不同维度几何形体的参数化表达,使得地理对象的结构自适应于构成该对象的次一级几何形体的变化,在降低数据存储量的同时减小了拓扑结构与空间关系的维护难度.基于多重向量表达地理对象,不仅可用CGA表征其几何构成,且其作为一个复形集合,可整体应用相关的几何与度量算子,获取其自身结构及不同地理对象间的几何与度量关系.由于CGA对不同维度对象表达的一致性与运算的坐标无关性,所构建的多数空间分析算子与算法,可同时适用于笛卡尔坐标系和球面坐标系[39].2.2基于CGA的三维空间数据存储结构基于CGA三维空间数据存储结构见图3.其中地理对象类(GeographicalObjects用于标定独立的地理对象,并通过MultivID与AttributesIDSets分别标定该地理对象的多重向量表达与属性.所定义的基类(MultiV,包含了CGA基本元素、空间构建与空间转换、几何体维度计算与类型解析以及Clifford积展开运算等基本运算功能,从而有效支撑了地理对象的CGA表达与分析.基于MultiV可依次派生出多重向量表达类(MultiVectorExpression和可表达不同维度几何单形的共形空间点集类(3DCGA_Points、线类(3DCGA_Lines、点对类(3DCGA_PointPairs、面类(3DCGA_Planes、圆类(3DCGA_Cycles、四面体类(