幾何代數GIS計算引擎的設計與實現

胡 勇，孫 惠，羅 文，袁 林 旺

(1.南京師范大學計算機科學與技術學院，江蘇 南京 210023；2.南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210023)

?

幾何代數GIS計算引擎的設計與實現

胡 勇1,2，孫 惠2，羅 文2，袁 林 旺2

(1.南京師范大學計算機科學與技術學院，江蘇 南京 210023；2.南京師范大學虛擬地理環境教育部重點實驗室，江蘇 南京 210023)

分析型GIS的發展對GIS開發模式的統一性和算法的通用性提出了新的要求。基于幾何代數(GA)的GIS多維統一計算模型(GA-MUC)為進行復雜GIS空間分析提供了解決思路。該文提出了基于GA的多維統一GIS計算引擎(GA-MUCE)，探討了基于GA的屬性空間、網絡空間與場空間中基本對象與算子的表達，并將其用于GIS算法的構建。該引擎具有自適應性特征，可根據具體的應用需求定義計算空間，進而設計相應的對象表達與算子、算法庫，最終構建插件形式的GIS分析求解模板。該研究是對復雜GIS空間分析問題求解模式的探索，有利于促進新一代分析型GIS的發展。

幾何代數(GA)；GA-MUC；計算引擎；計算插件

0 引言

隨著物聯網及大數據時代的到來，海量、動態、非結構化的多源空間數據的分析已成為當今及未來GIS發展的核心[1]，迫切需要發展以空間多要素分析與服務為核心，可有效支撐海量數據分析與過程模擬的“分析型GIS”。相對于傳統的以數據為核心的“管理型GIS”，“分析型GIS”要求能應對不同來源、不同類型、海量地理時空數據的整合分析，并要求在分析算法層面上支撐大規模、多維數據的高效計算。但現有GIS空間數據的計算規則與分析方法相對滯后，在多維對象的自適應表達、空間數據的統一分析及多維統一分析框架的構建方面仍顯不足,亟須發展一套相對通用的GIS算法模板以及統一的系統開發模式,使得海量數據資源得到有效利用。

幾何代數(GA)是一種結合代數，實現了不同代數系統的有效統一與集成[2]，從而為包含不同地理要素表達和各類GIS數據互操作的計算空間的構建提供了可能。多重向量結構對混合維度幾何對象與語義結構的統一組織與表達，為相關空間數據的組織、存儲與運算提供了原生的數學與數據結構[3]；幾何代數算子的統一性也可實現不依賴于坐標的幾何關系計算[4]，從而為包含空間、語義等多要素的GIS對象的自適應表達、動態更新與關系計算提供了有利支撐。袁林旺等提出了基于幾何代數的GIS多維統一計算模型(GA-MUC)[5]，并在三維GIS空間數據建模[6]、多維統一GIS計算[7]和場數據特征分析[5]等領域得到應用。以上研究為基于幾何代數的GIS計算提供了理論上的推導與應用驗證。本文基于GA-MUC框架，利用幾何代數空間中的基本表達與算子構建直接面向GIS計算的對象表達與運算，設計了基于幾何代數的屬性空間、網絡空間與場空間的表達，并對上述空間中對象表達與計算算子的生成規則進行探討，進而構建了基于幾何代數的多維統一計算引擎(GA-MUCE)，并給出具體的系統實現流程和案例示范。

1 理論基礎與GA-MUCE設計框架

1.1 幾何代數多重向量表達與算子運算

在幾何代數系統中，幾何積的不可逆性是其可用于幾何問題求解的基礎[4]。同時利用幾何積還可構建其它更為復雜的幾何關系運算，此類運算被稱為GA算子。對于給定多重向量MA和MB，可定義二者間的運算“°”為：

(1)

1.2GA-MUCE設計層次框架

