易 琳，袁 林 旺，俞 肇 元，羅 文，閭 國(guó) 年

Voronoi生成的Clifford代數(shù)實(shí)現(xiàn)方法

易 琳，袁 林 旺＊，俞 肇 元，羅 文，閭 國(guó) 年

（南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046）

引入具有維度融合、坐標(biāo)無(wú)關(guān)等特性的Clifford幾何代數(shù)，構(gòu)建不同維度統(tǒng)一Voronoi生成框架及算法流程。定義了可支撐不同維度、不同對(duì)象間距離、相交及對(duì)偶關(guān)系的幾何、拓?fù)溥\(yùn)算，基于多重向量設(shè)計(jì)了可支撐不同維度地理對(duì)象的統(tǒng)一存儲(chǔ)結(jié)構(gòu)及關(guān)系表達(dá)機(jī)制，實(shí)現(xiàn)了基于Clifford代數(shù)的多維統(tǒng)一Voronoi生成算法。以中國(guó)城市氣象數(shù)據(jù)為例進(jìn)行了算法驗(yàn)證，并分析了算法復(fù)雜度。結(jié)果表明，該算法可根據(jù)輸入數(shù)據(jù)維度自適應(yīng)地實(shí)現(xiàn)相應(yīng)維度的Voronoi分析，可為以維度統(tǒng)一為特征的GIS分析算法實(shí)現(xiàn)提供借鑒。

Clifford代數(shù);維度統(tǒng)一;Voronoi算法

Voronoi算法是GIS最具代表性的空間分析方法之一［1－3］，Voronoi圖的構(gòu)建同時(shí)涉及點(diǎn)、線(xiàn)、面等多種幾何對(duì)象間度量、拓?fù)潢P(guān)系的表達(dá)與計(jì)算［4］，多維Voronoi分析也得到較多關(guān)注［5－8］。但GIS中常用的Voronoi算法對(duì)二維空間數(shù)據(jù)結(jié)構(gòu)依賴(lài)較強(qiáng)，高維擴(kuò)展相對(duì)困難;而由計(jì)算幾何等領(lǐng)域發(fā)展的高維Voronoi算法［9，10］缺乏與GIS空間數(shù)據(jù)的有效連接機(jī)制。Clifford代數(shù)以維度運(yùn)算作為幾何運(yùn)算基礎(chǔ)，運(yùn)算具有坐標(biāo)無(wú)關(guān)性，并能對(duì)不同代數(shù)系統(tǒng)進(jìn)行有機(jī)集成［11，12］，被廣泛應(yīng)用于相對(duì)論物理學(xué)、計(jì)算機(jī)視覺(jué)和機(jī)器人學(xué)等領(lǐng)域［13－16］。謝維信等基于Clifford代數(shù)研究了二維Delaunay剖分和Voronoi圖構(gòu)建［17］。Dorst等給出了基于共形幾何代數(shù)的多維統(tǒng)一Voronoi圖的理論框架和理論推導(dǎo)［18］，并進(jìn)行了二維實(shí)現(xiàn);Zonnenberg實(shí)現(xiàn)了多維Voronoi圖生成程序庫(kù)CGAP［19］，受存儲(chǔ)結(jié)構(gòu)、計(jì)算引擎及不同數(shù)據(jù)類(lèi)型頻繁轉(zhuǎn)換等制約，在算法結(jié)構(gòu)、效率與運(yùn)算穩(wěn)定性等方面有待提高，且缺乏與GIS空間數(shù)據(jù)的有效連接。本文研究了不同維度Voronoi的Clifford代數(shù)表達(dá)及其幾何特性，構(gòu)建了適用于GIS的Voronoi生成算法。

1 基于Clifford代數(shù)的Voronoi算法構(gòu)建

1.1 Clifford代數(shù)及Clifford代數(shù)空間

