基于龐卡萊代數的TEN三維GIS模型研究

馬玉梅，馬 超

(1.新疆維吾爾自治區第二測繪院，新疆 烏魯木齊 830002;2.東北師范大學 地理科學學院，吉林 長春 130024)

基于龐卡萊代數的TEN三維GIS模型研究

馬玉梅1，馬 超2

(1.新疆維吾爾自治區第二測繪院，新疆 烏魯木齊 830002;2.東北師范大學 地理科學學院，吉林 長春 130024)

不規則四面體網具有結構簡單、易于擴展的特性。借助于龐卡萊代數，應用邊界表示理論重新描述了TEN模型。與傳統幾何結構模型相比，這種模型具有表達簡單、易于計算的特點。同時，提出基于龐卡萊代數的TEN合并和刪除運算以及拓撲一致性檢查。在VC++環境下，對TEN模型的合并和刪除運算進行編程與實現。實驗表明，基于龐卡萊代數的TEN模型可以有效建立動態實體模型，能夠實時建立拓撲關系，適合于表達不規則礦體等動態變化的三維實體。

龐卡萊代數；三維地理信息系統；不規則四面體格網；拓撲一致性；邊界表達法

當前的GIS三維模型多是依賴現有的三維軟件進行建模[1-2]，這種方法雖然快速有效，但在導入三維GIS軟件中進行空間分析會受到一定程度限制，原因是對模型的數據結構一無所知，導致三維模型只能進行可視化表達，無法進行自定義分析。因此，這種模型并非真正意義上的三維模型，真正的GIS三維模型必須是從底層開發的模型。由于模型應用目的不同，各國學者也提出相應的三維模型，例如，我國學者吳立新提出的面模型、體模型和混合模型[3]；Abdul-Rahman提出的三維陣列模型、八叉樹模型、構造性實體幾何模型和三維TIN模型[4]；此外，還有WANG YANBING提出的地理模型、地質模型、集成模型[5]。無論三維模型如何分類，都不可能完美解決地學GIS中的所有問題，因此試圖建立一種萬能模型是不可行的，模型應該是與應用要求相匹配。雖然不規則四面體網(irregular tetrahedral network，TEN)已被廣泛建模，其拓撲結構也被多次表達[6]，但建模沒有統一的定論，建立的模型缺乏動態編輯，一致性檢驗缺乏，因此，本文基于龐卡萊代數(Poincaré algebra)提出了三維GIS中的TEN的建模方法及其拓撲一致性檢查要求，并實現了TEN的合并、刪除運算及DBMS連接。

1 龐卡萊TEN模型

1.1 拓撲結構

1.2 邊界表示

如式(1)所示，TEN可用向量形式描述各個維度單純形，0維單純形表示為S0=，一維單純形表示為S1=，二維單純形表示為S2=，三維向量表示為S3=，并依次推廣到n維單純形情況。向量的方向性決定了Sn表示的是頂點集{v0,…,vn}中頂點的排列，當n為0,1,2,3維時分別表示1,2,6,24種情況，例如，當n=2時，S2分別為，，，，，，若，，標記“+”，則，,相應地標記為“-”，并且有=-，=-，=-。在二維條件下，正負號可以判斷某面的法向量，從而區分模型的內外性，三維條件下的推理類似二維情況。

(1)

根據龐卡萊對邊界的定義[8]，TEN的邊界可用代數和形式進行描述，如果n維單純形Sn的邊界用?Sn表示，那么?Sn的表達為

(2)

2 龐卡萊TEN運算

基于龐卡萊代數的3D TEN明顯特點是TEN可以實時動態更新，空間實體由有限個TEN組成，在某些TEN發生諸如合并、刪除變化后，龐卡萊代數運算可以重建每次變化的拓撲關系，這與以往單純的基于幾何的TEN模型是完全不同的?；邶嬁ㄈR代數的TEN拓撲檢查伴隨著實體的存在而存在，這種檢查體現了構成實體的各個TEN與實體的拓撲統一。

2.1 TEN合并與刪除

