王巧燕，蔣曉敏，張 豐*，杜震洪，劉仁義

(1. 浙江大學(xué) 浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室， 浙江 杭州 310028；2. 浙江大學(xué) 地球科學(xué)學(xué)院， 浙江 杭州 310027)

基于幾何代數(shù)的時(shí)空宗地meet計(jì)算研究

王巧燕1,2，蔣曉敏1,2，張 豐1,2*，杜震洪1,2，劉仁義1,2

(1. 浙江大學(xué) 浙江省資源與環(huán)境信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室， 浙江 杭州 310028；2. 浙江大學(xué) 地球科學(xué)學(xué)院， 浙江 杭州 310027)

根據(jù)幾何代數(shù)在地理空間對(duì)象建模和多維數(shù)據(jù)分析應(yīng)用的特點(diǎn)，研究了共形幾何代數(shù)交/并(meet/join)算子的含義、構(gòu)建和應(yīng)用.利用幾何代數(shù)多維統(tǒng)一、高維計(jì)算適應(yīng)的優(yōu)勢(shì)，設(shè)計(jì)了基于幾何代數(shù)meet算子和有向半空間劃分理論的時(shí)空宗地meet算法.從三維地籍和時(shí)空數(shù)據(jù)建模出發(fā)，在共形幾何代數(shù)和時(shí)空代數(shù)范疇中，給出了三維、四維時(shí)空宗地的定義和表達(dá).同時(shí)，以宗地?cái)?shù)據(jù)的拓?fù)溆?jì)算為例，將該算法運(yùn)用于三維時(shí)空宗地拓?fù)溆?jì)算場(chǎng)景——?dú)v史回溯中，取得了良好的效果.該算法的理念同樣適用于四維時(shí)空宗地的歷史回溯meet求解.

幾何代數(shù)；時(shí)空拓?fù)潢P(guān)系計(jì)算；meet算子；時(shí)空宗地求交

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

幾何代數(shù)，是用代數(shù)的語言來描述和表達(dá)圖形的操作，通過引入Clifford積，實(shí)現(xiàn)幾何不變量和協(xié)變量的代數(shù)表示和計(jì)算[1].憑借共形幾何代數(shù)與坐標(biāo)無關(guān)及多維統(tǒng)一的高效運(yùn)算等特性，其被引入多維時(shí)空的統(tǒng)一表達(dá)與分析，并可進(jìn)行不依賴于坐標(biāo)的高維空間幾何計(jì)算[2].時(shí)空GIS建模和表達(dá)需要從時(shí)空觀和基礎(chǔ)數(shù)學(xué)理論進(jìn)行革新.羅文等[3]在共形幾何代數(shù)框架中對(duì)地理空間的多維對(duì)象進(jìn)行了建模，實(shí)現(xiàn)了三維場(chǎng)景的可視化和交互操作.宗真等[4]利用與Grassman分級(jí)結(jié)構(gòu)一致的幾何代數(shù)外積表達(dá)，構(gòu)建了三角網(wǎng)模型，同時(shí)研究了三角網(wǎng)meet求交算法，并將其應(yīng)用于南極冰蓋消融平衡線的模擬計(jì)算.

本文從三維地籍和時(shí)空數(shù)據(jù)建模出發(fā)，分析現(xiàn)下地籍時(shí)空數(shù)據(jù)在建模和時(shí)空分析中的限制[5-8]，將幾何代數(shù)理論用于時(shí)空宗地的建模和表達(dá)中，同時(shí)設(shè)計(jì)相應(yīng)的時(shí)空宗地meet算子，并將其應(yīng)用于時(shí)空宗地的拓?fù)潢P(guān)系計(jì)算.最后，以建德市白沙村約20 a的時(shí)空宗地?cái)?shù)據(jù)為例進(jìn)行建模，實(shí)現(xiàn)宗地歷史回溯場(chǎng)景的求解.

1 時(shí)空宗地幾何代數(shù)表達(dá)和meet算子構(gòu)建

1.1 時(shí)空宗地的幾何代數(shù)表達(dá)