Clifford代數(shù)是一種結(jié)合代數(shù)，運(yùn)算規(guī)則實(shí)現(xiàn)了標(biāo)量運(yùn)算與矢量運(yùn)算、維度運(yùn)算和幾何運(yùn)算的統(tǒng)一。典型的Clifford代數(shù)空間Cl（p，q）可通過(guò)式（1）定義：

通過(guò)選取并定義不同單位向量間Clifford積的符號(hào)，可實(shí)現(xiàn)不同維度幾何、代數(shù)空間定義，并保證不同空間中運(yùn)算的坐標(biāo)無(wú)關(guān)性。與復(fù)數(shù)類(lèi)似，式（1）中“＋”的幾何意義僅用于表達(dá)連接而非數(shù)值運(yùn)算，“＋”可以連接不同維度的表達(dá)式，構(gòu)成稱(chēng)為多重向量（MultiVector）的多維度共存的數(shù)學(xué)結(jié)構(gòu)，該結(jié)構(gòu)是Clifford代數(shù)中基本的數(shù)學(xué)結(jié)構(gòu)之一。

在歐氏、齊次和共形這3類(lèi)最常用的Clifford代數(shù)空間中，齊次空間通過(guò)增加一固定的投影維，將三維歐氏空間Cl（3，0）嵌入高維射影空間，實(shí)現(xiàn)了代數(shù)空間的Grassmann分級(jí)結(jié)構(gòu)與幾何形體分級(jí)結(jié)構(gòu)的統(tǒng)一;而共形空間Cl（4，1）則在齊次空間基礎(chǔ)上增加無(wú)窮遠(yuǎn)點(diǎn)，在保留齊次空間外積的Grassmann分級(jí)結(jié)構(gòu)的同時(shí)，使得內(nèi)積具備了表征距離、角度等基本度量的明確幾何意義［14］。在齊次和共形空間中的新增維度僅用于輔助計(jì)算，而不影響所嵌入歐氏空間的幾何特性及運(yùn)算規(guī)則。Clifford代數(shù)在不同空間中的表達(dá)與相互轉(zhuǎn)換，使幾何計(jì)算過(guò)程具有內(nèi)蘊(yùn)性和直觀性，在有效支撐和簡(jiǎn)化高維計(jì)算的同時(shí)，也為歐氏幾何、雙曲幾何、射影幾何、微分幾何等提供統(tǒng)一和簡(jiǎn)潔的齊性代數(shù)框架。

1.2 基于Clifford代數(shù)的Voronoi算法設(shè)計(jì)

Voronoi的數(shù)學(xué)定義與其發(fā)生點(diǎn)集的維度無(wú)關(guān)，具備了發(fā)展多維統(tǒng)一算法的數(shù)學(xué)基礎(chǔ)。提升法是求解高維Delaunay和Voronoi常用方法之一，通過(guò)將d維空間的點(diǎn)集提升至d＋1維，可將d維的Delaunay求解轉(zhuǎn)化為d＋1維的凸包求解，結(jié)合Delaunay與Voronoi的對(duì)偶關(guān)系獲得d維空間點(diǎn)集的Delaunay和 Voronoi（圖1a）［20］。歐氏幾何與計(jì)算幾何缺乏多維統(tǒng)一的對(duì)象表達(dá)與空間關(guān)系計(jì)算方法，基于Clifford代數(shù)的維度運(yùn)算及其坐標(biāo)無(wú)關(guān)性，可實(shí)現(xiàn)基本幾何對(duì)象維度與坐標(biāo)無(wú)關(guān)的自適應(yīng)表達(dá)（圖1b），并可定義相應(yīng)的幾何與拓?fù)潢P(guān)系運(yùn)算算子（圖1c）［21］，從而統(tǒng)一并簡(jiǎn)化不同維度幾何對(duì)象的表達(dá)與運(yùn)算?；贑lifford代數(shù)的不同維度統(tǒng)一Voronoi算法流程如圖1d所示。利用共形變換實(shí)現(xiàn)歐氏空間向共形空間轉(zhuǎn)換與維度提升，基于凸包與Delaunay在維度上的對(duì)應(yīng)關(guān)系，在共形空間求解d＋1維凸包后映射回歐氏空間即得Delaunay圖。而Voronoi圖的求解則通過(guò)將共形空間中點(diǎn)集的超切平面圍成的包絡(luò)結(jié)果反向投影回歐氏空間實(shí)現(xiàn)。

