基于几何代数的时空宗地meet计算研究

王巧燕，蒋晓敏，张 丰*，杜震洪，刘仁义

(1. 浙江大学 浙江省资源与环境信息系统重点实验室， 浙江 杭州 310028；2. 浙江大学 地球科学学院， 浙江 杭州 310027)

基于几何代数的时空宗地meet计算研究

王巧燕1,2，蒋晓敏1,2，张 丰1,2*，杜震洪1,2，刘仁义1,2

(1. 浙江大学 浙江省资源与环境信息系统重点实验室， 浙江 杭州 310028；2. 浙江大学 地球科学学院， 浙江 杭州 310027)

根据几何代数在地理空间对象建模和多维数据分析应用的特点，研究了共形几何代数交/并(meet/join)算子的含义、构建和应用.利用几何代数多维统一、高维计算适应的优势，设计了基于几何代数meet算子和有向半空间划分理论的时空宗地meet算法.从三维地籍和时空数据建模出发，在共形几何代数和时空代数范畴中，给出了三维、四维时空宗地的定义和表达.同时，以宗地数据的拓扑计算为例，将该算法运用于三维时空宗地拓扑计算场景——历史回溯中，取得了良好的效果.该算法的理念同样适用于四维时空宗地的历史回溯meet求解.

几何代数；时空拓扑关系计算；meet算子；时空宗地求交

A study on meet computation of spatio-temporal parcel based on conformal geometric algebra. Journal of Zhejiang University(Science Edition), 2017,44(1):076-082

几何代数，是用代数的语言来描述和表达图形的操作，通过引入Clifford积，实现几何不变量和协变量的代数表示和计算[1].凭借共形几何代数与坐标无关及多维统一的高效运算等特性，其被引入多维时空的统一表达与分析，并可进行不依赖于坐标的高维空间几何计算[2].时空GIS建模和表达需要从时空观和基础数学理论进行革新.罗文等[3]在共形几何代数框架中对地理空间的多维对象进行了建模，实现了三维场景的可视化和交互操作.宗真等[4]利用与Grassman分级结构一致的几何代数外积表达，构建了三角网模型，同时研究了三角网meet求交算法，并将其应用于南极冰盖消融平衡线的模拟计算.

本文从三维地籍和时空数据建模出发，分析现下地籍时空数据在建模和时空分析中的限制[5-8]，将几何代数理论用于时空宗地的建模和表达中，同时设计相应的时空宗地meet算子，并将其应用于时空宗地的拓扑关系计算.最后，以建德市白沙村约20 a的时空宗地数据为例进行建模，实现宗地历史回溯场景的求解.

1 时空宗地几何代数表达和meet算子构建

1.1 时空宗地的几何代数表达

“时空宗地”一词最早由史云飞等[9]在进行四维地籍的研究时提出，时空宗地是由宗地权属边界(包括时间边界和空间边界)对四维时空或三维时空进行剖分而形成的时空单元.根据时空宗地空间边界的不同形态，目前实际存在的时空宗地有三维和四维2种，三维时空宗地指地表宗地+时间维，其空间边界为二维多边形，几何表现为以宗地空间边界围成的多边形为底、以量化后的生存时间总长为棱的棱柱(见图1)；四维时空宗地指地上或地下宗地+时间维，空间边界为三维多面体，用来描述四维时空宗地几何形状的单位几何体是超立方体，其时间t轴同时垂直于x、y、z轴，每个三维宗地实体的面是一个以生存时间总长为棱的棱柱的底面(见图2).

图1 三维时空宗地几何形态Fig.1 Three-dimensional geometry of spatio-temporal parcel

图2 四维时空宗地几何形态(投影后)Fig.2 Four-dimensional geometry ofspatio-temporal parcel

时空宗地的立方体模型与几何代数的正交基组向量表示形式一致，几何代数在三维时空中，使用3个正交基向量e1，e2，e3表达时空单点P：

P=x·e1+y·e2+ct·e3.

(1)

而共形几何代数则是在此基础上引入零点e0和无穷远点e∞，构建共形空间C3，提高子空间的表达能力，实现点、直线、平面、圆、球等对象的基本表达.同理，几何代数往四维时空扩展，被称为时空代数，时空代数中使用4个正交基向量：e1，e2，e3，e4对时空单点进行表达[10-13]:

P=x·e1+y·e2+z·e3+ct·e4.

(2)

1.2 时空宗地meet算子构建

Meet关系在时空拓扑中意指相接关系，由于时空宗地是对四维时空的连续覆盖[14]，meet关系是时空宗地重要的时空拓扑关系，不仅可以用来研究2个时空宗地间的时空关系，还可以用来研究时空宗地的自身演化过程，甚至，考虑到时空宗地的特殊性，meet计算能够在特定视角实现对时空宗地的剖分和观察.故而，本文所定义的meet算子不仅可用于时空相接关系的计算，还可用于时空元素，例如时空切面、时空切体与时空宗地的时空相交关系计算，是适应多维和高维共形几何代数的meet算子，在地理时空分析领域可具体实现和扩展.

1.2.1 几何代数meet算子和half-space理论

1.2.1.1meet算子

现实空间中的对象求交最后往往转换成对各个基本元素相交关系的判断，包括点、线、面、圆等.通过组合可以实现空间维度扩张和收缩的外积和内积，以及可以表达对象正交补空间的对偶运算.共形几何代数meet算子，在3D线性代数基础上进行统一和扩展，可应用于n维空间的子空间求交[2].

Meet算子的计算借助于最小超空间和内积.最小超空间，即容纳对象的最小空间在一个维度上的扩展.对于简单多维对象，meet算子可以使用对象的伪标量来定义最小超空间，而对于复杂多维子空间对象，需要借助对象的join运算来定义对象的最小超空间[2,15].对于对象的join运算，这里不作展开.

(3)

式(3)中，对于简单子空间对象，其代表A、B最小子空间的J可用A和B的伪标量I代替.

利用几何代数meet算子可以对基本元素：点、线、面、圆的相交关系进行代数求解.其中，线线求交，两直线异面或平行，其meet求解结果为无穷点，即两直线相交于无穷点，也即不相交；直线与平面求交，直线和平面的管线有3种：相交、不相交、直线在平面上，需要对其meet结果和平方进行联合判断；面面求交，或平行或相交，根据其meet结果平方与0的比较结果来判断[4].

表1 基本几何元素的几何代数meet求交计算

1.2.1.2 Half-space

几何代数中基本几何对象的meet求交，针对的对象是无边界的、在其所在的维度子空间无限延伸的，而时空宗地却是有明确权属边界的对象.将针对无限子空间的meet算子应用于有限几何体的meet求交，则需要在几何代数基本meet计算后，对meet结果的有效性进行判断.

CAMERON等[16]在STOLFI等[17]提出的有向摄影几何理论基础上，对共形空间R3+1,1中各加1所表示的正、负空间(e+、e-)进行探讨，提出了half-space(半空间)的概念.半空间是指用n-1维的实体A去分割n维实体B，以实体A为界，划分B所在的空间的任一侧空间，称作半空间，其由一系列0维的点组成.例如：0维有向点分割1维直线空间，1维有向直线分割二维平面空间，2维有向平面分割3维体空间.在有向共形空间中，点、线、面、圆、球等都被赋予方向性，例如：A∧B∧n和B∧A∧n代表的是不同方向的2个直线对象，借鉴线和圆的Grassman层次结构的一致性，对代数所表达的直线方向的一致性进行判断，可以将无穷点视作一个点，将线弯曲成圆，按同一方向排列的点的外积所表示的线对象是相等的，即为同一个对象，如图3所示.半空间理论中引入求t值的表达式可以判断两直线方向的一致性.式(4)中，若表示的直线与所表示的直线方向一致，则t值大于0[16].

t=(A∧P∧n)(A∧B∧n).

(4)

图3 方向一致性判断Fig.3 The direction consistency judgement

1.2.2 时空宗地meet算子

在时空宗地meet算子中，对基本元素的交并关系求解，可通过几何代数基本要素构建子空间(blade)直接参与meet求解[4].对于具有明确边界约束的时空宗地，则先通过构建子空间参与基本meet运算后，对meet结果进行维度解析和对象解析.针对解析后的结果，通过有向共形几何空间的半空间理论构建统一的算子，对meet的时空宗地进行meet有效性判断.