“時(shí)空宗地”一詞最早由史云飛等[9]在進(jìn)行四維地籍的研究時(shí)提出，時(shí)空宗地是由宗地權(quán)屬邊界(包括時(shí)間邊界和空間邊界)對(duì)四維時(shí)空或三維時(shí)空進(jìn)行剖分而形成的時(shí)空單元.根據(jù)時(shí)空宗地空間邊界的不同形態(tài)，目前實(shí)際存在的時(shí)空宗地有三維和四維2種，三維時(shí)空宗地指地表宗地+時(shí)間維，其空間邊界為二維多邊形，幾何表現(xiàn)為以宗地空間邊界圍成的多邊形為底、以量化后的生存時(shí)間總長(zhǎng)為棱的棱柱(見圖1)；四維時(shí)空宗地指地上或地下宗地+時(shí)間維，空間邊界為三維多面體，用來描述四維時(shí)空宗地幾何形狀的單位幾何體是超立方體，其時(shí)間t軸同時(shí)垂直于x、y、z軸，每個(gè)三維宗地實(shí)體的面是一個(gè)以生存時(shí)間總長(zhǎng)為棱的棱柱的底面(見圖2).

圖1 三維時(shí)空宗地幾何形態(tài)Fig.1 Three-dimensional geometry of spatio-temporal parcel

圖2 四維時(shí)空宗地幾何形態(tài)(投影后)Fig.2 Four-dimensional geometry ofspatio-temporal parcel

時(shí)空宗地的立方體模型與幾何代數(shù)的正交基組向量表示形式一致，幾何代數(shù)在三維時(shí)空中，使用3個(gè)正交基向量e1，e2，e3表達(dá)時(shí)空單點(diǎn)P：

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

(1)

而共形幾何代數(shù)則是在此基礎(chǔ)上引入零點(diǎn)e0和無窮遠(yuǎn)點(diǎn)e∞，構(gòu)建共形空間C3，提高子空間的表達(dá)能力，實(shí)現(xiàn)點(diǎn)、直線、平面、圓、球等對(duì)象的基本表達(dá).同理，幾何代數(shù)往四維時(shí)空擴(kuò)展，被稱為時(shí)空代數(shù)，時(shí)空代數(shù)中使用4個(gè)正交基向量：e1，e2，e3，e4對(duì)時(shí)空單點(diǎn)進(jìn)行表達(dá)[10-13]:

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

(2)

1.2 時(shí)空宗地meet算子構(gòu)建

Meet關(guān)系在時(shí)空拓?fù)渲幸庵赶嘟雨P(guān)系，由于時(shí)空宗地是對(duì)四維時(shí)空的連續(xù)覆蓋[14]，meet關(guān)系是時(shí)空宗地重要的時(shí)空拓?fù)潢P(guān)系，不僅可以用來研究2個(gè)時(shí)空宗地間的時(shí)空關(guān)系，還可以用來研究時(shí)空宗地的自身演化過程，甚至，考慮到時(shí)空宗地的特殊性，meet計(jì)算能夠在特定視角實(shí)現(xiàn)對(duì)時(shí)空宗地的剖分和觀察.故而，本文所定義的meet算子不僅可用于時(shí)空相接關(guān)系的計(jì)算，還可用于時(shí)空元素，例如時(shí)空切面、時(shí)空切體與時(shí)空宗地的時(shí)空相交關(guān)系計(jì)算，是適應(yīng)多維和高維共形幾何代數(shù)的meet算子，在地理時(shí)空分析領(lǐng)域可具體實(shí)現(xiàn)和擴(kuò)展.

1.2.1 幾何代數(shù)meet算子和half-space理論

1.2.1.1meet算子

現(xiàn)實(shí)空間中的對(duì)象求交最后往往轉(zhuǎn)換成對(duì)各個(gè)基本元素相交關(guān)系的判斷，包括點(diǎn)、線、面、圓等.通過組合可以實(shí)現(xiàn)空間維度擴(kuò)張和收縮的外積和內(nèi)積，以及可以表達(dá)對(duì)象正交補(bǔ)空間的對(duì)偶運(yùn)算.共形幾何代數(shù)meet算子，在3D線性代數(shù)基礎(chǔ)上進(jìn)行統(tǒng)一和擴(kuò)展，可應(yīng)用于n維空間的子空間求交[2].