構建基于幾何代數的多維統一GIS計算引擎(GA-MUCE)三層架構如圖1所示：1)空間構建層，主要實現GA空間定義。由于不同的GA模型其表達能力與運算能力不盡相同，同時考慮到空間的維度也會對后續算子構建的復雜度和運算效率產生影響，GA空間的定義通常根據GIS數據和具體GIS分析需求制定。2)對象表達層，主要實現GIS數據到GA空間的嵌入，為常用的多維矢量數據、網絡數據與場數據分別制定表達結構和轉換方法。在表達中不僅需要解決對象幾何與幾何結構的嵌入，還需要考慮到地理屬性與語義關系的表達。3)算子生成層，該層主要利用GA空間中基本的算子、算法，結合GIS空間運算算法，構建復合的GIS空間計算算子，并利用多重向量的計算規則將其向網絡空間和高維場空間擴展，實現GIS空間計算算子集的構建。

圖1 計算引擎層次結構

Fig.1FrameworkofGA-MUCE

2 GA-MUCE構建方法

2.1 基于GA的GIS空間表達

幾何代數空間的可定義性是其可用于不同GIS問題求解的重要前提。幾何代數空間的定義主要分為基向量的定義和度量特征定義兩個步驟。基向量的個數反映了對象維度，度量特征多是由基向量間的內積矩陣確定。據內積運算特點，可進一步將其簡化為在i=j和i≠j兩種情況下，對ei·ej的限定[4]。度量特征可用于幾何代數運算規則及運算特性的定義。例如，在歐氏空間中內積表示兩向量之間的模與其角度的乘積，而共形空間中內積表示兩點之間距離平方的相反數。

圖2 不同度量空間示例

Fig.2Samplesofdifferentmetricspaces

根據上述空間定義規則，定義可支持各類GIS數據計算的幾何代數空間，如表1所示。

2.2 基于GA的GIS對象表達

表1 常用GIS空間的GA表達

Table1TheGArepresentationsofthecommonGISspaces