时空宗地是在其所在空间中连续覆盖不重叠的几何体，时空宗地间原则上不存在相交的拓扑关系[9,14].近年来，由于土地资源过热，时空宗地变更频繁，且时空宗地间关系越来越复杂，则对时空宗地自身的演化进程以及演化过程中的邻里关系进行研究显得尤为重要.而这往往需要获取时空宗地的历史形态和历史关联.三维时空宗地是以宗地空间边界多边形为底、以生存时长为棱的平行多棱柱.在获取时空宗地的历史信息时，通过求解时空宗地平行多棱柱之间底面与顶面的meet关系，可以分析时空宗地的变更情况；通过求解时空切面与时空宗地的meet关系，可以获取某一时空的土地利用现状.

在进行以上2种meet场景求解时，需要先划分时空宗地结构：时空近似体+时间线段+空间多边形.时空近似体通过对空间近似对象在时间上进行均匀延伸构建.常见的空间近似对象有最小外包立方体、最小外包n边平行棱柱和最小外包球3种.时空近似体的选取取决于时空对象的分布情况，根据其在时间和空间上的分布特征进行统计分析，以求取最佳时空近似体.例如，可借助“空间多边形紧凑度”和“生存周期差异性”2个指标进行具体分析．本文选取最小外包球作为示例，对时空宗地的meet计算进行阐述.在此基础上，可借助时空宗地最小外包球、时空宗地空间边界多边形和时空宗地时间棱，讨论上述2种meet场景的求解.其中，球对象作为几何代数的基本要素，可以直接使用几何代数的meet算子进行求交，时空宗地空间边界多边形与时间棱线段对象则需要另作讨论.据此，本文探讨了半空间理论支持下的点与线段、点与多边形、线段与线段、线段与多边形、多边形与多边形的meet关系的求解，其中，点与线段和点与多边形又是这5类对象meet求解的基础.

表2 三维时空宗地meet场景讨论

Table 2 Discussion on meet scene for three-dimensional spatio-temporal parcel

三维时空宗地meet场景三维时空宗地meet场景示意图所需求解meet对象时空要素与时空宗地时间切面与时间棱：平面与直线、平面与线段时空宗地与时空宗地空间边界与空间边界：球与球、平面与平面、线段与线段、点与多边形

1.2.2.1 点与线段、线段与线段

要判断一个点对象P是否和一个线段对象meet，首先通过几何代数meet求解点P和该线段所属直线L的关系，若相交则表明点对象处于线段对象或线段对象延长线上.要进一步确定点对象是否和线段对象meet，需要利用线段的0维有向端点划分1维直线的空间，构建表达式求解参数t值，判断点处在哪一半空间.式(5)和(6)中，点在线段所在直线上，当(A∧P∧n)与L:(A∧B∧n)所表示的直线方向一致时，t1>0，当P点与A点重合时，t1=0，t2同t1.若不考虑点已在线段所在直线上的情况，图4中t1和t2同时大于0表示的是一块包含线段AB的二维区域，需要先将相交点P约束在一维线段AB之上，通过几何代数基本元素的meet计算.

t1=(A∧P∧n)L,

(5)

t2=(P∧B∧n).

(6)

图4 点P与线段AB的关系判断Fig.4 Judgement of the relationship between thepoint P and the line segment AB

点与线段以及线段所在直线的相交关系可以分为：点与线段端点重合，点在线段上，点在线段延长线上.点不与线段所在直线相交也分为：点在直线左边，点在直线右边.要进一步确定点对象是否和线段对象相交，需要根据t1和t2判断.如图5所示，联合κ值与t值进行判断，可得到点与线段的相对关系.

结合图5整理点与线段的关系，两者之间可能存在的关系的推导过程见表3.

图5 点P与线段AB的关系Fig.5 The relationship between the point P andthe line segment AB注 κ=grade((AI)(A∧B∧n)),t1=(A∧P∧n)(A∧B∧n),t2=(P∧B∧n)(A∧B∧n).