圖1 Voronoi圖、對(duì)象表達(dá)和基本關(guān)系運(yùn)算算子定義及Voronoi-Delaunay算法流程Fig.1 The definition of Voronoi，objects expression and basic operations in Clifford space and the algorithm flow of Voronoi-Delaunay

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 存儲(chǔ)結(jié)構(gòu)與拓?fù)潢P(guān)系維護(hù)

共形空間中不同維度幾何體的層次結(jié)構(gòu)滿(mǎn)足Grassmann分級(jí)結(jié)構(gòu)，d維基本幾何形體可直接通過(guò)d個(gè)任意共形點(diǎn)集的外積構(gòu)建［22］，實(shí)現(xiàn)了維度與坐標(biāo)無(wú)關(guān)的幾何對(duì)象統(tǒng)一表達(dá)與存儲(chǔ)。幾何代數(shù)中多重向量提供了不同維度、不同類(lèi)型幾何對(duì)象表達(dá)、關(guān)聯(lián)及數(shù)學(xué)運(yùn)算結(jié)構(gòu)的統(tǒng)一［23］?；編缀螌?duì)象構(gòu)建及基于多重向量的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)思路見(jiàn)圖2。除點(diǎn)集外，其他幾何形體存儲(chǔ)均可通過(guò)存儲(chǔ)所包含點(diǎn)的ID標(biāo)識(shí)。其中線(xiàn)段只標(biāo)定起點(diǎn)和終點(diǎn)，根據(jù)兩點(diǎn)的外積與e∞外積構(gòu)建線(xiàn)段方程;射線(xiàn)則利用點(diǎn)、方向、e∞外積方程表達(dá)，并采取標(biāo)定起點(diǎn)和發(fā)射方向方式存儲(chǔ)。該存儲(chǔ)結(jié)構(gòu)有效利用了共形空間中不同維度幾何形體在構(gòu)建關(guān)系和表達(dá)形式上的簡(jiǎn)潔性，不僅便于拓?fù)潢P(guān)系維護(hù)，也適用于任意維度幾何對(duì)象存儲(chǔ)。

不同維度統(tǒng)一Voronoi算法的關(guān)鍵在于拓?fù)潢P(guān)系建立，通過(guò)ID建立點(diǎn)與算法生成中各要素間的拓?fù)潢P(guān)系（圖3）。其中，Delaunay按順序組織每個(gè)三角形的頂點(diǎn)ID表達(dá)三角形間鄰接關(guān)系。Voronoi中多邊形（cell）可利用原始數(shù)據(jù)點(diǎn) PID（N1，N2，N3）為主索引，建立其與 hyper＿segements、hyper＿rays的關(guān)聯(lián)，并通過(guò)此ID連接原始數(shù)據(jù)與該點(diǎn)所在cell的鄰接cell及各超線(xiàn)段、超射線(xiàn)。線(xiàn)段與射線(xiàn)通過(guò)SID和RID進(jìn)行標(biāo)定，進(jìn)而實(shí)現(xiàn)其與所屬多邊形對(duì)應(yīng)關(guān)系的建立。該拓?fù)潢P(guān)系結(jié)構(gòu)的優(yōu)勢(shì)在于不僅有效組織Voronoi、Delaunay圖間的連接關(guān)系，而且在CGA空間運(yùn)算中確定了空間提升后地理點(diǎn)集數(shù)據(jù)與所求得的超切面間的拓?fù)潢P(guān)系，在對(duì)超切面相交結(jié)果進(jìn)行解析時(shí)，能保持原數(shù)據(jù)與生成結(jié)果的關(guān)聯(lián)關(guān)系。