正如前述，TEN實體動態變化主要是合并和刪除，式(2)描述了龐卡萊代數的and運算和subtraction(合并與刪除計算)，合并的實質是去除公共邊或公共面的問題，三維計算結果為n胞元復合體。圖1表示相鄰邊和公共面的合并計算，應用式(2)計算結果如圖1所示。

圖1 TEN二、三維單純形的合并計算

刪除是合并的逆運算，如果隱式保留合并計算前各要素的指針，刪除計算是可以實現的，而且是可逆的。但如果對未進行合并運算的TEN進行刪除運算，則必須對TEN進行空間三角剖分，此時刪除運算變得復雜多變。根據九交模型，對TEN的結點、邊、三角形和四面體進行建模，可得到16種拓撲關系，去除6種不存在和無意義的關系，可得到如下10種拓撲關系：

1)一個結點與已有TEN的某結點重合，另一結點在各TEN的公共邊，這時各個TEN被一分為二。

2)一個結點與已知點重合，另一點在公共三角形面上，這時每個TEN被一分為三。

3)一個結點與已知點重合，另一點在某TEN內部，單個TEN被一分為四。

4)起始結點在邊界三角形上，終結點在邊上。

5)起始結點在三角形上，終結點在TEN內。

6)起始結點、終結點均在三角形上。

7)起始結點在三角形上，終結點在邊上。

8)約束邊被相交三角形分成兩段。

9)第二結點插入三角形面。

10)第二結點被插入到三角形某邊。

圖2展示了a，b，c 3種關系，上述10種關系的實質是采用約束線對TEN進行分割，然后生成子TEN，其特點是線的兩個端點與TEN的某一要素層級相交，這種設計的目的是為了避免復雜的空間剖分，使刪除計算變得復雜。

圖2 TEN刪除計算的10種情形

上述的各種情形，在TEN結構設計中必須體現，即TEN的結構設計必須考慮兩個條件，第一TEN結構必須要體現自身點、邊、三角形、四面體結構；第二是必須滿足TEN的拓撲關系計算，這樣才能實現TEN的動態編輯，因此，TEN結構的拓撲關系特別重要，它是刪除、合并計算的基礎。

2.2 TEN拓撲結構檢查

TEN的構成可以基于點、線或面，由于基于點描述最簡單，因而被各種建模軟件廣泛采用。點構成規則主要檢驗點的重合性和共面性，如果TEN空間4點僅有2點重合，TEN退化為三角形，如果3、4個點重合，則TEN退化為邊與點，因此不存在共面點是TEN的構成規則。滿足點的構成規則條件下，應用歐拉公式(式(3))對TEN進行拓撲結構檢驗。

(3)

2.3 TEN復合體的一致性檢驗

復合體一致檢查主要包括連續性檢查、完整性檢查與表面(內、外表面)一致性檢查，3項檢查遵從由前到后的順序。連續性檢查是檢驗相連TEN的連接關系，連接規則可自定義，這里規定以三角形相連的TEN是合法的，這個連接規則已在TEN的數據結構中予以體現。完整性檢查則是應用式(4)對TEN復合體進行整體檢查，在式(4)中，L為幾何體的環數，分為外環與內環，S為殼數，G為穿過幾何體的洞數，這項檢查需要設計“洞”、“殼”、“環”的判斷算法，實現比較麻煩。

(4)

3 TEN建模實驗

3.1 TEN的合并與刪除

在VC++環境下，對TEN的合并和刪除操作進行了實驗，其中創建TEN采用的是種子生成算法，設計了Ten類對TEN的創建進行了實現，為了便于實驗進行，這里設計了and()函數，將3個TEN合并為一個TEN，并保留合并結點(圖3(a))，用以保證TEN的逆操作。根據前文所述，TEN的數據結構既顧及到自身結構，又顧及到拓撲要求，TEN的結構部分代碼如下:

Class Ten

{

long CTenID;//TEN的ID;用于索引

CarrayID_OF_Triangle;//組成單體TEN所有三角形

Attribute_OF_Ten attibute;//TEN的幾何與非幾何屬性

long Belong_Which; //TEN屬于哪個多胞元復合體

bool Is_ConstructTop()；//拓撲結構是否建立

bool Is_Ten_Deleted;//TEN是否被刪除

bool Is_Checked;//拓撲結構檢查是否進行

bool Is_ContainStraint;//是否包含拓撲約束

};