Meet算子的計(jì)算借助于最小超空間和內(nèi)積.最小超空間，即容納對(duì)象的最小空間在一個(gè)維度上的擴(kuò)展.對(duì)于簡(jiǎn)單多維對(duì)象，meet算子可以使用對(duì)象的偽標(biāo)量來定義最小超空間，而對(duì)于復(fù)雜多維子空間對(duì)象，需要借助對(duì)象的join運(yùn)算來定義對(duì)象的最小超空間[2,15].對(duì)于對(duì)象的join運(yùn)算，這里不作展開.

(3)

式(3)中，對(duì)于簡(jiǎn)單子空間對(duì)象，其代表A、B最小子空間的J可用A和B的偽標(biāo)量I代替.

利用幾何代數(shù)meet算子可以對(duì)基本元素：點(diǎn)、線、面、圓的相交關(guān)系進(jìn)行代數(shù)求解.其中，線線求交，兩直線異面或平行，其meet求解結(jié)果為無窮點(diǎn)，即兩直線相交于無窮點(diǎn)，也即不相交；直線與平面求交，直線和平面的管線有3種：相交、不相交、直線在平面上，需要對(duì)其meet結(jié)果和平方進(jìn)行聯(lián)合判斷；面面求交，或平行或相交，根據(jù)其meet結(jié)果平方與0的比較結(jié)果來判斷[4].

表1 基本幾何元素的幾何代數(shù)meet求交計(jì)算

1.2.1.2 Half-space

幾何代數(shù)中基本幾何對(duì)象的meet求交，針對(duì)的對(duì)象是無邊界的、在其所在的維度子空間無限延伸的，而時(shí)空宗地卻是有明確權(quán)屬邊界的對(duì)象.將針對(duì)無限子空間的meet算子應(yīng)用于有限幾何體的meet求交，則需要在幾何代數(shù)基本meet計(jì)算后，對(duì)meet結(jié)果的有效性進(jìn)行判斷.

CAMERON等[16]在STOLFI等[17]提出的有向攝影幾何理論基礎(chǔ)上，對(duì)共形空間R3+1,1中各加1所表示的正、負(fù)空間(e+、e-)進(jìn)行探討，提出了half-space(半空間)的概念.半空間是指用n-1維的實(shí)體A去分割n維實(shí)體B，以實(shí)體A為界，劃分B所在的空間的任一側(cè)空間，稱作半空間，其由一系列0維的點(diǎn)組成.例如：0維有向點(diǎn)分割1維直線空間，1維有向直線分割二維平面空間，2維有向平面分割3維體空間.在有向共形空間中，點(diǎn)、線、面、圓、球等都被賦予方向性，例如：A∧B∧n和B∧A∧n代表的是不同方向的2個(gè)直線對(duì)象，借鑒線和圓的Grassman層次結(jié)構(gòu)的一致性，對(duì)代數(shù)所表達(dá)的直線方向的一致性進(jìn)行判斷，可以將無窮點(diǎn)視作一個(gè)點(diǎn)，將線彎曲成圓，按同一方向排列的點(diǎn)的外積所表示的線對(duì)象是相等的，即為同一個(gè)對(duì)象，如圖3所示.半空間理論中引入求t值的表達(dá)式可以判斷兩直線方向的一致性.式(4)中，若表示的直線與所表示的直線方向一致，則t值大于0[16].

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

(4)

圖3 方向一致性判斷Fig.3 The direction consistency judgement

1.2.2 時(shí)空宗地meet算子

在時(shí)空宗地meet算子中，對(duì)基本元素的交并關(guān)系求解，可通過幾何代數(shù)基本要素構(gòu)建子空間(blade)直接參與meet求解[4].對(duì)于具有明確邊界約束的時(shí)空宗地，則先通過構(gòu)建子空間參與基本meet運(yùn)算后，對(duì)meet結(jié)果進(jìn)行維度解析和對(duì)象解析.針對(duì)解析后的結(jié)果，通過有向共形幾何空間的半空間理論構(gòu)建統(tǒng)一的算子，對(duì)meet的時(shí)空宗地進(jìn)行meet有效性判斷.

