楊　乃，賈　躍，蘇黎蘭，萬　林，楊　潔

(1. 中國地質(zhì)大學(xué)信息工程學(xué)院，湖北 武漢 430074； 2. 揚(yáng)州市城市規(guī)劃編制研究中心，江蘇揚(yáng)州 225002； 3. 中國地質(zhì)大學(xué)公共管理學(xué)院，湖北 武漢 430074)

?

基于點(diǎn)集的拉伸建模改進(jìn)方法

楊乃1，賈躍2，蘇黎蘭3，萬林1，楊潔1

(1. 中國地質(zhì)大學(xué)信息工程學(xué)院，湖北 武漢 430074； 2. 揚(yáng)州市城市規(guī)劃編制研究中心，江蘇揚(yáng)州 225002； 3. 中國地質(zhì)大學(xué)公共管理學(xué)院，湖北 武漢 430074)

探討了拉伸建模存在公共基元重復(fù)構(gòu)建、側(cè)面空間關(guān)系丟失、產(chǎn)生冗余基元等拓?fù)鋯栴}，指出了不同地物三維模型兩個(gè)側(cè)面之間拓?fù)潢P(guān)系存在的12種表現(xiàn)形式，提出了基于點(diǎn)集的自動(dòng)拉伸建模方法，并分別介紹了點(diǎn)集的提取流程和體的構(gòu)建流程，最后通過一個(gè)實(shí)例證明了以上方法對傳統(tǒng)拉伸建模方法在拓?fù)潢P(guān)系方面存在的不足有所改進(jìn)。

拓?fù)潢P(guān)系；拉伸建模；三維建模；空間關(guān)系；地圖可視化

拓?fù)潢P(guān)系是最重要的一種空間關(guān)系[1-2]，是空間查詢與分析的基礎(chǔ)[3]，已廣泛應(yīng)用于制圖綜合、空間推理、空間數(shù)據(jù)挖掘等實(shí)際應(yīng)用中[4]。拓?fù)潢P(guān)系不一致將會(huì)導(dǎo)致空間認(rèn)知錯(cuò)誤，影響地圖的傳輸效果[2]。當(dāng)前，三維模型的拓?fù)錁?gòu)建與分析已成為3DGIS的主要研究內(nèi)容之一[5-10]。

以拉伸(Extrusion)的方式建立三維模型是3DGIS及三維建模軟件中常見的一種建模方法，尤其適用于具有規(guī)則形體結(jié)構(gòu)的地物模型構(gòu)建，如建筑物。這種建模方法往往不會(huì)考慮地物之間的拓?fù)潢P(guān)系，導(dǎo)致出現(xiàn)諸如公共面重復(fù)、垂直方向上空間關(guān)系丟失等問題，建立的模型常常僅限于可視化表達(dá)，無法進(jìn)行進(jìn)一步的空間分析[11]。針對這些問題，文獻(xiàn)[12]將整個(gè)區(qū)域的建筑和地形統(tǒng)一用一張Delaunay三角網(wǎng)表示，實(shí)現(xiàn)了類似拉伸的效果，但無法表達(dá)兩個(gè)相鄰建筑的垂直公共面；文獻(xiàn)[11]和文獻(xiàn)[13]基于約束性Delaunay三角網(wǎng)構(gòu)建了拓?fù)湟恢碌娜S城市模型，其中產(chǎn)生的若干點(diǎn)、若干面仍然可以進(jìn)一步綜合以降低拓?fù)鋸?fù)雜性。本文將對此進(jìn)行改進(jìn)，提出一種基于點(diǎn)集的自動(dòng)拉伸建模方法，能夠改進(jìn)傳統(tǒng)拉伸建模方法在拓?fù)潢P(guān)系方面存在的若干不足。

一、拉伸建模拓?fù)鋯栴}分析

三維空間中，體與體之間的拓?fù)潢P(guān)系共有8種[8-14]，在三維地籍與房產(chǎn)管理領(lǐng)域，建筑物的體對象之間只有相離和相鄰關(guān)系[5-6]，其底面也僅對應(yīng)存在這兩種關(guān)系。拉伸建模是將一系列描述體狀地物底面的多邊形按指定高度進(jìn)行拉伸拔高以形成塊狀多面體的三維建模方法，最適用于上述建筑體模型的建立[11]，如圖1所示。這種方式建立的三維模型主要存在如下拓?fù)鋯栴}。