GIS空間GA空間基向量度量定義幾何空間屬性空間網絡空間場空間歐氏空間e1，e2，…，ene2i=1，ei·ej=0齊次空間e0，e1，…，ene2i=1，ei·ej=0共形空間e0，…，en，e∞e0·e0=e∞·e∞=0，e0·e∞=-1n維屬性空間ea1，ea2，…，eaneai·eaj=0e2ai=1 ai為數值型e2ai=0 ai為字符，枚舉型{n維網絡空間ev1，ev2，…，evnevi∧evj=evivj 連通evi∧evj=0 不連通{n維張量空間e1+e2…+enA B=[aib1ei1，…，aibjeij]

在幾何代數空間中主要有blades和多重向量兩種表達方式，blades多用于表達單一維度對象，而多重向量則可實現混合維度對象的表達，可用于構建復雜的幾何體，或者實現包含語義、拓撲等信息的多維復合表達。

在幾何表達空間中基本對象主要包括點、線、面、球等理想的幾何對象，由于GIS空間中對象均具有明確的邊界信息，并且多為復合結構，需要利用多重向量組合不同維度的blades；在網絡空間中表達連通性的節點、邊、路徑均可通過blades進行表達，其中當grade為1時表示節點，grade為2時表示網絡的一條邊，grade大于2時表示路徑；場空間中的基本對象是向量的表達，在其各自的嵌入空間中均為blade，但在整個張量空間中可表達為多重向量，并可通過多重向量在特定子空間的投影得到具有明確地理語義特征的blade結構，為復雜的地理分析提供支撐。基于GA的GIS對象表達示例見表2。

表2 基于GA的GIS對象表達示例

Table 2 The GA-based representation of GIS objects

GIS對象GA空間表達式線段n+2維共形空間L=A1∧A2射線n+2維共形空間R=A+ v三角形n+2維共形空間T=F+L1+L2+L3四面體n+2維共形空間Te=S+T1+T2+T3網絡節點n維網絡空間N=wvievi，w為權重網絡邊n維網絡空間E=wvivjevivj，w為權重含m個節點的路徑n維網絡空間P=wvx1，vx2，…，vxmevx1，vx2，…，vxm，w為網絡權重場向量n維張量空間V=a1e1+a2e2，…，+anen

注：A、F、S分別表示點、平面、球的共形幾何代數表達。

2.3 基于GA的GIS計算算子

GA算子所具有的對象無關特征及可重構性是GIS空間計算算法構建的基礎，其特征內蘊的性質為包含多信息要素的對象空間關系分析與求解提供了依據，可在幾何代數基礎算子的基礎上構建面向幾何、關系、網絡及場數據的求解算子(表3)。其中幾何度量包括對象間距離求解及對象自身模(體積、面積)的計算。基于上述幾何代數運算空間的定義，可以將上述度量指標分別映射到幾何代數空間中的內積和外積運算；幾何關系判斷包括同維度對象及不同維度對象的判斷，其中同維度對象可通過meet算子進行判斷，不同維度對象需要先將低維對象投影至高維對象并判斷其同低維對象間外積的符號，當其符號一致時表示在內部，不一致則在外部[9]；網絡空間中的網絡延拓算子由外積構造，并嵌入了網絡連通性的判斷[10]；場空間主要通過構建梯度算子實現場特征參數的統一計算[11]。

表3 GA空間GIS計算算子

Table3TheGA-basedoperatorsofGIScomputation

分類算子表達式幾何度量關系判斷網絡空間算子場空間算子距離量算D(A1，A2)=κA1·A2模量算S( u， v)=τ u∧ v同維度對象QA1-A2=(meet(A1，A2)2>0)不同維度對象(點/三角形)QA-T=(sign(aiaj→∧aia→)≥0)網絡延拓算子mei∧nej=(m?n)eij，m、n為網絡權重場梯度算子grad(a)= Δalimτ→0f(x+εa)-f(x)ε

在歐氏幾何框架下，對象間距離、角度等空間關系的計算在不同維度對象上不統一，不同類型對象間的運算也需要分別處理，從而使得傳統算法適用性不強，不利于設計面向動態場景和大規模數據的統一求解框架。GA框架下的幾何對象表達與計算對幾何度量關系具有內蘊性與繼承性，基于幾何代數的度量與關系表達更為簡潔且便于運算，同時利用GA算子對網絡空間和場空間的統一求解也有利于設計融合多種地理要素的復雜問題的算法。

3 GA-MUCE系統實現

3.1 系統實現流程

基于GA-MUCE的GIS實現主要包含GA-MUCE構建模塊和GIS問題求解模塊兩部分(圖3)，主要實現GIS數據的嵌入表達、GIS算法的幾何代數改造以及分析結果的投影與輸出等功能。

圖3 GA-MUCE實現流程

Fig.3 Implementation procedure of GA-MUCE

GA-MUCE構建模塊主要包含基于幾何代數GIS空間的構建、GIS對象的表達及GIS算子的設計三部分。它是GIS數據嵌入GA空間以及后續GIS空間問題求解的基礎，主要通過建立GIS計算空間中的對象表達和運算，并利用GA計算軟件庫實現相關算法。目前已有一系列較為成熟的幾何代數計算庫，包括CLUCalc[12]、Gaigen[13]、Gaalop[14]和Gaalet[15]等。但上述算法庫大多面向幾何計算，缺少面向具體GIS數據的實現。考慮面向大規模GIS計算的效率優化需求，選用較為高效的Gaigen 2.5作為本計算引擎中計算空間構建模塊的核心計算庫，實現基于Gaigen的計算空間向GIS計算空間的映射。

GIS問題的求解模塊實現了GIS問題的幾何代數形式化表達與求解。幾何代數形式化表達需要在對現有算法充分解析的前提下，提煉出相應的幾何代數求解模式，并將其轉換為可直接用于算子求解的代數表達。在模式提煉過程中需要充分考慮幾何代數表達與運算的統一性與求解過程的優化，可利用Gaalop等GA表達式化簡庫對上述形式化表達加以優化從而得出最高效的幾何代數算法。最后求得計算結果并將其反向投影回GIS空間。

綜上所述，構建GA-MUCE的實現步驟如下：1)設定空間維度與基向量，定義基向量間的內積矩陣，構建度量空間；2)根據給定分析數據的組織方式，結合幾何代數空間定義，構建歐氏空間向幾何代數空間的嵌入方法和幾何代數空間對象向歐氏空間投影方法；3)選取所要使用的GA算子與算法，結合GIS空間基本對象的空間度量與求解方法，設計基于幾何代數的GIS空間計算算子；4)分析需要求解的空間計算問題，對其傳統求解方法加以解析，并對其進行幾何代數構造，得到空間問題求解的幾何代數形式化表達；5)優化算法流程，求得最終結果。

