朱 杰，孫毅中

1. 南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023； 2. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

多約束的平面點集形狀重構(gòu)方法

朱 杰1,2，孫毅中1,2

1. 南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023； 2. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

針對平面點集空間分布的復雜性，本文提出了一種基于Delaunay三角網(wǎng)的平面點集形狀重構(gòu)方法。首先采用一種簡單且實用的數(shù)據(jù)結(jié)構(gòu)以表達Delaunay三角網(wǎng)中嵌入的幾何信息和拓撲信息，然后由外向內(nèi)迭代過濾Delaunay三角網(wǎng)得到一個大概邊界，最后進一步考慮邊界的凹凸信息和空洞現(xiàn)象，獲取最終的精細邊界。試驗結(jié)果表明與其他典型的Delaunay三角網(wǎng)重構(gòu)方法相比，本文提出的算法能更好地適用于平面點集空間分布的復雜性，通過所構(gòu)建的數(shù)學模型實現(xiàn)了凸凹多邊形內(nèi)外邊界提取。

平面點集；形狀重構(gòu)；Delaunay三角網(wǎng)；多約束；GIS

平面點集形狀重構(gòu)在GIS相關應用領域如地圖綜合[1-3]、建筑物輪廓線提取[4-6]、地理范圍確定[7-8]以及地理信息檢索(GIR)[9]中是一項重要而基礎的工作，旨在從一堆無序的點集(僅有坐標信息)中提取出平面點集的分布范圍，近似地表達真實的輪廓信息。如何考慮點集空間分布的復雜性是許多平面點集形狀重構(gòu)方法面臨的主要問題。通過對國內(nèi)外學者的研究分析，將這種復雜性歸納為以下4個方面：①點集的空間關系表達，包括幾何信息和拓撲信息；②空間密度分布不均；③局部凹凸信息的精確描述；④內(nèi)部空洞問題。此外，為更加精確地描述點集形狀輪廓信息，重構(gòu)過程中還需要顧及重構(gòu)結(jié)果的唯一性和規(guī)則性。

現(xiàn)有平面點集形狀重構(gòu)方法可以分為3類：①基于凸殼的方法；②基于Delaunay三角網(wǎng)的方法；③基于曲線重構(gòu)的方法?；谕箽さ姆椒╗10-12]大都采用凸殼內(nèi)縮的策略獲取邊界的凹凸特征，在一定情況下能夠處理空間密度分布不均的情況，但由于該算法缺少點集的拓撲信息，難以保證邊界的規(guī)則性，也無法識別空洞現(xiàn)象?；贒elaunay三角網(wǎng)的重構(gòu)過程可以分為兩步：①構(gòu)建Delaunay三角網(wǎng)；②基于圖形結(jié)構(gòu)特征提取一些幾何單元來近似地表達真實邊界情況。最早的這類重構(gòu)方法是Sculpture方法[13]和α-shapes方法[14]。Delaunay Sculpture是一種剝離三角網(wǎng)算法，由外向內(nèi)不斷刪除不規(guī)則的三角形直到產(chǎn)生一個符合條件的點集形狀。基于這種思想衍生了許多算法[15-18]，這些算法能夠提取任意形狀的點集，剝離規(guī)則也保證了最終邊界的規(guī)則性，但這些算法不夠穩(wěn)健，難以適應復雜的凹部和空洞現(xiàn)象，如χ-shape算法[16]通過迭代判斷Delaunay三角網(wǎng)邊界邊長，將滿足閾值的邊長保留作為最終的邊界提取結(jié)果，這種全局參數(shù)對密度分布不均的樣本數(shù)據(jù)重構(gòu)效果不是很穩(wěn)定，該算法也沒有考慮空洞問題；為克服全局度量受密度變化影響較大的缺陷，?RGG算法[18]采用了局部度量方式對三角網(wǎng)進行過濾，避免了算法的參數(shù)化，針對三角網(wǎng)中特定的結(jié)構(gòu)特征能夠有效識別空洞現(xiàn)象，但該算法對含有規(guī)則的凹邊界和狹長空洞是失效的。α-shapes算法類似Delaunay三角網(wǎng)，參數(shù)α控制了輪廓信息的含量,由于這個原因，需要不斷變化參數(shù)α值以得到理想的輪廓信息。但是，α-shapes不能準確地表達點集密度分布不均的情況。為了顧及局部密度信息,后期出現(xiàn)了若干α-shapes改進算法，如r-shape[19]、A-shapes[20]、LDA-α-complex[21]等，這些算法采用了局部度量和全局度量策略，能夠滿足平面點集分布不均、空洞等復雜情況，但是輸入?yún)?shù)過多?；谇€重構(gòu)的方法采用曲線擬合方法如泊松法[22]、最小二乘法[23]、徑向基函數(shù)法[24]估算點集的曲率，將滿足曲率閾值條件的點判定為邊界特征候選點，最后將這些邊界點連接即達到了邊界提取的目的。曲線重構(gòu)方法可以針對無規(guī)則的點云數(shù)據(jù)提取出精度較高的邊界點，但這種方法需要計算每一個數(shù)據(jù)點的曲率值，其計算過程非常復雜。