圖1　拉伸建模圖示

1. 公共基元重復(fù)構(gòu)建

結(jié)點(diǎn)、邊、面和體是4種拓?fù)浠猍6]，如圖1(a)所示，多邊形A、B是俯視條件下相鄰地物的兩個(gè)底面示意圖，因高度不同，通過拉伸之后形成的三維模型如圖1(b)所示，其中，二者公共的部分(圖1(c)中mnde)的結(jié)點(diǎn)、邊、面在A、B拉伸時(shí)被分別構(gòu)建。

2. 側(cè)面空間關(guān)系丟失

如圖1所示，即使底面A、B之間存在拓?fù)潢P(guān)系，但拉伸建模之后，側(cè)面形成的結(jié)點(diǎn)、邊、面，如圖1(a)邊def對應(yīng)的側(cè)面(圖1(c))中共形成8個(gè)結(jié)點(diǎn)、10條邊、3個(gè)面，它們之間的相互關(guān)系并沒有得到有效存儲(chǔ)，不利于垂直方向上的空間分析。

3. 產(chǎn)生冗余基元

上文中公共基元重復(fù)構(gòu)建將產(chǎn)生一些重復(fù)的基元。此外，還會(huì)產(chǎn)生一些不必要的基元，具體如下：

1) 在底面數(shù)據(jù)采集時(shí)，經(jīng)常會(huì)出現(xiàn)多點(diǎn)重合的現(xiàn)象，拉伸建模后，頂面對應(yīng)將會(huì)產(chǎn)生重合點(diǎn)。

2) 底面邊線中間的若干節(jié)點(diǎn)拉伸建模后，在頂面形成對應(yīng)的節(jié)點(diǎn)，在對應(yīng)側(cè)面上被拉伸成為一條條直線，將側(cè)面分割為多個(gè)子側(cè)面。如圖1(a)邊bcd拉伸后，點(diǎn)c在頂面對應(yīng)形成點(diǎn)i，并被拉伸為直線ci，將側(cè)面bdjh分割為面bcih和面cdji(如圖1(c)所示)。

3) 多個(gè)具有不同高度屬性的底面相接時(shí)，某些公共點(diǎn)拉伸建模后將會(huì)導(dǎo)致冗余基元的產(chǎn)生。如圖1(a)所示，底面A與底面B高度屬性不同，拉伸建模后，邊def對應(yīng)的側(cè)面理應(yīng)被分割為具有相接關(guān)系的2個(gè)子側(cè)面，但實(shí)際上被劃分為3個(gè)子側(cè)面(如圖1(b)、圖1(c)所示)，其原因在于底面A拉伸后在點(diǎn)e對應(yīng)的頂面邊上產(chǎn)生了多余點(diǎn)k，側(cè)面上產(chǎn)生了多余邊km。文獻(xiàn)[11]和文獻(xiàn)[13]尚未解決該問題。

二、側(cè)面拓?fù)潢P(guān)系分析

上述拓?fù)鋯栴}主要體現(xiàn)在三維模型側(cè)面上，根據(jù)拉伸建模原理，側(cè)面不可能出現(xiàn)島、洞等情況，只能是規(guī)則的簡單多邊形。簡單多邊形存在8種拓?fù)潢P(guān)系[15-18]，但拉伸形成的三維模型側(cè)面之間只存在相離、相接、相交、覆蓋、覆蓋于、相等6種拓?fù)潢P(guān)系。以2個(gè)地物為例，具體表現(xiàn)形式有12種(如圖2所示)。

圖2　側(cè)面拓?fù)潢P(guān)系

