E-WID 三維拓?fù)潢P(guān)系計算方法與實現(xiàn)

楊國紅，周曉光,2，賀鴻愿,2，侯東陽,2，李存志,2

1. 中南大學(xué) 地球科學(xué)與信息物理學(xué)院， 長沙 410083；

2. 自然資源部時空信息與智能服務(wù)重點實驗室，長沙 410083

1 引 言

自然資源部辦公廳2022 年《全面推進實景三維中國建設(shè)的通知》中稱：“實景三維作為真實、立體、時序化反映人類生產(chǎn)、生活和生態(tài)空間的時空信息，是國家重要的新型基礎(chǔ)設(shè)施”。其建設(shè)包括建立地上、地下、室內(nèi)、室外等地理空間實體的三維結(jié)構(gòu)及時空關(guān)系等（陳軍等，2022）。三維拓?fù)潢P(guān)系作為最重要也是最基本的空間關(guān)系（Belussi 等，2020），是實景三維建設(shè)及三維（three dimensions，3D）地理信息系統(tǒng)（geographic information system，GIS）中三維空間數(shù)據(jù)質(zhì)量控制（何建寧等，2022）、更新處理與空間分析（Emamgholian 等，2021；Salleh，2021；黃蘭蘭等，2022）的理論基礎(chǔ)。

三維空間數(shù)據(jù)間的拓?fù)潢P(guān)系類型多樣（曹全龍等，2023）。其無法一一存儲，不同拓?fù)潢P(guān)系類型對應(yīng)的沖突與更新等處理操作迥異，因此，需要用特定模型對其進行形式化區(qū)分，以便于計算機自動識別與計算（Egenhofer 和Franzosa，1991；陳軍和趙仁亮，1999）。國內(nèi)外研究針對這一關(guān)鍵問題開展了大量工作，如建立了三維4I（郭薇和陳軍，1997）、9I（Egenhofer 和Herring，1990）、25I（Zhou 和Guan，2019）、K6N9-I（郭甲騰和吳立新，2008）和GA-based（Yuan 等，2014） 等模型。這些模型大多是基于二維4I 、9I 模型發(fā)展起來的，并存在一些不足，如對于復(fù)雜目標(biāo)的適用性有限、區(qū)分能力不足等。另外，當(dāng)前應(yīng)用比較廣泛的9I（3D）模型僅定義了三維簡單目標(biāo)間的拓?fù)潢P(guān)系，不能區(qū)分帶通道（如帶窗戶的墻壁）或空穴（如帶溶洞的地質(zhì)體）等復(fù)雜目標(biāo)間的拓?fù)潢P(guān)系類型，且9I（3D）模型只能區(qū)分八種簡單體/體關(guān)系（其中只有一種相交關(guān)系），不能區(qū)分如圖1（b）~（d）所示的三種常見拓?fù)潢P(guān)系。因此，賀鴻愿（2021）引入流形拓?fù)淅碚?，將已有?E-WID（ Euler-number-based whole-object intersection and difference）模型（Zhou 等，2013），拓展至三維空間，建立了適用于復(fù)雜目標(biāo)且比現(xiàn)有三維拓?fù)潢P(guān)系模型區(qū)分能力更強的三維E-WID（3D）拓?fù)潢P(guān)系模型。拓?fù)潢P(guān)系在三維數(shù)據(jù)更新中具有重要作用。如圖1（b）、（d）所示，灰色墻壁為室內(nèi)新增墻壁，與原紅色墻壁間都有交，但圖1（d）新增墻B 穿過了舊墻A，一般為沖突。E-WID（3D）雖然能夠區(qū)分如圖1 所示拓?fù)潢P(guān)系，但目前尚缺乏其拓?fù)潢P(guān)系計算方法。

圖1 主墻墻壁與隔墻墻壁間不同的拓?fù)潢P(guān)系示例Fig.1 Example of different topological relationship between a main wall and a partition wall

E-WID（3D）模型并不局限于單一的數(shù)據(jù)組織方式，但由于拓?fù)潢P(guān)系計算依賴于空間目標(biāo)的幾何數(shù)據(jù)，因此，計算的具體實現(xiàn)需借助特定的三維空間數(shù)據(jù)組織模型?，F(xiàn)有代表性三維數(shù)據(jù)組織模型中，B-Rep模型在GIS 中使用最為廣泛，且已被ISO、OGC（open geospatial consortium）和CityGML（city geography markup language）等組織所采用(Zhou 等，2013；吳立新和史文中，2005；樊文平等，2005)。其中, Nef多面體數(shù)據(jù)組織模型具有能夠表達復(fù)雜目標(biāo)（如帶通道或空穴的體），對應(yīng)的布爾運算結(jié)果可表示為閉集且可以保留低維的幾何元素（如兩體間交集的點、線與面片）等特點（Hachenberger 等，2007）相較于其他B-Rep 模型能更好地與E-WID（3D）模型結(jié)合。