3.2 GA空間與算子庫構建

幾何代數是通過將低維度數據嵌入到高維數據從而獲得更高自由度的對象表達、運動表達與算子求解。但隨著空間維度的增加，在空間計算中所要處理的blade項迅速增多，導致算法復雜度增大，因而需要選取恰當的空間維度；同時考慮到不同幾何代數模型的度量特征不同，其所能構建的算子也不盡相同，在幾何代數空間的構建過程中要根據具體的分析需求定義不同的幾何代數空間模型，并選用合適的計算算子。為了保證幾何代數空間定義的靈活性，可通過配置文件構建計算空間。首先設計幾何代數空間構建所需要的空間基本信息、空間基向量以及空間度量設置，進而列出在算法中應用到的所有算子(圖4a)。利用上述配置文件結合Gaigen生成可執行的C++代碼。

由于GIS對象多包含邊界、紋理等語義信息，需要將幾何代數空間中由子空間所表達的基礎對象擴展為可用于GIS空間運算的幾何對象，該過程可通過組合GA基本對象實現。圖4b示例了GIS空間中點對象和射線對象的表達。不同于基礎GA對象，點對象在包含點坐標的同時，還要給出其切平面(用于計算法向量)和紋理坐標(紋理渲染與可視化)；而射線對象和三角形對象即是在FreeVector對象和Plane對象的基礎上分別添加了端點約束和邊界約束。圖4b列舉了對基于GA基本算子的GIS計算算子的擴展方法。對于射線，其基于端點的反射算子可進一步解析為：在保留原始射線端點的前提下，對其方向向量應用GA反射算子，同理可推導出三角形rotor變換算子。

3.3 算法插件的設計與系統嵌入

算法構建層的主要工作是實現傳統GIS算法的幾何代數形式化表達并對GA表達的流程進行簡化，最后求得運算結果。基于GA表達與算子的統一性，可設計相對通用的GIS表達與計算框架。在此框架下的GIS問題的形式化求解流程具有統一性，因而可設計基于GA-MUCE的算法模板，并通過插件方式嵌入到系統中。首先設計算法模板(圖4c)，同時在系統API中設置相應的插件接口類，實現對所綁定模板參數的輸入、輸出，同時設計對模板空間轉換函數及算法實現函數的事件調用，最終實現空間計算算法的插件形式嵌入與求解。

3.4 系統開發與實現

利用上述特性，設計了插件模式的GIS：基于幾何代數的多維空間計算系統(圖4d)，實現了基本GIS空間數據的管理，利用幾何代數計算引擎對GIS空間計算提供算子與算法支撐，并通過插件的思路構建特定的GIS分析功能。

系統窗體與控件利用WxWidget庫實現，利用OpenGL和VTK分別實現多維矢量數據渲染及多維時空場數據的可視化；在應用程序接口中主要實現了三種基本數據的管理與運算，并提供了GIS空間求解模型接口，實現插件形式的GIS空間計算模塊的集成。

4 結論

Fig.4 System implementation of GA-MUCE

本文介紹了基于幾何代數的GIS計算引擎(GA-MUCE)設計與程序實現，提出了基于GA的GIS計算空間構建、GIS對象表達和GIS算子構建的計算引擎三層架構。在對多維矢量數據、網絡數據與高維場數據的表達與運算特征梳理的基礎上，構建了基于幾何代數的幾何空間、屬性空間、網絡空間與場空間表達與運算。最后提出了基于配置文件的幾何代數空間定義方法和基于封裝的GIS對象與算子構建方法，并基于幾何代數算法的靈活性與統一性，在對現有計算流程分析的基礎上，設計了插件嵌入的算法集成機制。利用配置文件可定義出合適的幾何代數空間，GIS空間計算算法則可通過插件的形式嵌入與擴展，表明本文構建的計算引擎具有較好的可定制性和可擴展性。