2.2 核心算法實(shí)現(xiàn)

Delaunay和Voronoi生成的核心偽碼見(jiàn)圖4。Delaunay生成依賴(lài)共形空間中點(diǎn)集凸包的求解。通過(guò)以任一點(diǎn)作為起點(diǎn)，連接該點(diǎn)最鄰近的兩點(diǎn)依次判斷每3個(gè)數(shù)據(jù)點(diǎn)外積構(gòu)成的面與點(diǎn)的位置關(guān)系，確定最小邊界包絡(luò)。算法核心在于基于對(duì)偶算子進(jìn)行點(diǎn)的超切面求解，以及不同維度幾何對(duì)象的求交。利用對(duì)偶算子Dual（）求得輸入各點(diǎn)的超切面，并將其存儲(chǔ)至hyper Tangent Plane中，調(diào)用intersection（）函數(shù)計(jì)算超切面不同維度組成部分的相交結(jié)果，進(jìn)而將超切面連接形成半閉合超多面體。由于外積運(yùn)算具有反對(duì)稱(chēng)性，所構(gòu)建各面具有不同的方向性，因此需要進(jìn)行包絡(luò)檢測(cè)與修正。基于Check＿upper＿envelop（）方法對(duì)存儲(chǔ)結(jié)果進(jìn)行包絡(luò)檢測(cè)，若為上包絡(luò)，則調(diào)用unlift＿space（）函數(shù)將包絡(luò)相交邊界反向投影，得到Voronoi圖各邊;若經(jīng)檢測(cè)非上包絡(luò)則返回至超切平面求解，進(jìn)而對(duì)包絡(luò)構(gòu)建過(guò)程進(jìn)行修正，直至檢測(cè)為上包絡(luò)。迭代所有頂點(diǎn)輸出Voronoi。

3 實(shí)例驗(yàn)證與算法分析

3.1 不同維度的Voronoi的生成實(shí)驗(yàn)與對(duì)比

本文選取2005年中國(guó)城市氣象觀測(cè)數(shù)據(jù)的經(jīng)度、緯度、高程作為3個(gè)空間維度的試驗(yàn)數(shù)據(jù)（圖5a），數(shù)據(jù)來(lái)源于中國(guó)氣象科學(xué)數(shù)據(jù)共享服務(wù)網(wǎng)（http：//cdc.cma.gov.cn），共計(jì)179個(gè)站點(diǎn)。算法實(shí)現(xiàn)基于VC?9.0，并以插件形式集成于CAUSTA系統(tǒng)中［23］。二維和三維Voronoi圖見(jiàn)圖5b、圖5d。結(jié)果顯示本文構(gòu)建算法可實(shí)現(xiàn)不同維度Voronoi的求解。圖5c為ArcGIS二維Voronoi分析結(jié)果，兩者的微小差距出現(xiàn)在無(wú)窮遠(yuǎn)點(diǎn)的射線(xiàn)上，謝維信等已論證了基于Clifford代數(shù)的Voronoi算法不受邊界限制［17］，其結(jié)果具有更好的準(zhǔn)確性與有效性。不同浮點(diǎn)精度誤差的模擬實(shí)驗(yàn)也顯示本文算法具有較強(qiáng)的穩(wěn)健性。

3.2 算法復(fù)雜度分析

圖5 多維Voronoi算法的實(shí)現(xiàn)及對(duì)比Fig.5 Implementation of 2D and 3D Voronoi algorithm and the results comparison

4 結(jié)論與討論