在刪除時計算設計了subtraction()函數，其運算過程是：先選擇剖分點，然后生成分割線，最后將TEN分割為若干子TEN，剔除相應的子TEN，完成刪除操作(圖3(b))。為了實現TEN復合體的一致性檢驗，這里設計并實現了TEN復合體的結構，以滿足拓撲檢查，TEN復合體結構部分代碼如下:

Class CmBody

{

long ID_OF_CompoundBody;//復合體的標識號

CarrayIDs_OF_Ten;//組成復合體的TEN集合

Ten_CompoundBody_Attribute RWB ;//復合體的屬性

Carray Adjacent_CompoundBody; //相鄰的TEN復合體

bool Is_Deleted;//是否被合并

bool HasHoles;//是否有洞

bool HasIslands;//是否有島

bool HasShells;//是否有殼

bool IsConsistencyChecked;//是否進行過拓撲一致性檢查

};

在VC++環境中，程序完成了TEN的生成、合并與刪除每次操作前后，調用了 Is_Checked()函數和IsConsistencyChecked()函數進行了TEN自身拓撲結構檢查和TEN復合體的一致性檢驗。IsConsistencyChecked()函數運行時，調用了HasIslands()、HasShells()、HasHoles()3個函數，分別完成了島、殼、洞的判斷，使拓撲一致性檢查得以實現。

圖3 TEN的合并與刪除

3.2 DBMS連接

TEN由點、線、面、體4個抽象要素構成，由于客觀實體比較復雜，因此構成實體的TEN數量較多，因此TEN所連接的屬性表眾多，這是TEN模型的一個缺點。如果TEN中單純形Sn的屬性為A(Sn)，則屬性類型集合A(Tn)如式(5)所示；如果結點、邊、三角形、四面體的屬性數分別為m，n，u，v，則TEN的總的屬性數的保留公式如式(6)所示[9]。

(5)

SUMTEN=4m+6n+4u+v.

(6)

如圖4(a)所示，房屋模型用FDS(Formal Data Structure)表達時[10]，由1個體、7個面、15個邊、10個點構成，其屬性表數為要素個數33個，而用TEN表達，則由8個體、24個面、25個邊、10個點構成，屬性數為8×1+4×24+6×25+4×10=294個，可見屬性表數較多，因此，需要充分考慮TEN各級要素的屬性信息，包括圖形屬性和非圖形屬性信息。

在Ten類中，變量CTenID標識了TEN的ID，且此ID是以TEN結點編碼為索引進行遍歷的，由于三維模型總存在拓撲操作，因此TEN也不斷變化，以TEN結點編碼為索引可以隨拓撲關系變化而變化，因此TEN的幾何信息查詢易于實現。TEN的基本操作諸如距離查詢、體積計算、線的可視性分析等均易于實現，其它復雜分析諸如緩沖區分析和疊加分析，也是易于實現的。TEN查詢一般分為幾何信息查詢和非幾何信息查詢，非幾何查詢需要建立DBMS，使之與幾何信息通過表ID進行連接，并進行修改與存儲，最后實現查詢分析。

在研究中，對房屋模型進行三維莫頓碼編碼[11]，即對構成房屋的各個TEN結點進行編碼，編碼時采用的順序為x1y1z1x2y2z2x3y3z3x4y4z4，例如，最底端代碼(100000000600100600100608)表示頂點坐標為(10,00,00)，(00,06,00)，(10,06,08)的TEN編碼，最后形成的編碼如圖4(b)左端所示。三維莫頓碼是信息查詢分析的索引基礎，與TEN的ID進行了綁定。當TEN與外部DBMS進行鏈接，首先搜索TEN的ID，搜索到TEN的幾何信息表，再通過ID與外部DBMS關聯。圖5(a)展示房屋模型P面信息查詢時幾何屬性表與DBMS連接的信息；圖5(b)左側為幾何屬性表，右側為DBMS屬性信息。

圖4 房屋TEN模型屬性表數