其中，圖2(g)表示兩個(gè)側(cè)面存在相等關(guān)系，圖2(c)和圖2(l)、圖2(d)和圖2(k)、圖2(h)和圖2(j)盡管對稱，但因地物之間的高度及判斷目標(biāo)的先后順序不同，本文實(shí)現(xiàn)過程并不相同，因此將其列在圖2中。對于2個(gè)以上的地物，拉伸建模后可能出現(xiàn)一個(gè)三維模型側(cè)面與其他多個(gè)三維模型側(cè)面存在拓?fù)潢P(guān)系的情況，但也只是圖2各種情況的排列組合，本文每次只需考慮兩個(gè)側(cè)面即可。

三、基于點(diǎn)集的自動(dòng)拉伸建模方法

為解決上述問題，本文首先根據(jù)地物高度及其底面之間的拓?fù)潢P(guān)系，提取一系列點(diǎn)，然后基于這些點(diǎn)構(gòu)建三維模型的各個(gè)面，最終由這些面封閉構(gòu)成體。

1. 點(diǎn)集的提取

構(gòu)成三維模型的點(diǎn)集主要包括底面、頂面的結(jié)(節(jié))點(diǎn)及側(cè)面上與其他三維模型相關(guān)聯(lián)的點(diǎn)。

(1) 底面重合點(diǎn)的處理

要避免拉伸建模后產(chǎn)生重合點(diǎn)，首先必須對底面重合點(diǎn)進(jìn)行處理。重合點(diǎn)可以通過坐標(biāo)值是否相同進(jìn)行判斷，也可以通過點(diǎn)與點(diǎn)之間的拓?fù)潢P(guān)系進(jìn)行判斷，找出重合點(diǎn)之后，只需保留其中一個(gè)點(diǎn)即可。

(2) 底面及頂面非拐點(diǎn)的處理

當(dāng)節(jié)點(diǎn)關(guān)聯(lián)的兩條邊之間的夾角為180°，稱之為非拐點(diǎn)。非拐點(diǎn)是拉伸建模產(chǎn)生冗余基元的重要因素，主要表現(xiàn)為：①底面邊上的非拐點(diǎn)，但與其他底面沒有關(guān)聯(lián)關(guān)系，拉伸后導(dǎo)致頂面邊上也產(chǎn)生非拐點(diǎn)，如圖3中的點(diǎn)a，拉伸后頂面形成非拐點(diǎn)d，并在側(cè)面形成邊ad；②底面邊上的非拐點(diǎn)，與其他底面存在關(guān)聯(lián)關(guān)系，同時(shí)也是其他底面的非拐點(diǎn)，拉伸后導(dǎo)致兩個(gè)三維模型的頂面邊上都產(chǎn)生非拐點(diǎn)，如圖3中的點(diǎn)b，拉伸后在兩個(gè)頂面上分別形成非拐點(diǎn)e和f，并在側(cè)面形成邊be、ef；③較高三維模型底面上的非拐點(diǎn)，與其他底面存在關(guān)聯(lián)關(guān)系，但不是其他底面的非拐點(diǎn)，拉伸建模后在較高三維模型頂面形成非拐點(diǎn)，如圖3中的c點(diǎn)拉伸后在底面A對應(yīng)的三維模型頂面形成非拐點(diǎn)h。這些非拐點(diǎn)并不需要提取，主要通過與之相關(guān)聯(lián)的兩條邊之間的夾角是否為180°來判斷。

圖3　非拐點(diǎn)示意圖

(3) 頂面及側(cè)面點(diǎn)的提取

頂面點(diǎn)是指頂面輪廓邊上的點(diǎn)，側(cè)面點(diǎn)是指側(cè)面內(nèi)域及與底面垂直的側(cè)面邊上的點(diǎn)。對獨(dú)立地物而言，不存在側(cè)面點(diǎn)，構(gòu)建頂面點(diǎn)時(shí)，x、y坐標(biāo)值與對應(yīng)底面點(diǎn)相同，z坐標(biāo)在對應(yīng)底面點(diǎn)z坐標(biāo)值基礎(chǔ)上增加地物高度值即可。對與其他地物相鄰的地物而言，底面點(diǎn)與其他底面不存在關(guān)聯(lián)關(guān)系時(shí)，其對應(yīng)頂面點(diǎn)的構(gòu)建方法與獨(dú)立地物相同；底面點(diǎn)與多個(gè)底面相關(guān)聯(lián)時(shí)，則根據(jù)關(guān)聯(lián)底面的高度屬性從低到高排序，依次構(gòu)建側(cè)面點(diǎn)，其中當(dāng)多個(gè)關(guān)聯(lián)底面高度屬性值相等時(shí)，對應(yīng)只構(gòu)建一個(gè)側(cè)面點(diǎn)，各側(cè)面點(diǎn)x、y坐標(biāo)值與對應(yīng)底面點(diǎn)相同，z坐標(biāo)在對應(yīng)底面點(diǎn)z坐標(biāo)值基礎(chǔ)上增加各關(guān)聯(lián)底面高度屬性值即可。