時(shí)空宗地是在其所在空間中連續(xù)覆蓋不重疊的幾何體，時(shí)空宗地間原則上不存在相交的拓?fù)潢P(guān)系[9,14].近年來，由于土地資源過熱，時(shí)空宗地變更頻繁，且時(shí)空宗地間關(guān)系越來越復(fù)雜，則對(duì)時(shí)空宗地自身的演化進(jìn)程以及演化過程中的鄰里關(guān)系進(jìn)行研究顯得尤為重要.而這往往需要獲取時(shí)空宗地的歷史形態(tài)和歷史關(guān)聯(lián).三維時(shí)空宗地是以宗地空間邊界多邊形為底、以生存時(shí)長(zhǎng)為棱的平行多棱柱.在獲取時(shí)空宗地的歷史信息時(shí)，通過求解時(shí)空宗地平行多棱柱之間底面與頂面的meet關(guān)系，可以分析時(shí)空宗地的變更情況；通過求解時(shí)空切面與時(shí)空宗地的meet關(guān)系，可以獲取某一時(shí)空的土地利用現(xiàn)狀.

在進(jìn)行以上2種meet場(chǎng)景求解時(shí)，需要先劃分時(shí)空宗地結(jié)構(gòu)：時(shí)空近似體+時(shí)間線段+空間多邊形.時(shí)空近似體通過對(duì)空間近似對(duì)象在時(shí)間上進(jìn)行均勻延伸構(gòu)建.常見的空間近似對(duì)象有最小外包立方體、最小外包n邊平行棱柱和最小外包球3種.時(shí)空近似體的選取取決于時(shí)空對(duì)象的分布情況，根據(jù)其在時(shí)間和空間上的分布特征進(jìn)行統(tǒng)計(jì)分析，以求取最佳時(shí)空近似體.例如，可借助“空間多邊形緊湊度”和“生存周期差異性”2個(gè)指標(biāo)進(jìn)行具體分析．本文選取最小外包球作為示例，對(duì)時(shí)空宗地的meet計(jì)算進(jìn)行闡述.在此基礎(chǔ)上，可借助時(shí)空宗地最小外包球、時(shí)空宗地空間邊界多邊形和時(shí)空宗地時(shí)間棱，討論上述2種meet場(chǎng)景的求解.其中，球?qū)ο笞鳛閹缀未鷶?shù)的基本要素，可以直接使用幾何代數(shù)的meet算子進(jìn)行求交，時(shí)空宗地空間邊界多邊形與時(shí)間棱線段對(duì)象則需要另作討論.據(jù)此，本文探討了半空間理論支持下的點(diǎn)與線段、點(diǎn)與多邊形、線段與線段、線段與多邊形、多邊形與多邊形的meet關(guān)系的求解，其中，點(diǎn)與線段和點(diǎn)與多邊形又是這5類對(duì)象meet求解的基礎(chǔ).

表2 三維時(shí)空宗地meet場(chǎng)景討論

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

三維時(shí)空宗地meet場(chǎng)景三維時(shí)空宗地meet場(chǎng)景示意圖所需求解meet對(duì)象時(shí)空要素與時(shí)空宗地時(shí)間切面與時(shí)間棱：平面與直線、平面與線段時(shí)空宗地與時(shí)空宗地空間邊界與空間邊界：球與球、平面與平面、線段與線段、點(diǎn)與多邊形

1.2.2.1 點(diǎn)與線段、線段與線段

要判斷一個(gè)點(diǎn)對(duì)象P是否和一個(gè)線段對(duì)象meet，首先通過幾何代數(shù)meet求解點(diǎn)P和該線段所屬直線L的關(guān)系，若相交則表明點(diǎn)對(duì)象處于線段對(duì)象或線段對(duì)象延長(zhǎng)線上.要進(jìn)一步確定點(diǎn)對(duì)象是否和線段對(duì)象meet，需要利用線段的0維有向端點(diǎn)劃分1維直線的空間，構(gòu)建表達(dá)式求解參數(shù)t值，判斷點(diǎn)處在哪一半空間.式(5)和(6)中，點(diǎn)在線段所在直線上，當(dāng)(A∧P∧n)與L:(A∧B∧n)所表示的直線方向一致時(shí)，t1>0，當(dāng)P點(diǎn)與A點(diǎn)重合時(shí)，t1=0，t2同t1.若不考慮點(diǎn)已在線段所在直線上的情況，圖4中t1和t2同時(shí)大于0表示的是一塊包含線段AB的二維區(qū)域，需要先將相交點(diǎn)P約束在一維線段AB之上，通過幾何代數(shù)基本元素的meet計(jì)算.