綜上所述，本文利用Nef 多面體3D 數(shù)據(jù)模型及對應(yīng)的布爾運算算法，研究了三維E-WID 拓?fù)潢P(guān)系計算方法，其中，包括基于集合運算結(jié)果的空間組件構(gòu)建、維度與歐拉數(shù)計算算法等，模擬實現(xiàn)了三維空間目標(biāo)間的E-WID（3D）拓?fù)潢P(guān)系的計算。

2 基于Nef 多面體的E-WID(3D)拓?fù)潢P(guān)系計算總體思路

2.1 E-WID(3D)拓?fù)潢P(guān)系模型

E-WID（3D）拓?fù)潢P(guān)系模型引入流形拓?fù)鋵Χ⑷S基本空間目標(biāo)進行統(tǒng)一形式化定義，通過目標(biāo)整體交/差結(jié)果的維數(shù)和歐拉數(shù)取值的不同來區(qū)分二元目標(biāo)間的拓?fù)潢P(guān)系類型。E-WID(3D)模型的描述公式如下（賀鴻愿，2021）：

式中，fD為集合運算結(jié)果的維度取值，當(dāng)結(jié)果為空或各組件純?yōu)辄c（零維）、純?yōu)榫€（一維）、純?yōu)槊妫ǘS）、純?yōu)轶w（三維）五種基本情形時，對應(yīng)的取值分別為{–1,0,1,2,3}；當(dāng)結(jié)果為點線混合、點面混合、點體混合、線面混合、線體混合、面體混合、點線面混合、點線體混合、點面體混合、線面體混合與線面體混合時，對應(yīng)的取值分別為{4,5,6,7,8,9,10, 11,12,13,14}；fE為集合運算結(jié)果中各空間組件歐拉數(shù)的合計值，當(dāng)結(jié)果為空時取值為0，整體取值范圍為（–∞,+∞）。

2.2 E-WID(3D)拓?fù)潢P(guān)系計算總體思路

兩空間目標(biāo)間E-WID（3D）拓?fù)潢P(guān)系計算一般包括五個關(guān)鍵步驟。以圖2 中的兩簡單體A和B為例，其計算步驟包括 ：①獲取兩空間目標(biāo)的幾何數(shù)據(jù)等； ②對兩目標(biāo)進行整體交/差集合運算；③構(gòu)建滿足E-WID（3D）模型中維度和歐拉數(shù)計算需求的交/差空間組件，如圖2（b）中交集的非流形需分解為流形等；④依次計算各交/差組件的維度和歐拉數(shù)；⑤計算各集合運算結(jié)果的fD和fE取值并進行形式化表達與檢驗。

圖2 兩三維空間目標(biāo)（簡單體）間E-WID（3D）拓?fù)潢P(guān)系計算步驟示例“Dim（）”為組件的維數(shù)；“Eul（）”為組件的歐拉數(shù)；si 為交集組件；sd 為差集組件Fig.2 Example of the steps for calculating the E-WID (3D) topological relationship between two three-dimensional objects(simple monomers)

基于Nef 多面體的E-WID（3D）拓?fù)溆嬎懔鞒?，如圖3 所示。包括如下步驟：①讀取三維空間目標(biāo)A、B空間數(shù)據(jù)，并將其轉(zhuǎn)換為Nef 多面體；②對兩Nef 多面體A與B進行整體交/差集合運算；③構(gòu)建交/差運算結(jié)果的拓?fù)浣M件；④依次計算各交/差組件的維度和歐拉數(shù)；⑤計算各集合運算結(jié)果的fD和fE取值；⑥將計算結(jié)果轉(zhuǎn)化為式（1）中的描述矩陣。上述過程中，數(shù)據(jù)獲取與格式轉(zhuǎn)換、布爾運算、形式化結(jié)果轉(zhuǎn)換與檢驗等的實現(xiàn)均相對簡易，但兩Nef 多面體整體間交/差集組件拓?fù)錁?gòu)建及其應(yīng)歐拉數(shù)計算實現(xiàn)相對復(fù)雜。