(4) 拓?fù)湫畔⒋鎯?chǔ)

提取點(diǎn)集之后，需存儲(chǔ)各點(diǎn)與底面及底面點(diǎn)的對應(yīng)關(guān)系，為方便后續(xù)體的構(gòu)建，還需存儲(chǔ)各點(diǎn)的高程值及其排序。如圖4所示，具有同一底面關(guān)聯(lián)點(diǎn)的各點(diǎn)，可以通過高程值或高程排序判斷各點(diǎn)在Z方向上的連通關(guān)系；具有不同底面關(guān)聯(lián)點(diǎn)的各點(diǎn)(如點(diǎn)3、點(diǎn)4)，可以通過底面關(guān)聯(lián)點(diǎn)的排列序號及是否存在相同關(guān)聯(lián)底面來判斷在XY平面上是否存在連通關(guān)系等。

圖4　點(diǎn)的拓?fù)湫畔?/p>

2. 體的構(gòu)建

若不考慮側(cè)面拓?fù)潢P(guān)系，底面點(diǎn)數(shù)為n時(shí)，拉伸建立的三維模型由n+2個(gè)面組成，但實(shí)際如上文所述，當(dāng)?shù)匚锵噜彆r(shí)，某些側(cè)面將被分割為若干個(gè)子側(cè)面，組成三維模型的面數(shù)將大于n+2。因此，在體的構(gòu)建過程中，為保證側(cè)面拓?fù)潢P(guān)系的正確性，最重要就是通過以上點(diǎn)集構(gòu)建存儲(chǔ)拓?fù)湫畔⒌母鱾€(gè)面。

(1) 底面構(gòu)建

根據(jù)點(diǎn)集存儲(chǔ)的拓?fù)湫畔?，找到地物關(guān)聯(lián)的底面點(diǎn)，連接封閉即可。

(2) 頂面構(gòu)建

在點(diǎn)集中找到與底面點(diǎn)對應(yīng)且高度屬性值為地物高度的點(diǎn)，連接封閉即可。

(3) 側(cè)面構(gòu)建

根據(jù)上文分析可知，底面點(diǎn)在頂面上不一定有對應(yīng)的點(diǎn)，如圖5中點(diǎn)c，因此在構(gòu)建側(cè)面時(shí)，以頂面點(diǎn)為基準(zhǔn)，在兩個(gè)連通頂面點(diǎn)對應(yīng)的底面點(diǎn)之間尋找是否存在共享子側(cè)面，有則先構(gòu)建該共享子側(cè)面，再判斷這兩個(gè)連通頂面點(diǎn)與對應(yīng)底面點(diǎn)之間是否還存在非共享子側(cè)面，有則繼續(xù)構(gòu)建該非共享子側(cè)面。如圖5所示，連通頂面點(diǎn)B、g對應(yīng)的底面點(diǎn)A、d之間存在共享子側(cè)面，從點(diǎn)A開始尋找連通的底面點(diǎn)c，從點(diǎn)集中找到點(diǎn)A、c對應(yīng)的側(cè)面點(diǎn)a、b，由這4個(gè)點(diǎn)即可構(gòu)建共享子側(cè)面Aabc，構(gòu)建完成后接著構(gòu)建頂面點(diǎn)B、g與底面點(diǎn)A、d之間存在的非共享子側(cè)面aBgdcb，非共享子側(cè)面由共享子側(cè)面頂面點(diǎn)、不存在共享子側(cè)面的底面邊結(jié)點(diǎn)、連通頂面點(diǎn)共同構(gòu)成。