t1=(A∧P∧n)L,

(5)

t2=(P∧B∧n).

(6)

圖4 點(diǎn)P與線段AB的關(guān)系判斷Fig.4 Judgement of the relationship between thepoint P and the line segment AB

點(diǎn)與線段以及線段所在直線的相交關(guān)系可以分為：點(diǎn)與線段端點(diǎn)重合，點(diǎn)在線段上，點(diǎn)在線段延長(zhǎng)線上.點(diǎn)不與線段所在直線相交也分為：點(diǎn)在直線左邊，點(diǎn)在直線右邊.要進(jìn)一步確定點(diǎn)對(duì)象是否和線段對(duì)象相交，需要根據(jù)t1和t2判斷.如圖5所示，聯(lián)合κ值與t值進(jìn)行判斷，可得到點(diǎn)與線段的相對(duì)關(guān)系.

結(jié)合圖5整理點(diǎn)與線段的關(guān)系，兩者之間可能存在的關(guān)系的推導(dǎo)過程見表3.

圖5 點(diǎn)P與線段AB的關(guān)系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，用幾何代數(shù)meet排除平行和異面的情況后，基于點(diǎn)與線段的meet有效性判斷理論，判斷交點(diǎn)的有效性.交點(diǎn)P需要同時(shí)滿足與線段AB和CD的meet關(guān)系，見圖6，參考點(diǎn)與線段間的關(guān)系計(jì)算不再贅述.

1.2.2.2 點(diǎn)與多邊形、多邊形與多邊形

和零維有向點(diǎn)劃分一維線的半空間相同，一維有向線劃分出二維面的半空間.多邊形可以視作一系列有向線首尾相接形成的幾何圖形，多邊形所包絡(luò)的區(qū)域可以視作一系列有向直線劃分的平面半空間的交集.通過待求meet的點(diǎn)對(duì)象和多邊形有向邊界直線外積構(gòu)成的有向面的方向，可以判斷該點(diǎn)對(duì)象是否與該多邊形對(duì)象圍成的區(qū)域meet.此外，基于點(diǎn)與多邊形、線段與線段的meet算子，可以構(gòu)建多邊形之間的meet算子，見圖7.

表3 點(diǎn)與線段關(guān)系概況

圖6 線段AB與CD關(guān)系的判斷Fig.6 Judgement of the relationship between the linesegment AB and the line segment CD

圖7 點(diǎn)P與多邊形ABCD關(guān)系判斷Fig.7 Judgement of the relationship betweenthe point P and the polygon ABCD

2 算法實(shí)現(xiàn)與案例驗(yàn)證

2.1 算法描述與流程

時(shí)空宗地meet計(jì)算中基本共形幾何代數(shù)元素的meet可以直接使用共形幾何代數(shù)自帶meet算子進(jìn)行求解，其中主要的具有邊界約束的幾何對(duì)象，則需在原meet算子基礎(chǔ)上引入有向半空間理論進(jìn)行擴(kuò)展.基于文中對(duì)時(shí)空宗地meet計(jì)算所做的闡述和討論，以三維時(shí)空宗地歷史回溯為例，對(duì)時(shí)空要素和三維時(shí)空宗地的meet進(jìn)行求解，提出了具體的三維時(shí)空宗地meet算法流程.鑒于三維時(shí)空宗地和四維時(shí)空宗地表達(dá)形式的統(tǒng)一性，對(duì)于四維時(shí)空宗地的meet求解，只要在三維時(shí)空宗地構(gòu)建的針對(duì)具有邊界約束的幾何對(duì)象的meet算子中，對(duì)點(diǎn)與多面體、多面體與多面體的meet求解再進(jìn)行具體討論，構(gòu)建相關(guān)的meet算子即可.三維時(shí)空宗地歷史回溯meet算法流程如圖8所示.

對(duì)三維時(shí)空宗地的歷史回溯meet算法步驟如下：

(1)對(duì)輸入的時(shí)空宗地使用共形幾何代數(shù)進(jìn)行編碼轉(zhuǎn)換，對(duì)輸入的觀測(cè)時(shí)間(回溯時(shí)間)使用幾何代數(shù)外積構(gòu)建時(shí)間切面S;