[1] GOODCHILD M F.Citizens as sensors:The world of volunteered geography[J].GeoJournal,2007,69(4):211-221.

[2] HESTENES D,SOBCYK G.Clifford Algebra to Geometric Calculus[M].Heidelberg:Springer-Verlag,1984.

[3] PERWASS C.Geometric Algebra with Applications in Engineering[M].Berlin,Heidelberg:Springer-Verlag,2009.

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

[5] YUAN L W,YU Z Y,LUO W,et al.Geometric algebra for multidimension-unified geographical information system[J].Advances in Applied Clifford Algebras,2013,23(2):497-518.

[6] 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.

[7] YUAN L W,LV G,LUO W,et al.Geometric algebra method for multidimensionally-unified GIS computation[J].Chinese Science Bulletin,2012,57(7):802-811.

[8] AERTS D,MAREK C.Tensor-product versus geometric-product coding[J].Physical Review A,2008,77(1):012316.

[9] 宗真,袁林旺,羅文,等.三角網求交的共形幾何代數算法[J].測繪學報,2014,43(2):200-207.

[10] 俞肇元,胡勇,朱曉林,等.基于幾何代數的多類型約束路網最優路徑分析算法[J].地理與地理信息科學,2014,30(2):10-15.

[11] 羅文,袁林旺,俞肇元,等.多維向量場特征參數的幾何代數統一計算方法[J].系統工程理論實踐,2013,33(9):2390-2396.

[12] PERWASS C.CLUCalc 2014.Available:http://www.clucalc.info/.2013-12-30.

[13] FONTIJNE D.Gaigen 2.5:Geometric Algebra Implementation Generator[R].2010.1-112.

[14] HILDENBRAND D.Foundations of Geometric Algebra Computing[M].New York:Springer,2013.

[15] SEYBOLD F,UWE W.Gaalet-a C++ expression template library for implementing geometric algebra[C].6th High-End Visualization Workshop.Austria:Obergurgl,2010.1-10.

Design and Realization of GA Based Multi-dimensional Integrated GIS Computing Engine

HU Yong1,2,SUN Hui2,LUO Wen2,YUAN Lin-wang2

(1.DepartmentofComputerScienceandTechnology,NanjingNormalUniversity,Nanjing210023；2.KeyLaboratoryofVGE,MinistryofEducation,NanjingNormalUniversity,Nanjing210023,China)

The development of analysis-oriented GIS requires GIS systems make much more progress to follow certain templates and GIS algorithms to deal with different types of geographic data and data in different dimensions.GA based multi-dimensional unified computation model (GA-MUC) provides a solution for complicated GIS spatial analysis.In this paper,the GA based multi-dimensional unified computing engine (GA-MUCE) is designed,and the expressions of basic objects and operators in GA-based attribute space,network space and field space are discussed respectively.Then these methods are applied to the construction of GIS algorithms.The engine is able to meet different application meets.It can be used to define the computing space,design operator and algorithm libraries,express specific GIS objects,and finally construct the GIS analyzing templates in the form of plugin.Researches have been done to explore solutions for complex GIS spatial analysis in the paper,which will help to promote the development of new generation of analysis-oriented GIS.

geometric algebra (GA)；GA-MUC；computing engine；computing plugin

2014-08-28；

2014-10-23

江蘇省高校自然科學研究項目“多維統一的幾何代數并行空間索引研究”(13KJB170006)；江蘇省自然科學基金青年基金項目“復雜場景中空間關系動態計算的幾何代數方法”(BK2012454)；國家科技支撐計劃課題“視頻GIS與突發公共事件的感知控制系統”(2012BAH35B02)

胡勇(1973-)，男，碩士，講師，主要從事計算機算法設計與GIS應用研究。E-mail:huyong@njnu.edu.cn

10.3969/j.issn.1672-0504.2015.01.006

P208;TP301.6

A

1672-0504(2015)01-0027-05