綜上分析，基于Delaunay三角網(wǎng)的平面點集重構(gòu)方法原理較簡單，其結(jié)構(gòu)能夠很好地彌補不規(guī)則點集的幾何信息和拓撲信息，較其他方法相對系統(tǒng)和穩(wěn)健。針對該方法存在的問題，本文基于Delaunay三角網(wǎng)提出了一種有效的平面點集重構(gòu)方法，首先采用一種局部度量方式對整個Delaunay三角網(wǎng)(凸殼)進行過濾得到初始邊界，然后通過構(gòu)建有效的數(shù)學模型實現(xiàn)凸凹多邊形內(nèi)外邊界提取。

1 理論基礎

1.1 數(shù)據(jù)結(jié)構(gòu)

Delaunay三角網(wǎng)中包含了3種實體要素：點、邊和三角形，本文采用了一種簡單且實用的數(shù)據(jù)結(jié)構(gòu)，即在Delaunay三角網(wǎng)中每個三角形記錄了其相應的三條邊，每條邊存儲了兩個端點信息，包括每個端點的坐標信息。此外，為了更有效地對邊界進行操作，每條邊還記錄了鄰近三角形信息，每個點存儲了鄰域邊信息。采用以上數(shù)據(jù)組織方式來表達Delaunay三角網(wǎng)中3種要素之間的拓撲信息對邊界搜索、提取以及拓撲檢查有著重要的作用。

1.2 相關定義

a. 懸掛邊、鏈式邊：它們不屬于任何一個三角形(圖1(a))。

b. 交叉點：每個邊界點由兩條邊界邊交匯而成，交叉點是兩條以上邊界邊的交點(圖1(a))。

圖1 邊界規(guī)則性示意圖Fig.1 Illustration of regular and non-regular boundary

(6) 空洞：從Delaunay三角網(wǎng)的結(jié)構(gòu)而言，空洞是一個封閉的凹部區(qū)域，即每個空洞由若干凹邊構(gòu)成而不存在可見邊界邊，從某種意義上而言，凹部和空洞具有相似的結(jié)構(gòu)特征。

2 算法過程

本文提出的算法是一種由外向內(nèi)有序過濾Delaunay三角網(wǎng)的過程。首先按照設定的數(shù)據(jù)結(jié)構(gòu)采用生長法[26]對平面點集構(gòu)建Delaunay三角網(wǎng)，將點群圍在一個凸殼內(nèi)，找出初始邊界；然后根據(jù)一種有序的篩選策略對初始邊界向內(nèi)過濾，得到一個大概邊界，過濾的過程中要保證邊界的規(guī)則性；最后進一步考慮邊界的凹凸信息和空洞現(xiàn)象，得到最終的準確邊界。算法可分為兩部分：粗邊界提取和精細邊界生成。

2.1 粗邊界提取

Delaunay三角網(wǎng)提供了3個參數(shù)：周長、角度和邊長。周長和邊長閾值都屬于全局度量方式，容易受密度變化的影響，角度作為一種局部度量方式要優(yōu)于周長和邊長。根據(jù)格式塔鄰近性原則[27]可知平面點集的邊界由點群外圍且距離相近的點連接而成，換言之，在一個邊界三角形中，如果邊界邊所對應的角度越大，則兩個邊界點之間的距離也就越大，兩個邊界點之間不符合鄰近性原則，應當刪除它們之間的連線(即邊界邊)。上述性質(zhì)能夠適應空間實體密度的變化，為此本文采用角度作為重構(gòu)參數(shù)。給定一個平面點集，設邊界邊為Be,邊界三角形中邊界邊所對應的角度表示為Angle(Be)，角度閾值為R，其粗邊界提取的具體流程如圖2所示。

圖2 粗邊界提取流程Fig.2 Rough boundary extraction flow chart