本文利用Clifford代數(shù)在多維融合、計(jì)算的坐標(biāo)無(wú)關(guān)等優(yōu)勢(shì)，構(gòu)建了面向GIS的多維統(tǒng)一Voronoi算法：修改了傳統(tǒng)提升法的Voronoi生成框架，構(gòu)建了不同維度統(tǒng)一Voronoi算法流程;基于相應(yīng)的幾何、拓?fù)渌阕?，?shí)現(xiàn)了不同維度、不同對(duì)象間距離、相交及對(duì)偶關(guān)系運(yùn)算;利用共形空間中幾何對(duì)象的Grassmann分級(jí)結(jié)構(gòu)，基于多重向量給出了可支撐不同維度地理對(duì)象的統(tǒng)一存儲(chǔ)結(jié)構(gòu)及關(guān)系表達(dá)機(jī)制;設(shè)計(jì)了用于Voronoi求解的核心算法類(lèi)并進(jìn)行算法實(shí)現(xiàn)，進(jìn)而基于全國(guó)城市氣象觀測(cè)數(shù)據(jù)進(jìn)行了二維和三維Voronoi分析。

多維GIS空間分析是GIS發(fā)展的重要方向之一。由于維度擴(kuò)展所導(dǎo)致的復(fù)雜性及多維運(yùn)算的不統(tǒng)一性，要求GIS分析從理論基礎(chǔ)上能夠進(jìn)行多維融合，并能夠支持多維統(tǒng)一表達(dá)與運(yùn)算。本文研究表明基于Clifford代數(shù)構(gòu)建的不同維度統(tǒng)一Voronoi算法，在算法設(shè)計(jì)上實(shí)現(xiàn)了多維度統(tǒng)一，在計(jì)算結(jié)構(gòu)上實(shí)現(xiàn)了與Clifford代數(shù)結(jié)構(gòu)的有效銜接，在計(jì)算流程上也表現(xiàn)出簡(jiǎn)潔直觀性與幾何意義明確性等特征。Clifford代數(shù)可為多維融合GIS空間分析算法構(gòu)建提供全新的理論基礎(chǔ)與數(shù)學(xué)工具。

［1］顏輝武，祝國(guó)瑞，徐智勇.基于動(dòng)態(tài)Voronoi圖的距離倒數(shù)加權(quán)法的改進(jìn)研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（11）：1017－1020.

［2］李佳田，陳軍，趙仁亮，等.基于線(xiàn)性四叉樹(shù)結(jié)構(gòu)的Voronoi圖反向膨脹生成方法［J］.測(cè)繪學(xué)報(bào)，2008，37（2）：236－242.

［3］陳軍，李志林，蔣捷，等.多維動(dòng)態(tài)GIS空間數(shù)據(jù)模型與方法的研究［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2004，29（10）：858－862.

［4］KIM D S，KIM D U，SUGIHARA K.Voronoi diagram of a circle set from Voronoi diagram of a point set：Topology［J］.Computer Aided Geometric Design，2001，18（6）：541－562.

［5］LEE I，GAHEGAN M.Interactive analysis using Voronoi diagrams：Algorithms to support dynamic update from a generic triangle-based data structure［J］.Transections in GIS，2002，6（2）：89－114.

［6］KIM D，KIM D S.Region-expansion for the Voronoi diagram of 3D spheres［J］.Computer-Aided Design，2006，38：417－430.

［7］FORT M，SELLARES J A.Computing generalized higher-order Voronoi diagrams on triangulated surfaces［J］.Applied Mathematics and Computation，2009，215：235－250.

［8］BERCHTOLD S，ERTL B，DANIEL A K.Fast nearest neighbor search in high-dimensional space［A］.Proceedings of 14th International Conference on Data Engineering（ICDE′98）［C］.Orlando，F(xiàn)lorida，1998.23－27.

［9］NILFOROUSHAN Z，MOHADESB A，REZALLI M M，et al.3D hyperbolic Voronoi diagrams［J］.Computer-Aided Design，2010，42：759－767.

［10］DOLBILIN N P.Properties of faces of parallelohedra［J］.Proceedings of the Steklov Institute of Mathematics，2009，266（1）：105－119.