(2)按一定組織順序遍歷時(shí)空宗地集合中的所有時(shí)空宗地對(duì)象;

(3)判斷時(shí)空切面與時(shí)空宗地最小外包球MBC是否meet;

(4)若meet，判斷時(shí)間切面與時(shí)空宗地的任一時(shí)間棱L是否meet:

1)求解時(shí)間切面S與時(shí)間棱L所在直線C的meet關(guān)系，得到meet結(jié)果M；

2)若S與Cmeet，對(duì)M進(jìn)行維度解析和對(duì)象解析，提取交點(diǎn)信息；

3)使用有向半空間Omeet求解交點(diǎn)對(duì)于時(shí)間棱線段L的有效性.若相交，則將時(shí)空宗地的空間邊界正射投影于時(shí)間切面并輸出結(jié)果.

圖8 基于meet計(jì)算的三維時(shí)空宗地歷史回溯場(chǎng)景求解Fig.8 The history tracebacking scene resolution of three dimensionalspatio-temporal parcel based on meet computation

2.2 案例驗(yàn)證

以杭州建德市新安江鎮(zhèn)白沙村自20世紀(jì)90年代登記以來的地籍?dāng)?shù)據(jù)為例進(jìn)行算法驗(yàn)證，分別選取1996年1月1日、2002年1月1日、2006年1月1日、2010年1月1日為時(shí)間節(jié)點(diǎn)，構(gòu)建時(shí)間掃描面，與時(shí)空宗地meet求交. 圖 9(a)中展示的是軸構(gòu)建的時(shí)空中三維時(shí)空宗地的形態(tài)，即宗地在時(shí)間維度上展開，圖 9(b)、(c)、(d)展示了時(shí)間切面按一定時(shí)間采樣間隔構(gòu)建掃描面，與時(shí)空宗地進(jìn)行meet計(jì)算的動(dòng)態(tài)過程：圖9(b)為2002年1月1日的時(shí)間切面與時(shí)空宗地meet計(jì)算的結(jié)果，反映了2002年1月1日的宗地現(xiàn)狀；圖9(c)為2006年1月1日的時(shí)間切面與時(shí)空宗地meet計(jì)算的結(jié)果，反映了2006年1月1日的宗地現(xiàn)狀；圖9(d)為2010年1月1日的時(shí)間切面與時(shí)空宗地meet計(jì)算的結(jié)果，反映了2010年1月1日的宗地現(xiàn)狀.圖9(b)、(c)、(d)中，不同顏色的多棱柱分別代表不同類型的土地用途，藍(lán)紫色平面為時(shí)間掃描面，突出顯示的紅色多邊形為時(shí)間掃描面和時(shí)空宗地meet求交的結(jié)果.相應(yīng)地，圖10中的(a)、(b)、(c)、(d)分別為在ArcGIS平臺(tái)上進(jìn)行渲染的1996年1月1日、2002年1月1日、2006年1月1日、2010年1月1日的實(shí)際宗地確權(quán)狀況.

將求交結(jié)果與現(xiàn)實(shí)登記中宗地確權(quán)結(jié)果相比較，即圖9與圖10的比較.結(jié)果顯示，基于時(shí)空宗地meet算子計(jì)算的歷史節(jié)點(diǎn)上的宗地確權(quán)結(jié)果與實(shí)際宗地確權(quán)結(jié)果吻合，說明基于幾何代數(shù)理論構(gòu)建的時(shí)空宗地meet計(jì)算流程,能夠較好地應(yīng)用于宗地時(shí)空拓?fù)涞挠?jì)算.

本文通過案例驗(yàn)證了基于幾何代數(shù)的三維時(shí)空宗地表達(dá)和meet計(jì)算的可行性，同時(shí)，為四維時(shí)空宗地的幾何代數(shù)表達(dá)和拓?fù)溆?jì)算提供了時(shí)空宗地表達(dá)模型以及拓?fù)鋗eet算子構(gòu)建的理論基礎(chǔ)和研究思路.

圖9 基于時(shí)空宗地meet算子的時(shí)間掃描面與時(shí)空宗地求交Fig.9 The meet computation between time sweep planeand spatio-temporal parcel based on meet operator