粗邊界提取過程采用了排序-過濾的策略，這是因為邊界處的幾何特征與內(nèi)部相比具有明顯的“不規(guī)則性”，排序的效果是為了過濾掉最不規(guī)則的元素，保證邊界提取結(jié)果的唯一性；另一方面粗邊界提取算法雖然在一定程度上能夠反映形狀輪廓的凹凸信息，但是無法識別復雜的凹部和空洞現(xiàn)象，需要進一步施加約束條件，生成精細邊界。

2.2 精細邊界生成

粗邊界提取過程采用了基于角度的過濾策略對以下兩種結(jié)構(gòu)是失效的。

(1) 含有規(guī)則三角形的凹部。如果凹部存在如圖3(a)所示的規(guī)則三角形時，其作為邊界三角形邊界邊所對應的角度很小，為刪除此邊界邊必須降低閾值R，但閾值過小，邊界會過度收縮，難以得到理想的重構(gòu)效果。如果無法刪除此邊界邊，勢必會阻礙凹部的進一步探測。

(2) 空洞。粗邊界提取是由外向內(nèi)過濾邊界邊的內(nèi)縮過程，由邊界邊的定義可知，空洞內(nèi)的邊(圖4(a))不屬于邊界邊，因此，空洞現(xiàn)象無法被識別。

圖3 含有規(guī)則三角形的凹部Fig.3 An example of cavity with regular triangle

圖4 空洞現(xiàn)象Fig.4 An example of a hole

在1.2節(jié)中指出凹部和空洞可以視為同一種結(jié)構(gòu)，它們通常位于較周邊密度稀疏的區(qū)域，采用Voronoi圖來表示這種密度變化，從圖3(b)和圖4(b)中可以看出凹部和空洞區(qū)域密度較小，其周邊區(qū)域的密度相對較高。選用密度變化來定義這兩種結(jié)構(gòu)的原因在于Delaunay三角網(wǎng)是一個帶有密度性質(zhì)的空間鄰近性模型，不需要任何參數(shù)設置，參數(shù)信息完全包含在三角網(wǎng)中。從圖3(a)和圖4(a)中可以看出，位于這兩種結(jié)構(gòu)的邊界點其鄰域內(nèi)連線長短不一，梯度變化較大。基于此，采用一個相對參數(shù)來量化這種特征，即通過判斷點的松散度來探測凹部和空洞，具體表達如下。

點的松散度：給定一個平面點集D，由點集生成的Delaunay三角網(wǎng)表示為DT。針對DT內(nèi)任一點實體P，F(xiàn)(P)表示點實體P的松散度，表示為

F(P)=Local_SD(P)/Local_Mean_Length(P)

(1)

(2)

Local_SD(P)=

(3)

F(P)值越小，說明該對象鄰域內(nèi)邊長梯度變化小。真實輪廓內(nèi)的點由于鄰域內(nèi)邊長變化較小，其F(P)值較小，相反，空洞和凹部處的邊界點F(P)值較大(圖3(c)和圖4(c))。因此，針對DT內(nèi)任一點實體P，凹部和空洞的松散度可以表達為

(4)

式中，Sets表示凹部和空洞的松散度集合；T表示松散度閾值。通過集合Sets可以找到空洞和凹部的邊界點，這些邊界點鄰域內(nèi)連線長短不一，如何篩選這些邊長是關鍵問題。從空間聚類的角度出發(fā)，松散度較大的主要原因在于長邊的存在，為刪除這些不合理的長邊，本文采用了AUTOCLUST算法[28]，其根據(jù)密度信息來探測長邊，具體表達如下。

長邊約束：給定一個平面點集D，由點集生成的Delaunay三角網(wǎng)表示為DT。針對DT內(nèi)任一點實體P，Longedge表示與P連接的所有邊的長邊約束條件，表示為

Longedge=Local_Mean_Length(P)+Global_SD

(5)

(6)

式中，Local_Mean_Length(P)表示P鄰域內(nèi)所有邊長的均值；Local_SD(Pi)表示點Pi鄰域內(nèi)所有邊長的標準差；Global_SD表示DT內(nèi)所有對象Local_SD(Pi)的平均值；N表示平面點集數(shù)目。

針對網(wǎng)內(nèi)任一點實體P，若與其直接相連接的邊的長度大于Longedge，則刪除該邊。對于保留下來的短邊可以調(diào)用粗邊界提取進行約束。基于此，精細邊界提取的具體過程如下。

(1) 在粗邊界提取的結(jié)果基礎上，計算整個點集的松散度并獲取集合Sets。

(2) 將Sets分為兩部分：邊界點的松散度和內(nèi)點松散度，如果點集同時存在凹部和空洞，凹部識別優(yōu)先于空洞，即邊界點遍歷優(yōu)先于內(nèi)點。