圖3 Nef 多面體的E-WID（3D）拓?fù)潢P(guān)系計算流程Fig.3 Calculation flow of E-WID (3D) topological relations in Nef polyhedron

3 E-WID(3D)拓?fù)潢P(guān)系計算方法

由于三維空間目標(biāo)的幾何結(jié)構(gòu)及相互關(guān)系的復(fù)雜和多樣性，三維空間目標(biāo)間的交/差集合運算的結(jié)果極其復(fù)雜多樣。如圖4 所示，兩目標(biāo)之間的交集可能同時出現(xiàn)點、線、面和體四種不同維度交集組件混存的情形；且這些交集組件之間不一定彼此相離，如圖2（b）中（si1和si2相接）。而對兩Nef多面體（空間目標(biāo)）進行布爾運算后，其運算結(jié)果依然是將其整體作為一個Nef 多面體，并未自動將其分割成彼此獨立的空間組件（流形）。因此，要計算兩Nef 多面體間的E-WID(3D)拓?fù)潢P(guān)系，需先依據(jù)布爾運算結(jié)果對相應(yīng)的交/差組件進行拓?fù)錁?gòu)建。

圖4 兩體體間具有不同維度的交集組件示例Fig.4 Example of intersection components with different dimensions between two objects

3.1 交/差組件的拓?fù)浞治雠c構(gòu)建

3.1.1 交/差組件集合的拓?fù)浞治?/p>

在三維空間目標(biāo)的交/差集合運算結(jié)果中，常見的空間對象點、線、面可以相對容易地識別（圖5），因為它們具有明確的幾何形狀和位置。因此，獲取它們的空間信息相對較為簡單，無需進行過多的處理。通過識別和獲取這些基本組件的空間信息，可以進一步分析和處理三維空間目標(biāo)的交/差集合運算結(jié)果，以獲得更復(fù)雜的拓?fù)潢P(guān)系和幾何信息。

圖5 交/差集合運算中Nef 多面體的基礎(chǔ)情形Fig.5 Basic scenarios of Nefpolyhedron in set operations of intersection/difference

在集合交/差運算中，還會出現(xiàn)一些混合或相連的情況，包括：①線與面相連，如在圖6（a）中，線l1與面s1相連；②線與體相連，如在圖6（b）中，線l1與體sd1相連；③面與面相連，如在圖6（c）中，面s1與面s2相連；④面與體相連，如在圖6（d）中，面s1與體sd1相連。

圖6 集合運算結(jié)果中Nef 多面體的帶懸掛情形Fig.6 Hanging situation of the Nef polyhedron in set operation results

在存在不同維度組件混合的情況下，需要對各個組件分別進行處理，并獲取它們的拓?fù)湫畔?。特別是當(dāng)集合交/差運算中存在不同維度組件相連時，需要對不同維度的組件進行拆分，以便準(zhǔn)確地分析和計算它們的拓?fù)潢P(guān)系。因此，在進行三維空間目標(biāo)的交/差集合運算時，需要綜合考慮不同維度組件之間的連接和相互關(guān)系，并采取相應(yīng)的方法來處理和解決這些情況，以獲得準(zhǔn)確的拓?fù)湫畔ⅰ?/p>

以交/差運算結(jié)果中存在面與面連接或面與體連接的情況為例，可以判斷面元素中的所有邊是否都與其他面相連來獲取交/差運算結(jié)果的拓?fù)湫畔?。如果存在一條或多條邊沒有與其他面相連，則該面可以構(gòu)成一個獨立的二維交/差組件。例如，在圖6（c）中，面s1只有一條邊與相連面相連，其余的邊沒有與其他面相連；在圖6（d）中，面s1也只有一條邊與相連體的面相連，其余的邊沒有與其他面相連。因此，根據(jù)邊界相連情況，可以確定s1為一個獨立的二維交/差組件。通過識別和判斷交/差運算結(jié)果中的二維面元素，以及其邊與其他面的連接情況，可以將獨立的二維組件確定出來，并進行相應(yīng)的處理。這樣可以準(zhǔn)確地分析和計算三維空間目標(biāo)間的拓?fù)潢P(guān)系。