线段与线段的meet，用几何代数meet排除平行和异面的情况后，基于点与线段的meet有效性判断理论，判断交点的有效性.交点P需要同时满足与线段AB和CD的meet关系，见图6，参考点与线段间的关系计算不再赘述.

1.2.2.2 点与多边形、多边形与多边形

和零维有向点划分一维线的半空间相同，一维有向线划分出二维面的半空间.多边形可以视作一系列有向线首尾相接形成的几何图形，多边形所包络的区域可以视作一系列有向直线划分的平面半空间的交集.通过待求meet的点对象和多边形有向边界直线外积构成的有向面的方向，可以判断该点对象是否与该多边形对象围成的区域meet.此外，基于点与多边形、线段与线段的meet算子，可以构建多边形之间的meet算子，见图7.

表3 点与线段关系概况

图6 线段AB与CD关系的判断Fig.6 Judgement of the relationship between the linesegment AB and the line segment CD

图7 点P与多边形ABCD关系判断Fig.7 Judgement of the relationship betweenthe point P and the polygon ABCD

2 算法实现与案例验证

2.1 算法描述与流程

时空宗地meet计算中基本共形几何代数元素的meet可以直接使用共形几何代数自带meet算子进行求解，其中主要的具有边界约束的几何对象，则需在原meet算子基础上引入有向半空间理论进行扩展.基于文中对时空宗地meet计算所做的阐述和讨论，以三维时空宗地历史回溯为例，对时空要素和三维时空宗地的meet进行求解，提出了具体的三维时空宗地meet算法流程.鉴于三维时空宗地和四维时空宗地表达形式的统一性，对于四维时空宗地的meet求解，只要在三维时空宗地构建的针对具有边界约束的几何对象的meet算子中，对点与多面体、多面体与多面体的meet求解再进行具体讨论，构建相关的meet算子即可.三维时空宗地历史回溯meet算法流程如图8所示.

对三维时空宗地的历史回溯meet算法步骤如下：

(1)对输入的时空宗地使用共形几何代数进行编码转换，对输入的观测时间(回溯时间)使用几何代数外积构建时间切面S;

(2)按一定组织顺序遍历时空宗地集合中的所有时空宗地对象;

(3)判断时空切面与时空宗地最小外包球MBC是否meet;

(4)若meet，判断时间切面与时空宗地的任一时间棱L是否meet:

1)求解时间切面S与时间棱L所在直线C的meet关系，得到meet结果M；

2)若S与Cmeet，对M进行维度解析和对象解析，提取交点信息；

3)使用有向半空间Omeet求解交点对于时间棱线段L的有效性.若相交，则将时空宗地的空间边界正射投影于时间切面并输出结果.

图8 基于meet计算的三维时空宗地历史回溯场景求解Fig.8 The history tracebacking scene resolution of three dimensionalspatio-temporal parcel based on meet computation

2.2 案例验证

以杭州建德市新安江镇白沙村自20世纪90年代登记以来的地籍数据为例进行算法验证，分别选取1996年1月1日、2002年1月1日、2006年1月1日、2010年1月1日为时间节点，构建时间扫描面，与时空宗地meet求交. 图 9(a)中展示的是轴构建的时空中三维时空宗地的形态，即宗地在时间维度上展开，图 9(b)、(c)、(d)展示了时间切面按一定时间采样间隔构建扫描面，与时空宗地进行meet计算的动态过程：图9(b)为2002年1月1日的时间切面与时空宗地meet计算的结果，反映了2002年1月1日的宗地现状；图9(c)为2006年1月1日的时间切面与时空宗地meet计算的结果，反映了2006年1月1日的宗地现状；图9(d)为2010年1月1日的时间切面与时空宗地meet计算的结果，反映了2010年1月1日的宗地现状.图9(b)、(c)、(d)中，不同颜色的多棱柱分别代表不同类型的土地用途，蓝紫色平面为时间扫描面，突出显示的红色多边形为时间扫描面和时空宗地meet求交的结果.相应地，图10中的(a)、(b)、(c)、(d)分别为在ArcGIS平台上进行渲染的1996年1月1日、2002年1月1日、2006年1月1日、2010年1月1日的实际宗地确权状况.