精細邊界的提取過程如圖5和圖6所示。

圖5 凹部識別流程Fig.5 Concave recognition flow chart

圖6 空洞識別流程Fig.6 Hole recognition flow chart

精細邊界提取過程中顧及了兩個順序，一是優(yōu)先級，凹部和空洞識別的優(yōu)先級，鄰域內(nèi)邊長和邊界邊的遍歷優(yōu)先級，優(yōu)先級能夠確保過濾掉最不規(guī)則的元素；另一個順序是遍歷順序，松散度遍歷和鄰域邊長遍歷都采用了降序排列，這確保了邊界提取的唯一性。

2.3 松散度閾值T的確定

(7)

目標函數(shù)通過探測過渡點將松散度劃分為兩部分，為達到二類分割的最佳效果即類內(nèi)方差最小或類間方差最大，引入PBM[29]指數(shù)來求解參數(shù)k。PBM指數(shù)作為一個相對評價指標能夠滿足緊密性與分離性的聚類準則，其具體表示為

(8)

(9)

式中，Nc表示簇的數(shù)量；Ni表示簇Ci中實體數(shù)量；vi表示簇i的質(zhì)心；Ei表示簇Ci的內(nèi)部距離(簇內(nèi)所有空間對象到其質(zhì)心的距離之和)；E1表示數(shù)據(jù)集只分為一類的聚類內(nèi)部距離；ENc表示數(shù)據(jù)集分為Nc個簇的聚類內(nèi)部距離；DNc表示空間簇間的分離度，其隨著Nc增大而增大，最大值為數(shù)據(jù)集中最遠兩個簇的質(zhì)心距離。PBM指數(shù)越大，則表示得到的聚類結(jié)果越可靠。

結(jié)合粗邊界和精細邊界提取過程，分別對含有規(guī)則三角形的凹部和空洞機進行識別。首先調(diào)用粗邊界提取流程對含有凹部或者空洞的Delaunay三角網(wǎng)(參考圖3(a)和4(a))進行過濾，其結(jié)果如圖7(a)和圖8(a)所示；在粗邊界提取的基礎上調(diào)用精細邊界提取流程，通過PBM指數(shù)確定松散度閾值T(參考圖7(d)—(e)和圖8(d)—(e))以此找到位于凹部或者空洞處的邊界點(圖7(b)和圖8(b))，篩選邊界點的鄰域邊從而得到最終的邊界(圖7(c)和圖8(c))。

圖7 含有規(guī)則三角形的凹部識別過程Fig.7 Different stages of the proposed algorithm for cavity detection

圖8 空洞的識別過程Fig.8 Different stages of the proposed algorithm for hole detection

3 試驗分析

3.1 參數(shù)R的選擇

粗邊界和精細邊界的生成過程中，角度閾值R是邊界收斂的重要約束條件。平面點集存在兩種形式：一是含有空洞和凹部的點集，另一個是不含有以上兩種現(xiàn)象的點集。針對不含有空洞和凹部的點集，Delaunay三角網(wǎng)內(nèi)的三角形近似等邊三角形，此類點集的凸殼邊界即為理想的邊界收斂結(jié)果。對于含有空洞和凹部的點集，需要深入討論角度閾值R對此類點集邊界收斂的作用過程，為此，本文設計了幾組模擬試驗來評價參數(shù)R對重構(gòu)結(jié)果的精度影響，以獲取合適的參數(shù)取值范圍為用戶在參數(shù)R選擇方面提供參考。模擬試驗采用既定的形狀和點集分布類型，L2誤差范數(shù)[16]作為重構(gòu)結(jié)果的精度評價方法，其具體表達為

(10)

式中，O代表原始多邊形；S代表重構(gòu)結(jié)果。L2誤差范數(shù)通過原始多邊形與重構(gòu)結(jié)果的面積比例大小評價重構(gòu)效果，L2誤差范數(shù)等于0，則表示重構(gòu)結(jié)果與原始多邊形邊界完全吻合。

如果只看老師的評語，肯定是扁平片面的。通過創(chuàng)新的他評形式，看到了很多人生活中學習上為人上的更全面更真實的一面，看到了很多人在為人處世上的成長改變，看到了他們的朋友圈人緣，看到了他們的真心真意。