在處理三維空間目標(biāo)間的交/差集合運算結(jié)果時，處理空洞是一個關(guān)鍵問題?？斩词窃诮?差運算結(jié)果中存在未被填充或連接的空缺區(qū)域。在圖7 中，簡單面A與簡單面B進行差集運算（AB）形成了一個帶有空洞的平面目標(biāo)（圖7（b））。針對這個問題，可以利用簡單面A與簡單面B的交集運算結(jié)果（A∩B，圖7（c））與目標(biāo)進行判斷。通過判斷兩個目標(biāo)是否完全相同，可以得出目標(biāo)B 是否包含于目標(biāo)A，從而獲取差集運算（AB）的空洞信息，并完成目標(biāo)的構(gòu)建。這種方法通過比較交集運算結(jié)果與目標(biāo)本身的一致性，來判斷空洞的存在與位置，從而實現(xiàn)對空洞的處理。這種處理方式可以提供更準(zhǔn)確的空間信息，并為后續(xù)的拓?fù)潢P(guān)系計算提供可靠的基礎(chǔ)。

圖7 集合運算結(jié)果中Nef 多面體的帶空洞情形Fig.7 Nef polyhedron with voids in set operation results

3.1.2 交/差組件的拓?fù)錁?gòu)建

在E-WID（3D）模型中，集合運算結(jié)果中的空間組件都對應(yīng)著一個連通的緊致（閉集）的n流形，其中，n表示維度，取值范圍為0≤n≤3。每個維度的組件都具有特定的幾何結(jié)構(gòu)和拓?fù)涮卣?。以二維交/差組件的拓?fù)錁?gòu)建為例，為了從集合運算結(jié)果中識別并構(gòu)建二維交/差組件，采取步驟如下。

首先，遍歷所有的面目標(biāo)，判斷每個面是否與其他面相連。如果某個面有一條以上的邊沒有與其他面相連，則將其記錄為一個二維組件。同時，當(dāng)遇到帶有空洞的平面時，也需要將其記錄為二維組件并進行標(biāo)記。其次，完成所有面目標(biāo)的處理后，需要進一步判斷構(gòu)建的二維組件之間是否存在相連。如果存在相連的情況，需要將它們合并為一個更大的二維組件。此外，如果二維組件的連接形成了環(huán)形通道，需要將這些環(huán)形通道單獨記錄并進行存儲。最后，通過這一系列步驟，完成二維交/差組件的構(gòu)建。

判斷規(guī)則一：設(shè)face 為集合運算結(jié)果平面集中faces 中的任意一個面，edge 為 face 的邊，facei(i∈(1,n))為faces 中的面，edgej(j∈(1,n))為組成facei中的邊，isolatedFace 為孤立面；如果edge 不等于facei.edgej，則face 為孤立面。

當(dāng)使用CGAL 庫中Nef 多面體表示時，可以通過檢查Nef 多面體中的平面數(shù)據(jù)是否存在內(nèi)環(huán)和外環(huán)，來判斷是否存在空洞，可直接判斷目標(biāo)是否存在空洞，此處不再展開，二維組件是否相連與一維組件中的判斷類似，下面是設(shè)計的規(guī)則。

判斷規(guī)則二：設(shè) isolatedFace 為孤立面，isolatedFacei(i∈(1,n))為孤立面isolatedFaces中的面，mergedFace(isolatedFace,isolatedFacei)為孤立面合并函數(shù)，edge 為孤立面的邊；如果isolatedFace.edge與 isolatedFacei.edge 相等，則執(zhí)行合并操作mergedFace(isolatedFace,isolatedFacei)。

基于二維組件的構(gòu)建規(guī)則，使用交/差集合運算結(jié)果中的平面集合與平面邊界集合，可實現(xiàn)二維交/差組件的構(gòu)建，二維交/差組件的構(gòu)建算法如圖8所示。

圖8 二維交/差組件的構(gòu)建算法Fig.8 Construction algorithm for 2D intersection/difference components

3.2 交/差組件的歐拉數(shù)計算

因為已構(gòu)建好的各維度交/差組件均對應(yīng)于一個流形（可胞腔剖分），所以其對應(yīng)的歐拉數(shù)均可以通過如下計算（Lee，2010）：

式中，X為一個可胞腔（或三角）剖分的拓?fù)淇臻g（或緊致流形）；n為X的維度；ai為X中i維胞腔（cell）的數(shù)目；Eul（X）為X的歐拉數(shù)。

對于零維、一維和二維的交/差組件，因均不包含三維胞腔，故其歐拉數(shù)可以統(tǒng)一通過式（2）的簡化公式來計算，即

式中，V為對應(yīng)組件經(jīng)胞腔（或三角）剖分后的頂點數(shù)；E為邊數(shù)；F為面數(shù)。