圖5　側(cè)面構(gòu)建圖示

(4) 體的構(gòu)建及拓?fù)湫畔⒋鎯?chǔ)

建立頂面、底面及側(cè)面后，為便于體的構(gòu)建及空間查詢與分析，需存儲(chǔ)各面的類型信息，并建立4種拓?fù)浠年P(guān)聯(lián)關(guān)系，其中，建立面-面、面-體、體-體的拓?fù)潢P(guān)系是以拉伸的方式建立保持正確拓?fù)潢P(guān)系的三維地物模型的基礎(chǔ)。文獻(xiàn)[5]和文獻(xiàn)[6]指出了體的拓?fù)潢P(guān)系構(gòu)建模型，由于拉伸建模形成的頂面、底面及側(cè)面都與底面點(diǎn)存在對應(yīng)關(guān)系，因此，本文提出的方法中各面都記錄了底面關(guān)聯(lián)點(diǎn)。這樣，通過底面關(guān)聯(lián)點(diǎn)就可以判斷各面之間的拓?fù)潢P(guān)系，如圖5所示，側(cè)面aBgdcb的底面關(guān)聯(lián)點(diǎn)為點(diǎn)A、c、d，側(cè)面Aabc的底面關(guān)聯(lián)點(diǎn)為A、c，根據(jù)上文的側(cè)面拓?fù)潢P(guān)系分析及兩個(gè)面的共享基元點(diǎn)，很容易判斷兩者是相接關(guān)系。此外，對于頂面、底面而言，記錄包含它們的歸屬體及與它們有共享拓?fù)浠年P(guān)聯(lián)體；對于非共享子側(cè)面而言，記錄包含它們的歸屬體；對于共享子側(cè)面而言，記錄包含它們的所有關(guān)聯(lián)體(如圖6所示)。通過這種存儲(chǔ)方式，為面/面、面/體、體/體之間的空間查詢與分析提供了便利，構(gòu)建體時(shí)只需根據(jù)以上存儲(chǔ)的拓?fù)湫畔⒄业较鄳?yīng)的頂面、底面及側(cè)面封閉即可。

圖6　面的拓?fù)湫畔?/p>

3. 試驗(yàn)與分析

本文基于VB.net+ArcGISEngine對以上方法進(jìn)行了試驗(yàn)，圖7(a)為某小區(qū)底面數(shù)據(jù)，提取點(diǎn)集后的結(jié)果如圖7(b)所示，最終提取點(diǎn)數(shù)為119個(gè)，而常見拉伸建模方法形成的點(diǎn)數(shù)為228個(gè)?；谔崛〉狞c(diǎn)集建立的三維模型如圖7(c)所示，該方法很好地解決了底面帶洞、島等復(fù)雜多邊形的建模問題。圖7(d)為ArcScene提供的Extrusion功能拉伸后的結(jié)果，將其與圖7(c)對比，二者內(nèi)部結(jié)構(gòu)不同(圖7(c)和(d)中底部區(qū)域)，本文建立的體模型結(jié)構(gòu)更加簡單。此外，如圖7(e)所示，本文提出的方法還可用于基于面的空間查詢與分析。

圖7　試驗(yàn)與分析

四、結(jié)束語

本文顧及三維模型的拓?fù)潢P(guān)系，提出了基于點(diǎn)集的自動(dòng)拉伸建模改進(jìn)方法，能夠改進(jìn)拉伸建模在拓?fù)浞矫娲嬖诘娜舾刹蛔?。相比常見的拉伸建模方法，該方法提取的點(diǎn)數(shù)較少，并且隨著地物底面多邊形數(shù)及拓?fù)潢P(guān)系復(fù)雜性的增加，點(diǎn)數(shù)的減少量還將大大增加，以此構(gòu)建的體的內(nèi)部結(jié)構(gòu)得到了簡化，并能提供面/面、面/體、體/體之間的空間查詢與分析。盡管如此，由于拉伸建模形成的三維模型還存在一些弱點(diǎn)[5]，對于側(cè)面為非規(guī)則多邊形、頂面非平行于底面的地物來說，如何建立保持其拓?fù)湟恢滦缘娜S模型還有待進(jìn)一步研究。