模擬實驗采用了5組形狀數(shù)據(jù)：云南、內(nèi)蒙古、F字(宋體)、K字(宋體)和A字(宋體)，5組形狀數(shù)據(jù)邊界具有明顯的不規(guī)則性，包含了大量的凹部和空洞；考慮到點集分布類型(如隨機分布)有可能使點集內(nèi)部產(chǎn)生空洞現(xiàn)象，因此點集分布類型選擇均勻分布；每組形狀數(shù)據(jù)內(nèi)部生成的點集數(shù)目確保能夠覆蓋到形狀邊界，模擬實驗采用的點集數(shù)目分別是70、100、130和160，代表了不同的點集密度。由角度參數(shù)的內(nèi)涵可知閾值R的取值范圍在[0,180](試驗取值間隔為10)，圖11顯示了基于參數(shù)R每組形狀數(shù)據(jù)邊界收斂的L2誤差范數(shù)變化曲線，5組數(shù)據(jù)的邊界收斂過程大體相似這主要是因為空洞和凹部是等價的結(jié)構(gòu)；另外，每組數(shù)據(jù)的邊界收斂過程并沒有隨點集密度變化而發(fā)生改變。當R取值180時粗邊界中Delaunay三角網(wǎng)沒有邊被刪除(如圖9所示)，網(wǎng)內(nèi)存在大量的“不規(guī)則”長邊，此時精細邊界中的松散度閾值T也較高(如圖10所示)，只能刪除部分不規(guī)則長邊，無法徹底識別凹部或者空洞，邊界收斂效果不理想，表現(xiàn)為L2誤差范數(shù)值較高(如圖11(b)所示)；當R取值0時，網(wǎng)內(nèi)的邊本該全部刪除，但是由于受到邊界規(guī)則性的約束邊界邊不能存在懸掛邊、鏈式邊和交叉點，保留下來的邊界呈“鋸齒狀”，如圖9和10所示，邊界收斂效果同樣不理想，L2誤差范數(shù)值較高，如圖11(b)所示，因此要想獲得理想的邊界收斂效果R的取值范圍應該是0

圖9 粗邊界提取過程Fig.9 Rough boundary extraction process

圖10 精細邊界提取過程Fig.10 Refined boundary extraction process

圖11 邊界收斂的精度變化Fig.11 Precision variation of boundary convergence

結(jié)合模擬試驗的邊界收斂過程和圖11中不同點集密度邊界收斂的L2誤差范數(shù)變化過程可以得出，角度閾值R取值范圍在[80,120]內(nèi)就含有空洞和凹部的點集而言可以取得理想的邊界收斂結(jié)果。

3.2 試驗結(jié)果對比

為了驗證本文方法的有效性與優(yōu)勢性，將提出的方法與其他兩種基于Delaunay三角網(wǎng)的典型方法χ-shape和?RGG算法進行比較分析，試驗內(nèi)容主要包含以下幾個方面：

3.2.1 非均勻分布

圖12分別顯示了在平面點集分布不均情況下3種方法的邊界提取結(jié)果。χ-shape算法由于采用邊長閾值作為度量參數(shù)，當點集分布不均時邊界提取效果不是很穩(wěn)定，會產(chǎn)生大塊的鋸齒現(xiàn)象；?RGG算法和本文方法都采用了局部度量參數(shù)(三角形外接圓心和角度)能夠獲取合理的重構(gòu)結(jié)果；另外，平面點集形狀重構(gòu)本質(zhì)上屬于不確定性問題，即合理的重構(gòu)結(jié)果并不唯一。雖然?RGG是一種自動構(gòu)建形狀輪廓的方法，不需要任何參數(shù)，但從不確定性角度而言，本文提出的方法能夠產(chǎn)生若干合理的重構(gòu)結(jié)果，提供了更多的重構(gòu)細節(jié)。

3.2.2 含有規(guī)則三角形的凹部

3.2.3 空洞現(xiàn)象

圖14分別顯示了3種方法對空洞現(xiàn)象的處理結(jié)果。χ-shape算法無法識別空洞；?RGG算法針對三角網(wǎng)的結(jié)構(gòu)可以對空洞現(xiàn)象構(gòu)造邊界，但它無法識別狹長的空洞現(xiàn)象；本文方法能夠識別多樣的空洞現(xiàn)象，包括狹長空洞(圖14)和球狀空洞(圖8)。

3.2.4 噪聲和非連通區(qū)域

3種方法的重構(gòu)結(jié)果都包含了平面點集中所有點包括噪聲，若要解決噪聲問題可以采用空間聚類的方法如AMOEA算法[30]對平面點集進行預處理，剔除噪聲；在一些實例中，有些點集是非連通區(qū)域如“i”或者“=”,考慮到邊界的規(guī)則性，三種方法同樣不能生成非連通區(qū)域。