将求交结果与现实登记中宗地确权结果相比较，即图9与图10的比较.结果显示，基于时空宗地meet算子计算的历史节点上的宗地确权结果与实际宗地确权结果吻合，说明基于几何代数理论构建的时空宗地meet计算流程,能够较好地应用于宗地时空拓扑的计算.

本文通过案例验证了基于几何代数的三维时空宗地表达和meet计算的可行性，同时，为四维时空宗地的几何代数表达和拓扑计算提供了时空宗地表达模型以及拓扑meet算子构建的理论基础和研究思路.

图9 基于时空宗地meet算子的时间扫描面与时空宗地求交Fig.9 The meet computation between time sweep planeand spatio-temporal parcel based on meet operator

图10 实际宗地确权结果Fig.10 The parcel registration results

3 结论与展望

处于地理世界中的物体具有很强的时空依赖性和动态性，时空作为物体的固有属性，对其变化过程的研究具有重要意义.目前，对于时空变化过程的研究多基于关系数据库检索，此方法受限于数据库的表达和检索的水平.本文在现有时空宗地数据模型研究的基础上，对几何代数的时空表达、交并计算、有向半空间划分等内容展开了研究，利用几何代数多维统一、高维计算适应的优势，设计了基于几何代数meet算子和有向半空间划分理论的时空宗地meet算法.并探讨了时空宗地变化过程中的2种meet场景，针对时空宗地meet场景涉及的时空宗地最小外包球、时空宗地空间边界多边形、时空宗地时间棱的meet求解展开了具体的讨论，最后从三维时空宗地历史回溯角度出发，设计了三维时空历史回溯的meet算法.实验证明，该meet算法能在脱离传统关系数据库查找的模式下，较好地满足历史回溯和时空变化过程可视化展示的需求，相比于传统方法，不受限于关系数据库的表达和检索能力，更加灵活，且易扩展.该算法的理念同样适用于四维时空宗地的历史回溯meet求解.据此，后续的重点工作主要为:对四维时空宗地的几何结构组成要素(多面体)的meet计算进行扩展，对时空超平面等四维时空基本元素的特性进行理解和表达，对三维、四维时空宗地同时存在的多维混合时空meet进行扩展.

[1] 李洪波.共形几何代数——几何代数的新理论和计算框架[J].计算机辅助设计与图形学学报，2005,17(11):2383-2393. LI H B. Conformal geometric algebra-A new framework for computational geometry[J]. Journal of Computer Aided Design & Computer Graphics,2005,17(11):2383-2393.

[2] DORST L, FONTIJNE D, MANN S. Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry[M]. San Francisco: Morgan Kaufmann Publishers Inc,2007.

[3] 罗文,袁林旺,俞肇元,等.基于共形几何代数的三维地理场景建模与表达[J].测绘通报,2012(10):28-31. LUO W, YUAN L W, YU Z Y, et al. Conformal geometric algebra-based three dimensional scene modeling and expressing [J]. Bulletin of Surveying and Mapping,2012(10):28-31.

[4] 宗真,袁林旺,罗文,等.三角网求交的共形几何代数算法[J].测绘学报,2014(2):200-207. ZONG Z, YUAN L W, LUO W, et al. Triangulation intersection algorithm based on conformal geometric algebra [J]. Acta Geodaetica et Cartographica Sinica,2014(2):200-207.

[5] DÖNER F, THOMPSON R, STOTER J, et al. 4D cadastres: First analysis of legal, organizational and technical impact - With a case study on utility networks[J]. Land Use Policy,2010,27(4):1068-1081.

[6] DÖNER F, THOMPSON R, STOTER J, et al. Solutions for 4D cadastre - with a case study on utility networks[J]. International Journal of Geographical Information Science,2011,25(7):1173-1189.

[7] SONG W, YANG X. A spatio-temporal cadastral data model based on space-time composite model[C]// International Conference on Geoinformatics. Kaifeng: IEEE,2013:1-4.

[8] CLARAMUNT C, JIANG B. An integrated representation of spatial and temporal relationships between evolving regions[J]. Journal of Geographical Systems,2001,3(4):411-428.

