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

馬玉梅，馬 超

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

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

馬玉梅1，馬 超2

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

不規(guī)則四面體網(wǎng)具有結(jié)構(gòu)簡單、易于擴展的特性。借助于龐卡萊代數(shù)，應(yīng)用邊界表示理論重新描述了TEN模型。與傳統(tǒng)幾何結(jié)構(gòu)模型相比，這種模型具有表達簡單、易于計算的特點。同時，提出基于龐卡萊代數(shù)的TEN合并和刪除運算以及拓撲一致性檢查。在VC++環(huán)境下，對TEN模型的合并和刪除運算進行編程與實現(xiàn)。實驗表明，基于龐卡萊代數(shù)的TEN模型可以有效建立動態(tài)實體模型，能夠?qū)崟r建立拓撲關(guān)系，適合于表達不規(guī)則礦體等動態(tài)變化的三維實體。

龐卡萊代數(shù)；三維地理信息系統(tǒng)；不規(guī)則四面體格網(wǎng)；拓撲一致性；邊界表達法

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

1 龐卡萊TEN模型

1.1 拓撲結(jié)構(gòu)

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分別為，，，，，，若，，標記“+”，則，,相應(yīng)地標記為“-”，并且有=-，=-，=-。在二維條件下，正負號可以判斷某面的法向量，從而區(qū)分模型的內(nèi)外性，三維條件下的推理類似二維情況。

(1)

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

(2)

2 龐卡萊TEN運算

基于龐卡萊代數(shù)的3D TEN明顯特點是TEN可以實時動態(tài)更新，空間實體由有限個TEN組成，在某些TEN發(fā)生諸如合并、刪除變化后，龐卡萊代數(shù)運算可以重建每次變化的拓撲關(guān)系，這與以往單純的基于幾何的TEN模型是完全不同的。基于龐卡萊代數(shù)的TEN拓撲檢查伴隨著實體的存在而存在，這種檢查體現(xiàn)了構(gòu)成實體的各個TEN與實體的拓撲統(tǒng)一。

2.1 TEN合并與刪除

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

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

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

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

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

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

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

5)起始結(jié)點在三角形上，終結(jié)點在TEN內(nèi)。

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

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

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

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

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

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

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

上述的各種情形，在TEN結(jié)構(gòu)設(shè)計中必須體現(xiàn)，即TEN的結(jié)構(gòu)設(shè)計必須考慮兩個條件，第一TEN結(jié)構(gòu)必須要體現(xiàn)自身點、邊、三角形、四面體結(jié)構(gòu)；第二是必須滿足TEN的拓撲關(guān)系計算，這樣才能實現(xiàn)TEN的動態(tài)編輯，因此，TEN結(jié)構(gòu)的拓撲關(guān)系特別重要，它是刪除、合并計算的基礎(chǔ)。

2.2 TEN拓撲結(jié)構(gòu)檢查

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

(3)

2.3 TEN復(fù)合體的一致性檢驗

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

(4)

3 TEN建模實驗

3.1 TEN的合并與刪除

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

Class Ten

{

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

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

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

long Belong_Which; //TEN屬于哪個多胞元復(fù)合體

bool Is_ConstructTop()；//拓撲結(jié)構(gòu)是否建立

bool Is_Ten_Deleted;//TEN是否被刪除

bool Is_Checked;//拓撲結(jié)構(gòu)檢查是否進行

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

};

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

Class CmBody

{

long ID_OF_CompoundBody;//復(fù)合體的標識號

CarrayIDs_OF_Ten;//組成復(fù)合體的TEN集合

Ten_CompoundBody_Attribute RWB ;//復(fù)合體的屬性

Carray Adjacent_CompoundBody; //相鄰的TEN復(fù)合體

bool Is_Deleted;//是否被合并

bool HasHoles;//是否有洞

bool HasIslands;//是否有島

bool HasShells;//是否有殼

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

};

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

圖3 TEN的合并與刪除

3.2 DBMS連接

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

(5)

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

(6)

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

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

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

圖4 房屋TEN模型屬性表數(shù)

圖5 TEN模型的DBMS查詢

4 結(jié) 論

以龐卡萊代數(shù)為基礎(chǔ)的三維GIS模型易于表達實體的動態(tài)變化，能完美支持合并和刪除運算，并且可以實時進行拓撲一致性檢查?；邶嬁ㄈR的邊界表達法，本文在VC++環(huán)境中設(shè)計了TEN拓撲結(jié)構(gòu)和TEN復(fù)合體結(jié)構(gòu)，并實現(xiàn)了TEN模型的合并與刪除操作。實驗證明，基于龐卡萊代數(shù)的TEN拓撲關(guān)系易于建立，所生成的不規(guī)則四面體網(wǎng)適宜于表達不規(guī)則實體，如不規(guī)則礦體等。同時，基于龐卡萊代數(shù)的TEN創(chuàng)建、合并和刪除均易于實現(xiàn)，也易于進行拓撲一致性檢查與DBMS連接。后續(xù)的研究應(yīng)集中于TEN表的數(shù)據(jù)冗余去除與可視化表達，使三維GIS模型既結(jié)構(gòu)簡單，又具有良好的可視性與空間分析能力。

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

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

[3] 吳立新，史文中．地理信息系統(tǒng)原理與算法[M]．北京：科學(xué)出版社，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] 孫敏,薛勇,馬藹乃,等.基于四面體格網(wǎng)的3維復(fù)雜地質(zhì)體重構(gòu)[J].測繪學(xué)報,2002, 31(4):361-365.

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

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

[9] 劉艷,武廣臣.基于龐加萊代數(shù)的3D TEN模型及其拓撲關(guān)系建立研究[J].測繪科學(xué),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.

[責(zé)任編輯：劉文霞]

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

引用著錄：馬玉梅，馬超.基于龐卡萊代數(shù)的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