需要說明的是，雖然Nef 多面體數(shù)據(jù)中含有頂點、邊和面等幾何元素，但是這些元素并非胞腔剖分的結(jié)果，故需將對應(yīng)的交/差組件先進行三角剖分，才能依式（3）計算。經(jīng)剖分后，零維組件的邊數(shù)和面數(shù)均為零，一維組件的面數(shù)為零。如圖9（a）中零維組件A只含有1 個頂點，所以歐拉數(shù)等于1（V=1）；圖9（b）中一維組件B含有3 個頂點和2 條邊，所以歐拉數(shù)等于1（V–E=3–2=1）；圖9（c）中二維組件C(簡單面)含有3 個頂點、3條邊和 1 個面，所以歐拉數(shù)等于 1（V–E+F=3–3+1=1）；圖9（d）中二維組件D(帶洞面)含有8個頂點、16 條邊和8 個面，所以歐拉數(shù)等于0（V–E+F=8–16+8=0）。

圖9 零維、一維與二維組件的歐拉數(shù)計算示例Fig. 9 Example of Euler number calculation for zero-dimensional, one-dimensional and two-dimensional components

由于三維交/差組件含有三維胞腔，但Nef 多面體只表達了其邊界而忽略了其三維內(nèi)部，所以在數(shù)據(jù)層面無法依式（2）或式（3）直接計算。需先將其邊界進行三角剖分后，然后依式（2）計算其邊界的歐拉數(shù)，最后依式（4）計算其最終的歐拉數(shù)（Lee，2010）：

式中，C為一個體目標(biāo)；?C為體的邊界。

4 實驗驗證

為了驗證所提出的三維空間數(shù)據(jù)間的E-WID（3D）拓?fù)潢P(guān)系計算方法的可行性，選取開源的Blender 構(gòu)建實驗數(shù)據(jù)，對系統(tǒng)的相關(guān)功能及相應(yīng)拓?fù)潢P(guān)系的計算進行實驗驗證。驗證了體/體關(guān)系19種，體/面關(guān)系18 種，面/面關(guān)系18 種，體/線關(guān)系11 種，面/線關(guān)系10 種，線/線關(guān)系10 種，體/點關(guān)系3 種，面/點關(guān)系3 種，線/點關(guān)系3 種，點/點關(guān)系2 種等基本拓?fù)潢P(guān)系類型（賀鴻愿，2021）計算的可行性。圖1 中新建墻壁與原墻壁相交，存在沖突的兩種情形，9I（3D）模型不能區(qū)分。而本文方法實現(xiàn)了自動計算，并且可以準(zhǔn)確區(qū)分墻體打斷、貫穿情形，如圖10 所示。

圖10 E-WID(3D)拓?fù)潢P(guān)系計算示例（A）為三維空間目標(biāo)A；（B）為三維空間目標(biāo)B；R(A,B)為兩個三維空間目標(biāo)在真實空間中的相對位置形態(tài)Fig. 10 Example of E-WID (3D) topological relation calculation

5 結(jié) 論

三維拓?fù)潢P(guān)系是最基本且最重要的空間關(guān)系，其計算實現(xiàn)是空間數(shù)據(jù)質(zhì)量控制與處理等應(yīng)用的基礎(chǔ)?；贜ef 多面體數(shù)據(jù)模型及布爾運算，本文分析了三維空間目標(biāo)間的交/差集合運算的結(jié)果，設(shè)計了E-WID(3D)拓?fù)潢P(guān)系模型中的交/差組件拓?fù)錁?gòu)建與歐拉數(shù)計算的方法，并研發(fā)了對應(yīng)的原型計算系統(tǒng)，實現(xiàn)了三維空間數(shù)據(jù)間E-WID(3D)拓?fù)潢P(guān)系的自動計算。這為三維空間數(shù)據(jù)沖突檢測與基于拓?fù)潢P(guān)系的分析等應(yīng)用奠定了基礎(chǔ)。

本文僅實現(xiàn)了基于Nef 多面體的三維基本拓?fù)潢P(guān)系計算方法，而三維地理信息表達方式多樣，其他數(shù)據(jù)組織方法的三維拓?fù)潢P(guān)系計算可以參考本方法來實現(xiàn)或通過數(shù)據(jù)格式轉(zhuǎn)換方式調(diào)用。另外，三維拓?fù)潢P(guān)系的細(xì)分及在三維數(shù)據(jù)質(zhì)量控制、更新處理等方面的應(yīng)用將是下一步的研究方向。