圖10 實(shí)際宗地確權(quán)結(jié)果Fig.10 The parcel registration results

3 結(jié)論與展望

處于地理世界中的物體具有很強(qiáng)的時(shí)空依賴性和動(dòng)態(tài)性，時(shí)空作為物體的固有屬性，對(duì)其變化過程的研究具有重要意義.目前，對(duì)于時(shí)空變化過程的研究多基于關(guān)系數(shù)據(jù)庫(kù)檢索，此方法受限于數(shù)據(jù)庫(kù)的表達(dá)和檢索的水平.本文在現(xiàn)有時(shí)空宗地?cái)?shù)據(jù)模型研究的基礎(chǔ)上，對(duì)幾何代數(shù)的時(shí)空表達(dá)、交并計(jì)算、有向半空間劃分等內(nèi)容展開了研究，利用幾何代數(shù)多維統(tǒng)一、高維計(jì)算適應(yīng)的優(yōu)勢(shì)，設(shè)計(jì)了基于幾何代數(shù)meet算子和有向半空間劃分理論的時(shí)空宗地meet算法.并探討了時(shí)空宗地變化過程中的2種meet場(chǎng)景，針對(duì)時(shí)空宗地meet場(chǎng)景涉及的時(shí)空宗地最小外包球、時(shí)空宗地空間邊界多邊形、時(shí)空宗地時(shí)間棱的meet求解展開了具體的討論，最后從三維時(shí)空宗地歷史回溯角度出發(fā)，設(shè)計(jì)了三維時(shí)空歷史回溯的meet算法.實(shí)驗(yàn)證明，該meet算法能在脫離傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)查找的模式下，較好地滿足歷史回溯和時(shí)空變化過程可視化展示的需求，相比于傳統(tǒng)方法，不受限于關(guān)系數(shù)據(jù)庫(kù)的表達(dá)和檢索能力，更加靈活，且易擴(kuò)展.該算法的理念同樣適用于四維時(shí)空宗地的歷史回溯meet求解.據(jù)此，后續(xù)的重點(diǎn)工作主要為:對(duì)四維時(shí)空宗地的幾何結(jié)構(gòu)組成要素(多面體)的meet計(jì)算進(jìn)行擴(kuò)展，對(duì)時(shí)空超平面等四維時(shí)空基本元素的特性進(jìn)行理解和表達(dá)，對(duì)三維、四維時(shí)空宗地同時(shí)存在的多維混合時(shí)空meet進(jìn)行擴(kuò)展.

[1] 李洪波.共形幾何代數(shù)——幾何代數(shù)的新理論和計(jì)算框架[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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] 羅文,袁林旺,俞肇元,等.基于共形幾何代數(shù)的三維地理場(chǎng)景建模與表達(dá)[J].測(cè)繪通報(bào),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] 宗真,袁林旺,羅文,等.三角網(wǎng)求交的共形幾何代數(shù)算法[J].測(cè)繪學(xué)報(bào),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].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版,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] 俞肇元,袁林旺,胡勇,等.基于幾何代數(shù)的矢量時(shí)空數(shù)據(jù)表達(dá)與建模方法[J].地球信息科學(xué)學(xué)報(bào),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] 李武明,張雪峰.時(shí)空平面的Clifford代數(shù)與Abel復(fù)數(shù)系統(tǒng)[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版,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] 李武明.時(shí)空代數(shù)的若干性質(zhì)及應(yīng)用[J].通化師范學(xué)院學(xué)報(bào),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] 張玲玲,史云飛,郭仁忠,等.三維地籍產(chǎn)權(quán)體的定義與表達(dá)[J].地球信息科學(xué)學(xué)報(bào),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] 袁林旺.基于幾何代數(shù)的多維統(tǒng)一GIS[M].北京：科學(xué)出版社,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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(41471313,41101356,41101371,41171321)；國(guó)家科技基礎(chǔ)性工作專項(xiàng)(2012FY112300)；海洋公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)資助(2015418003,201305012)；浙江省攻關(guān)項(xiàng)目(2014C33G20,2013C33051).

王巧燕(1991-)，ORCID:http://orcid.org/0000-0002-5636-8184,女，碩士研究生，主要從事時(shí)空數(shù)據(jù)建模研究，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