[9] 史云飞,郭仁忠,李霖,等.四维地籍的建立与分析[J].武汉大学学报：信息科学版,2014,39(3):322-326. SHI Y F, GUO R Z, LI L, et al. Establishment and analysis 4D cadastre[J]. Geomatics and Information Science of Wuhan University,2014,39(3):322-326.

[10] 俞肇元,袁林旺,胡勇,等.基于几何代数的矢量时空数据表达与建模方法[J].地球信息科学学报,2012,14(1):67-73. YU Z Y,YUAN L W, HU Y, et al. Spatio-temporal vector data modeling based on geometric algebra[J].Journal of Geo-Information Science,2012,14(1):67-73.

[11] HESTENES D. Space-Time Algebra[M]. Switzerland: Springer International Publishing,1966.

[12] 李武明,张雪峰.时空平面的Clifford代数与Abel复数系统[J].吉林大学学报：理学版,2007,45(5):748-752. LI W M, ZHANG X F. Clifford algebra of spacetime plane and Abel complex number system[J]. Journal of Jilin University: Science Edition,2007,45(5):748-752.

[13] 李武明.时空代数的若干性质及应用[J].通化师范学院学报,2004,25(8):1-3. LI W M. The properties and application of the space time algebra[J]. Journal of Tonghua Teachers College,2004,25(8):1-3.

[14] 张玲玲,史云飞,郭仁忠,等.三维地籍产权体的定义与表达[J].地球信息科学学报,2010,12(2):207-213. ZHANG L L, SHI Y F, GUO R Z, et al. Definition and representation of property volume of three dimensional cadastre[J]. Journal of Geo-Information Science,2010,12(2):207-213.

[15] 袁林旺.基于几何代数的多维统一GIS[M].北京：科学出版社,2012. YUAN L W. Multi-dimensional Unified GIS Base on Geometric Algebra [M].Beijing：Science Press,2012.

[16] CAMERON J, LASENBY J. Oriented conformal geometric algebra[J]. Advances in Applied Clifford Algebras,2008,18(3/4):523-538.

[17] STOLFI J. Oriented Projective Geometry: A Framework for Geometric Computations[M]. Boston: Academic Press,1991.

WANG Qiaoyan1,2, JIANG Xiaomin1,2, ZHANG Feng1,2, DU Zhenhong1,2, LIU Renyi1,2

(1.ZhejiangProvincialKeyLaboratoryofResourcesandEnvironmentalInformationSystem,ZhejiangUniversity,Hangzhou310028,China; 2.DepartmentofEarthSciences,ZhejiangUniversity,Hangzhou310027,China)

Geometric algebra has advantages in solving problems of geometric object modeling and multidimensional data analysis. This paper conducts studies on the meaning, construction and application of its two operators: meet and join. By exploiting their merits of multidimensional consistency and high dimension adaptivity, we propose a spatio-temporal parcel meet algorithm. We also give definitions and representations of 3D and 4D spatio-temporal parcel within the domain of conformal geometric algebra and spatio-temporal algebra. The algorithm is successfully applied to conduct the topology computation of three dimension spatio-temporal parcels and achieves satisfactory results. . Experiment show that our approach provides a novel and effective way for the representation and topology computation of three dimensional spatio-temporal parcel and hopefully a new resolution for four dimensional spatio-temporal parcels.

geometric algebra; spatio-temporal topology relation computation; meet operator; spatio-temporal parcel meet

2016-01-05.

国家自然科学基金资助项目(41471313,41101356,41101371,41171321)；国家科技基础性工作专项(2012FY112300)；海洋公益性行业科研专项经费资助(2015418003,201305012)；浙江省攻关项目(2014C33G20,2013C33051).

王巧燕(1991-)，ORCID:http://orcid.org/0000-0002-5636-8184,女，硕士研究生，主要从事时空数据建模研究，E-mail:qywangZJUGIS@163.com.

*通信作者，ORCID:http://orcid:org/0000-0003-1475-8480,E-mail:zfcarnation@zju.edu.cn.

10.3785/j.issn.1008-9497.2017.01.012

P208

A

1008-9497(2017)01-076-08