［11］CLIFFORD W K.Applications of Grassmann′s extensive algebra［J］.American Journal of Math，1878，1：350－358.

［12］LI H B，HESTENES D，ROCKWOOD A.Generalized Homogeneous Coordinates for Computational Geometry［M］.Berlin Heidelberg New York：Springer-Verlag，2001.27－59.

［13］HESTENES D，SOBCZYK G.Clifford Algebra to Geometric Calculus：A Unified Language for Mathematics and Physics［M］.Reidel Publishing Company，1984.

［14］李洪波.共形幾何代數(shù)與幾何不變量的代數(shù)運(yùn)算［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（7）：902－911.

［15］HESTENES D.New Foundations for Classical Mechanics［M］.Kluwer Academic Publishers，1999.

［16］PERWASS C.Geometric Algebra with Applications in Engineering［M］.Heidelberg：Springer-Verlag，2009.

［17］XIE W X，CAO W M，MENG S.Coverage analysis for sensor networks based on Clifford algebra［J］.Science in China（Series F：Information Sciences），2008，51（5）：460－475.

［18］DORST L，F(xiàn)ONGJINE L，MANN D.Geometric Algebra for Computer Science：An Object-Oriented Approach to Geometry［M］.San Fransisco：Morgan Kaufmann，Elsevier Science Ltd，2007.

［19］ZONNENBERG C.Conformal Geometric Algebra Package［D］.U-trecht University，2007，INF/SCR－2006－066.

［20］EDELSBRUNNER H，SEIDEL R.Voronoi diagrams and arrangements［J］.Discrete and Computational Geometry，1986，1（1）：25－44.

［21］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.

［22］李洪波.共形幾何代數(shù)與運(yùn)動(dòng)和形狀的刻畫(huà)［J］.計(jì)算機(jī)輔助設(shè)計(jì)和圖形學(xué)學(xué)報(bào)，2006，18（7）：895－901.

［23］YUAN L W，YU Z Y，CHEN S F，et al.CAUSTA：Clifford algebra-based unified spatio-temporal analysis［J］.Transactions in GIS，2010，14（s1）：59－83.

［24］BRADFORD C B，DVID P D，HANNU H.The Quickhull algorithm for convex hulls［J］.ACM Transaction on Mathematical Software，1996，22（4）：469－483.

Clifford Algebra-Based Voronoi Algorithm

YI Lin，YUAN Lin－wang，YU Zhao－yuan，LUO Wen，LV Guo－nian
（KeyLaboratoryofVGE，MinistryofEducation，NanjingNormalUniversity，Nanjing210046，China）

Based on the superiority of Clifford algebra in multi-dimensional diffusion and coordinate freeing，the unified multi-dimensional generation framework and the algorithm flow of Voronoi have been constructed.Geometric operations and topological operations are defined，which can calculate the distance，intersection and dual among different dimensions and different types of geometric objects.And the unified storage structure and expression mechanism for different dimensional objects are designed with multivector.Finally，2D ＆3D experiments and comparison analysis of complexity and accuracy are given to validate the algorithm.The work proves that the designed algorithm is effective and feasible to multi-dimensional Voronoi analysis，and geometric algebra provides a new math tool to establish multi-dimensional unified spatial analysis algorithms.

Clifford algebra;multi-dimensional unified;Voronoi algorithm

P208

A

1672－0504（2011）05－0037－05

2011－05- 04;

2011－06－29

國(guó)家自然科學(xué)基金“基于共形幾何代數(shù)的三維空間數(shù)據(jù)模型研究”（41001224）;國(guó)家863課題“基于Clifford代數(shù)的時(shí)空統(tǒng)一數(shù)據(jù)模型關(guān)鍵技術(shù)研究”（2009AA12Z205）

易琳（1986－），女，碩士，從事GIS開(kāi)發(fā)研究。＊通訊作者E－mail：yuanlinwang＠njnu.edu.cn