圖12 針對點集分布不均χ-shape(綠色)、?RGG(藍色)和本文方法(白色)邊界提取結(jié)果的定性比較Fig.12 Qualitative comparison of χ-shape (in green)) and ?RGG(in cyan)) with the proposed algorithm (in black boundary) for non-uniform point set

圖13 針對含有規(guī)則三角形的凹部χ-shape(綠色)、?RGG(藍色)和本文方法(白色)邊界提取結(jié)果的定性比較Fig.13 Qualitative comparison of χ-shape (in green)) and ?RGG(in cyan)) with the proposed algorithm (in black boundary) for Cavities with regular triangles

3.3 應用實例

本節(jié)將引入兩個應用實例來驗證本文方法的實用性，以發(fā)現(xiàn)平面點集重構(gòu)方法在不同領域內(nèi)的應用潛力。城市輪廓是城市空間形態(tài)分析中一個重要的組成部分，本文基于POI數(shù)據(jù)利用提出的方法提取城市輪廓線。圖15(a)顯示了洛陽市地名地址POI數(shù)據(jù)(灰色部分)，由于城市輪廓線表達的是一個城市的大概分布范圍，因此這里采用粗邊界提取方法和凹部識別算法，不需要構(gòu)造城市內(nèi)部的邊界。圖15(a)給出了洛陽市城市輪廓提取結(jié)果(黑色曲線)，將提取的城市輪廓線與洛陽市遙感影像圖(圖15(b))疊加比較，結(jié)果如圖15(c)所示，紅色曲線代表洛陽市遙感影像邊界線，黑色曲線代表輪廓提取結(jié)果，二者邊界線有很高的吻合度。

圖15 洛陽城市輪廓提取結(jié)果及對比Fig.15 The urban contour of Luoyang generated by our algorithm and comparison result

另一個實例是基于LIDAR數(shù)據(jù)的建筑輪廓線提取，數(shù)據(jù)來源于文獻[31]給出的馬來西亞吉隆坡城市中心區(qū)各類不同幾何形狀的建筑，基于本文方法提取的各種形狀建筑輪廓線結(jié)果(如圖16所示)與文獻[31]的提取結(jié)果相似，這表明提出的方法可適用于凸凹多邊形內(nèi)外邊界提取。

圖16 各種形狀建筑輪廓線提取結(jié)果Fig.16 The extracting results of different building boundary with our algorithm

4 結(jié) 論

本文提出了一種多約束的平面點集形狀重構(gòu)方法，相比已有方法，該方法能夠更好地適應平面點集空間分布的復雜性。通過模擬試驗和應用實例可以發(fā)現(xiàn)：①本文方法可以適應空間密度分布不均、凹凸信息精確描述、內(nèi)部空洞等復雜情況下的平面點集形狀重構(gòu)；②需要的輸入?yún)?shù)只有一個且在試驗部分中給出了指導信息，方便用戶實際使用；③重構(gòu)過程中對平面點集中存在的凹部和空洞給出了一種有效的數(shù)學描述以及識別方法，具有較強的理論保證。進一步改進的方面有：實驗分析中缺少對算法自身的定量分析包括點集密度變化和點集分布類型的適應性分析；在應用領域中還局限在二維平面中，后期進一步考慮拓展到三維空間中。

[1] 艾廷華, 劉耀林. 保持空間分布特征的群點化簡方法[J]. 測繪學報, 2002, 31(2): 175-181. AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.

[2] GALTON A,DUCKHAM M.What is the Region Occupied by a Set of Points?[M]∥RAUBAL M, MILLER H J, FRANK A U, et al. Geographic Information Science. Berlin Heidelberg: Springer, 2006: 81-98.

[3] 李佳田,康順,羅富麗.利用層次Voronoi圖進行點群綜合[J]. 測繪學報, 2014, 43(12): 1300-1306. DOI: 10.13485/j.cnki.11-2089.2014.0166. LI Jiatian, KANG Shun, LUO Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1300-1306. DOI: 10.13485/j.cnki.11-2089.2014.0166.

[4] ZHU Chao, ZHANG Xiaopeng, HU Baogang, et al. Reconstruction of Tree Crown Shape from Scanned Data[M]∥PAN Zhigeng, ZHANG Xiaopeng, RHALIBI A E, et al. Technologies for E-learning and Digital Entertainment. Berlin Heidelberg: Springer, 2008: 745-756.