圖5 TEN模型的DBMS查詢

4 結 論

以龐卡萊代數為基礎的三維GIS模型易于表達實體的動態變化，能完美支持合并和刪除運算，并且可以實時進行拓撲一致性檢查。基于龐卡萊的邊界表達法，本文在VC++環境中設計了TEN拓撲結構和TEN復合體結構，并實現了TEN模型的合并與刪除操作。實驗證明，基于龐卡萊代數的TEN拓撲關系易于建立，所生成的不規則四面體網適宜于表達不規則實體，如不規則礦體等。同時，基于龐卡萊代數的TEN創建、合并和刪除均易于實現，也易于進行拓撲一致性檢查與DBMS連接。后續的研究應集中于TEN表的數據冗余去除與可視化表達，使三維GIS模型既結構簡單，又具有良好的可視性與空間分析能力。

[1] 馬威,李崇貴,林宏波. 基于ArcGIS的礦區三維可視化技術研究[J].礦山測量,2014(2):30-33.

[2] 孫華芬,侯克鵬,郭延輝. 基于SQL Server平臺復雜地質體FLAC3d模型的構建[J].遼寧工程技術大學學報(自然科學版),2012,31(4):500-503.

[3] 吳立新，史文中．地理信息系統原理與算法[M]．北京：科學出版社，2003．

[4] ABDUL-RAHMAN A，PILOUS M.Spatial Data Modelling for 3D GIS[M].New York:Springer Berlin Heidelberg New York,2008.2-3.

[5] WANG Yanbing, WU Lixin, SHI Wenzhong, et al.ON 3D GIS SPATIAL MODELING[A].ISPRS Workshop on Updating Geo-spatial Databases with Imagery & The 5th ISPRS Workshop on DMGISs[C].2007:237-240.

[6] 孫敏,薛勇,馬藹乃,等.基于四面體格網的3維復雜地質體重構[J].測繪學報,2002, 31(4):361-365.

[7] 程朋根,文紅.三維空間數據建模及算法[M].北京:國防工業出版社,2011:25-32.

[8] GEOGHEGAN R. Topological Methods in Group Theory[M].New York:Springer Science Business Media, 2008:353-362.

[9] 劉艷,武廣臣.基于龐加萊代數的3D TEN模型及其拓撲關系建立研究[J].測繪科學,2014,39(4):17-19.

[10] ZLATANOVAL S,RAHMAN A A,SHI Wenzhong.TOPOLOGY FOR 3D SPATIAL OBJECTS[J].Geoinformation Science Journal,2003, 3(1):56-65.

[11] WU Lixin, SHI Wenzhong. GTP-based Integral Real-3D Spatial Model for Engineering Excavation GIS (E2GIS)[J].Geo-Spatial Information Science,2004,7(2):123-128.

[責任編輯：劉文霞]

Research on TEN 3D GIS model based on Poincaré algebra

MA Yumei1,MA Chao2

(1.The Second Surveying and Mapping Institute of Xinjiang Uygur Autonomous Region，Urumqi 830002,China;2.School of Geography,Northeast Norma University,Changchun 130024,China)

Irregular tetrahedral network has the characteristics of simple structure, easy to expand. By means of Poincare algebra,TEN model is proposed by using boundary representation theory in this paper.Compared with the traditional geometric structure model, this model has the characteristics of simple expression and simplified calculation.At the same time, merge and delete operations as well as topology consistency checking are proposed based on Poincare algebra TEN.In the VC++ environment,the merge and delete operations are programed and then implemented.Experimental results show that ten model based on Poincare algebra can effectively establish a dynamic entity model,and it also can establish real-time topological relations,which is suitable for 3D entity such as irregular ore body that changes every time.

Poincaré algebra; 3D GIS;irregular tetrahedral network; topological consistency; boundary expression

引用著錄：馬玉梅，馬超.基于龐卡萊代數的TEN三維GIS模型研究[J].測繪工程，2017，26(5)：62-66.

10.19349/j.cnki.issn1006-7949.2017.05.013

2016-04-30

馬玉梅(1983-)，女，工程師，碩士.

P208

A

1006-7949(2017)05-0062-05