[1]鄧敏，李志林，李光強(qiáng). 簡單面目標(biāo)與帶孔洞面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法[J]. 測繪學(xué)報(bào)， 2008，37(3):330-337.

[2]詹陳勝，武芳，翟仁健，等. 基于拓?fù)湟恢滦缘木€目標(biāo)空間沖突檢測方法[J]. 測繪科學(xué)技術(shù)學(xué)報(bào)，2011，28(5):387-390.

[3]吳信才. 地理信息系統(tǒng)原理與方法[M]. 北京: 電子工業(yè)出版社, 2009: 48-51.

[4]鄧敏，馬杭英. 線與面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法[J]. 測繪學(xué)報(bào)，2008，37(4):507-513.

[5]郭仁忠，應(yīng)申，李霖. 基于面片集合的三維地籍產(chǎn)權(quán)體的拓?fù)渥詣?dòng)構(gòu)建[J]. 測繪學(xué)報(bào)，2012，41(4):620-626.

[6]李霖，趙志剛，郭仁忠，等. 空間體對象間三維拓?fù)錁?gòu)建研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2012，37(6):719-723.

[7]賀彪，李霖，郭仁忠，等. 顧及外拓?fù)涞漠悩?gòu)建筑三維拓?fù)渲亟╗J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2011，36(5):579-583.

[8]劉新，劉文寶，李成名. 三維體目標(biāo)間拓?fù)潢P(guān)系與方向關(guān)系的混合推理[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2010，35(1):74-78.

[9]鄧念東，侯恩科. 三維體元拓?fù)鋽?shù)據(jù)模型的修正及其形式化描述[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009，34(1):52-56.

[10]陳鵬，孟令奎，宋楊. 三維GIS中基于空間拓?fù)浼s束條件的R樹研究[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2007，32(4):347-349.

[11]LEDOUXH,MEIJERSM.TopologicallyConsistent3DCityModelsObtainedbyExtrusion[J].InternationalJournalofGeographicalInformationScience，2011, 25(4):557-574.

[12]TSEROC,DAKOWICZM,GoldCM,etal.BuildingReconstructionUsingLiDARData[C]∥Proceedingsof4thISPRSWorkshoponDynamicandMulti-dimensionalGIS.Pontypridd,Wales,UK：[s.n.], 2005：156-161.

[13]LEDOUXH,MEIJERSM.ExtrudingBuildingFootprintstoCreateTopologicallyConsistent3DCityModels[J].UrbanandRegionalDataManagement-UDMSAnnuals，2009(1): 39-48.

[14]ZLATANOVAS,RAHMANAA,SHIW.TopologicalModelsandFrameworksfor3DSpatialObjects[J].Computers&Geosciences, 2004(30):419-428.

[15]劉波，李大軍，鄒時(shí)林，等. 帶孔洞面域間的拓?fù)潢P(guān)系的組合推理[J]. 測繪學(xué)報(bào)，2011，40(2):262-267.

[16]沈敬偉，閭國年，溫永寧，等. 拓?fù)浜头较蚩臻g關(guān)系組合描述及其相互約束[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2011，36(11):1305-1308.

[17]汪西莉，覃婧嬋，曹菡，等. 基于SRC-Ontology的空間拓?fù)潢P(guān)系拓展表示方法及實(shí)現(xiàn)[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009，34(3):339-343.

[18]劉波，李大軍，阮見，等. 帶空洞面對象間拓?fù)潢P(guān)系形式化描述[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2009，34(1):68-71.

ImprovedExtrusionModelingMethodBasedonPointSet

YANGNai,JIAYue,SULilan,WANLin,YANGJie

2015-05-26

國家自然科學(xué)基金(41201474；41401449)

楊乃(1984—)，男，博士，講師，主要研究方向?yàn)槿S地圖可視化。E-mail：naigeer@163.com

P208

B

0494-0911(2016)05-0041-04

引文格式： 楊乃，賈躍，蘇黎蘭,等. 基于點(diǎn)集的拉伸建模改進(jìn)方法[J].測繪通報(bào)，2016(5)：41-44.DOI:10.13474/j.cnki.11-2246.2016.0151.