[5] 孫穎, 張新長, 康停軍, 等. 改進GAC模型在點云和影像自動提取建筑物邊界中的應用[J]. 測繪學報, 2013, 42(3): 337-343, 350. SUN Ying, ZHANG Xinchang, KANG Tingjun, et al. Improved GAC Model for Automatic Building Extraction from LiDAR Point Clouds and Aerial Image[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 337-343, 350.

[6] 孫穎, 張新長, 羅國瑋. 從機載激光雷達點云提取建筑物屋頂邊界的活動輪廓模型改進方法[J]. 測繪學報, 2014, 43(6): 620-626, 636. DOI: 10.13485/j.cnki.11-2089.2014.0106. SUN Ying, ZHANG Xinchang, LUO Guowei. Improved Active Contour Model for Building Roof Boundary Extraction from LiDAR Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(6): 620-626, 636. DOI: 10.13485/j.cnki.11-2089.2014.0106.

[7] KISILEVICH S, MANSMANN F, BAK P, et al. Where Would You Go on Your Next Vacation? A Framework for Visual Exploration of Attractive Places[C]∥Proceedings of 2010 Second International Conference on Advanced Geographic Information Systems, Applications, and Services(GEOPROCESSING). St. Maarten: IEEE, 2010: 21-26.

[8] HU Yingjie,GAO Song, JANOWICZ K, et al. Extracting and Understanding Urban Areas of Interest Using Geotagged Photos[J]. Computers, Environment and Urban Systems, 2015, 54: 240-254.

[9] LIU Yu, YUAN Yihong, XIAO Danqing, et al. A Point-set-based Approximation for Areal Objects: A Case Study of Representing Localities[J]. Computers, Environment and Urban Systems, 2010, 34(1): 28-39.

[10] SAMPATH A,SHAN Jie. Building Boundary Tracing and Regularization from Airborne LiDAR Point Clouds[J]. Photogrammetric Engineering & Remote Sensing, 2007, 73(7): 805-812.

[11] 程效軍, 何桂珍. 適用于多值曲面修復的空洞邊界提取方法及應用[J]. 測繪學報, 2012, 41(6): 831-837. CHENG Xiaojun, HE Guizhen. The Method and Application of Hole Boundary Extraction for Multi-valued Surface Repair[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(6): 831-837.

[12] 李雯靜, 李少寧, 邱佳, 等. 凸殼內(nèi)縮法進行多密度離散點群邊界檢測[J]. 測繪科學, 2014, 39(9): 126-129. LI Wenjing, LI Shaoning, QIU Jia, et al. Boundary Detection of Multi-density Point Cluster Using Convex Hull Retracted Method[J]. Science of Surveying and Mapping, 2014, 39(9): 126-129.

[13] BOISSONNAT J D. Geometric Structures for Three-dimensional Shape Representation[J]. ACM Transactions on Graphics (TOG), 1984, 3(4): 266-286.

[14] EDELSBRUNNER H, KIRKPATRICK D, SEIDEL R. On the Shape of a Set of Points in the Plane[J]. IEEE Transactions on Information Theory, 1983, 29(4): 551-559.

[15] KOLINGEROVI, ?ALIK B. Reconstructing Domain Boundaries Within A Given Set of Points, Using Delaunay Triangulation[J]. Computers & Geosciences, 2006, 32(9): 1310-1319.

[16] DUCKHAM M,KULIK L,WORBOYS M, et al. Efficient Generation of Simple Polygons for Characterizing the Shape of a Set of Points in the Plane[J]. Pattern Recognition, 2008, 41(10): 3224-3236.

[17] 黃先鋒, 程曉光, 張帆, 等. 基于邊長比約束的離散點準確邊界追蹤算法[J]. 武漢大學學報(信息科學版), 2009, 34(6): 688-691. HUANG Xianfeng, CHENG Xiaoguang, ZHANG Fan, et al. Boundary Tracing from Irregular Points Based on Ratio of Edge Length[J]. Geomatics and Information Science of Wuhan University, 2009, 34(6): 688-691.

[18] PEETHAMBARAN J, MUTHUGANAPATHY R. A Non-parametric Approach to Shape Reconstruction from Planar Point Sets Through Delaunay Filtering[J]. Computer-Aided Design, 2015, 62: 164-175.

[19] CHAUDHURI A R, CHAUDHURI B B, PARUI S K. A Novel Approach to Computation of the Shape of A Dot Pattern and Extraction of Its Perceptual Border[J]. Computer Vision and Image Understanding, 1997, 68(3): 257-275.

[20] MELKEMI M, DJEBALI M. Computing the Shape of A Planar Points Set[J]. Pattern Recognition, 2000, 33(9): 1423-1436.

[21] CHEVALLIER N, MAILLOT Y. Boundary of a Non-uniform Point Cloud for Reconstruction: Extended Abstract[C]∥Proceedings of the 27th Annual ACM Symposium on Computational Geometry. New York: ACM, 2011: 510-518.

[22] KAZHDAN M, HOPPE H. Screened Poisson Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(3): 29.

[23] 顧天奇, 張雷, 冀世軍, 等. 封閉離散點的曲線擬合方法[J]. 吉林大學學報(工學版), 2015, 45(2): 437-441. GU Tianqi, ZHANG Lei, JI Shijun, et al. Curve Fitting Method for Closed Discrete Points[J]. Journal of Jilin University(Engineering and Technology Edition), 2015, 45(2): 437-441.

[24] MERRY B, GAIN J, MARAIS P. Moving Least-squares Reconstruction of Large Models with GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(2): 249-261.

[25] MISTRY S,NIRANJAN U N, GOPI M. Puzzhull: Cavity and Protrusion Hierarchy to Fit Conformal Polygons[J]. Computer-Aided Design, 2014, 46: 233-238.

[26] 武曉波, 王世新, 肖春生. Delaunay三角網(wǎng)的生成算法研究[J]. 測繪學報, 1999, 28(1): 28-35. WU Xiaobo, WANG Shixin, XIAO Chunsheng. A New Study of Delaunay Triangulation Creation[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(1): 28-35.

[27] 艾廷華, 郭仁忠. 基于格式塔識別原則挖掘空間分布模式[J]. 測繪學報, 2007, 36(3): 302-308. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining Based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3): 302-308.

[28] ESTIVILL-CASTRO V,LEE I.Argument Free Clustering for Large Spatial Point-data Sets Via Boundary Extraction from Delaunay Diagram[J]. Computers, Environment and Urban Systems, 2002, 26(4): 315-334.

[29] PAKHIRA M K, BANDYOPADHYAY S, MAULIK U. Validity Index for Crisp and Fuzzy Clusters[J]. Pattern Recognition, 2004, 37(3): 487-501.

[30] ESTIVILL-CASTRO V,LEE I. Multi-level Clustering and Its Visualization for Exploratory Spatial Analysis[J]. GeoInformatica, 2002, 6(2): 123-152.

[31] 沈蔚, 李京, 陳云浩, 等. 基于LiDAR數(shù)據(jù)的建筑輪廓線提取及規(guī)則化算法研究[J]. 遙感學報, 2008, 12(5): 692-698. SHEN Wei, LI Jing, CHEN Yunhao, et al. Algorithms Study of Building Boundary Extraction and Normalization Based on LIDAR Data[J]. Journal of Remote Sensing, 2008, 12(5): 692-698.

(責任編輯：陳品馨)

An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints

ZHU Jie1,2，SUN Yizhong1,2

1. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing Normal University, Nanjing 210023,China; 2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China

An efficient algorithm to boundary representation from a planar point set in order to adapt the complexity of spatial distribution was presented in this paper. At first, an appropriate and practical data structure was designed to express geometric information and topological information, which provides an easy access to links embedded in DT serving as a basis for the filtering procedures; then the algorithm generates rough boundary based on an iterative removal of Delaunay triangulation. Furthermore, a mathematic formulation for cavities and holes was given and a statistical method to detect them was designed. Finally, a series of experiments including both simulated and real data sets to validate the effectiveness and practicability of our algorithm was conducted.

planar point set; shape reconstruction; Delaunay triangulation; multi-constraints; GIS

The National Natural Science Foundation of China (No.41671392); Special Program for basic research of Sci-tech Police of Ministry of Public Security (No.2015GABJC39)

ZHU Jie(1989—), male, PhD candidate, majors in city spatial data representation and mining.

SUN Yizhong

朱杰，孫毅中.多約束的平面點集形狀重構(gòu)方法[J].測繪學報，2017,46(2)：253-264.

10.11947/j.AGCS.2017.20160122. ZHU Jie，SUN Yizhong.An Efficient Approach to Shape Reconstruction from Planar Point Set Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica,2017,46(2):253-264. DOI:10.11947/j.AGCS.2017.20160122.

P208

A

1001-1595(2017)02-0253-12

國家自然科學基金(41671392)；公安部科技強警基礎工作專項(2015GABJC39)

2016-03-30

朱杰(1989—)，男，博士生，研究方向為城市空間數(shù)據(jù)表達與挖掘。

E-mail： Chu_Je@163.com

孫毅中

E-mail： sunyizhong_cz@163.com

修回日期： 2016-10-27