江 威,吳 艷 蘭,譚 樹 東,馬 藝 文

(1.武漢市測(cè)繪研究院，湖北 武漢 430022；2.安徽大學(xué)資源與環(huán)境工程學(xué)院，安徽 合肥 230601；3.國(guó)家海洋信息中心，天津300171；4.武漢市國(guó)土資源和規(guī)劃信息中心，湖北 武漢 430014)

?

一種多發(fā)生元Voronoi圖的柵格生成方法

江 威1,吳 艷 蘭2*,譚 樹 東3,馬 藝 文4

(1.武漢市測(cè)繪研究院，湖北 武漢 430022；2.安徽大學(xué)資源與環(huán)境工程學(xué)院，安徽 合肥 230601；3.國(guó)家海洋信息中心，天津300171；4.武漢市國(guó)土資源和規(guī)劃信息中心，湖北 武漢 430014)

利用距離變換和柵格疊加分析，提出一種實(shí)現(xiàn)任意距離定義的2-site Voronoi圖生成方法。首先進(jìn)行距離變換得到距離圖，然后通過鄰近關(guān)系對(duì)邊界進(jìn)行劃分得到2-site Voronoi圖，最后將生成的距離圖和2-site Voronoi圖疊加。實(shí)驗(yàn)表明，該文提出的2-site Voronoi圖生成方法可以快速構(gòu)建多種距離類型和不同鄰近關(guān)系下的Voronoi圖，共生成了21種距離函數(shù)下的最遠(yuǎn)、最鄰近和次鄰近Voronoi圖，解決了Voronoi圖的多樣性問題。該方法并不局限于點(diǎn)狀發(fā)生元，可以生成任意形態(tài)發(fā)生元Voronoi圖，并可以擴(kuò)展生成N-site Voronoi圖，生成的廣義距離圖可用來模擬成組的發(fā)生元在諸多約束條件下的區(qū)域增長(zhǎng)過程。

距離函數(shù)；Voronoi圖；距離變換；生長(zhǎng)模型

0 引言

Voronoi圖(簡(jiǎn)稱V圖)因其在空間鄰接和空間分割中的獨(dú)特性質(zhì)，被廣泛應(yīng)用于計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人路徑規(guī)劃、模式識(shí)別等領(lǐng)域，也是計(jì)算幾何的一個(gè)重要研究?jī)?nèi)容。影響V圖外觀和屬性的要素有發(fā)生元、距離類型和空間類型,其中，距離類型由空間類型決定。常規(guī)V圖是由平面上n個(gè)發(fā)生元通過其歐氏距離最近空間點(diǎn)把平面劃分成n個(gè)獨(dú)立區(qū)域，其發(fā)生元是一組點(diǎn)集，每個(gè)Voronoi區(qū)域只包含一個(gè)點(diǎn)發(fā)生元，但這種V圖并不適用于發(fā)生元具有預(yù)先分組信息的場(chǎng)合。本文引用文獻(xiàn)[1]中的術(shù)語將常規(guī)V圖稱為1-site V圖；類似地，將發(fā)生元具有預(yù)先分組信息的V圖稱為N-site V圖，其主要外觀特征是每個(gè)Voronoi區(qū)域?qū)?yīng)著一組點(diǎn)發(fā)生元而不是某個(gè)發(fā)生元。與單發(fā)生元V圖相比，多發(fā)生元V圖除在發(fā)生元的形態(tài)和數(shù)量上不同之外，其距離定義也不同。單發(fā)生元V圖中的距離值是每個(gè)像元到其最近單發(fā)生元的距離，而多發(fā)生元V圖的距離含義由距離函數(shù)決定，如距離和函數(shù)對(duì)應(yīng)于空間每個(gè)像元到多個(gè)發(fā)生元的距離和，此時(shí)的距離是由多個(gè)發(fā)生元共同決定的。

目前對(duì)于單發(fā)生元V圖已有廣泛研究[2,3],對(duì)于多發(fā)生元V圖的研究則較少，并且主要研究了2-site V圖，即成對(duì)發(fā)生元V圖。點(diǎn)發(fā)生元成組之后會(huì)產(chǎn)生許多距離類型，因此與常規(guī)V圖相比，2-site V圖有更多的變形體。目前對(duì)于2-site V圖的研究，主要是從理論上探討不同距離類型對(duì)應(yīng)的2-site V圖的復(fù)雜度。Barequet定義的2-site的距離函數(shù)包括距離和、距離差、距離乘積、三角形面積等，并利用矢量生成方法中的分治法有效生成了對(duì)應(yīng)的V圖。但對(duì)于更復(fù)雜的距離函數(shù)，如這3個(gè)點(diǎn)組成的三角形的周長(zhǎng)，其2-site V圖有待進(jìn)一步研究。對(duì)此，Hanniel證明了距離函數(shù)為三角形周長(zhǎng)的2-site V圖的計(jì)算復(fù)雜度為O(n2+ε)(ε>0)[4]。Dickerson等提出一個(gè)統(tǒng)一的模型形象地描述各種2-site V圖，如距離和函數(shù)和三角形周長(zhǎng)對(duì)應(yīng)的V圖，但沒有介紹構(gòu)建每個(gè)V圖的方法[5]。最近，人們提出一些新的2-site距離函數(shù)的變形。例如，文獻(xiàn)[6，7]提出“視角”函數(shù)，文獻(xiàn)[7]還提出一些基于圓的距離函數(shù)(如3個(gè)點(diǎn)外接圓的半徑)。Vyatkina等進(jìn)一步研究了平面上曼哈頓距離和切比雪夫距離下的2-site V的復(fù)雜度，并可以擴(kuò)展到閔可夫斯基距離度量和更高維的空間[8]。Dickerson等利用2-site V圖，根據(jù)鄰近關(guān)系，給地理網(wǎng)絡(luò)圖中的點(diǎn)加了標(biāo)注[9]。

2-site V圖具有很強(qiáng)的趣味性和特殊性。在生成方法上，Barequet等利用矢量方法中的分治法生成2-site V圖，但存在算法復(fù)雜等矢量方法固有的缺點(diǎn)，此外，其距離函數(shù)主要是算術(shù)距離和幾何距離(即三角形面積和三角形周長(zhǎng))，不具有靈活性。對(duì)于任意距離函數(shù)的2-site V圖，這種基于矢量的生成方法并不實(shí)用，目前缺乏適用于任意距離函數(shù)的2-site V圖的生成方法。本文利用距離變換和柵格疊加分析，提出一種實(shí)現(xiàn)任意距離定義的2-site V圖生成方法，并將其擴(kuò)展為適用于任意形態(tài)發(fā)生元、任意預(yù)先分組的多發(fā)生元V圖。

1 方法原理

生成V圖，最重要的就是進(jìn)行距離變換，也就是模擬發(fā)生元的區(qū)域增長(zhǎng)過程。類似的，生成2-site V圖，首先也是進(jìn)行距離變換得到距離圖，由于此時(shí)控制距離尺度的距離函數(shù)有多種，就會(huì)得到多種擴(kuò)展的距離圖；然后，通過鄰近關(guān)系對(duì)邊界進(jìn)行劃分，從而得到2-site V圖；最后將生成的距離圖和2-site V圖疊加，就得到了最終用來模擬區(qū)域增長(zhǎng)過程的V圖。本文利用距離變換和柵格疊加，提出一種2-site V圖的生成方法，關(guān)鍵步驟為：1)由每個(gè)發(fā)生元分別生成距離圖，稱為單發(fā)生元距離圖(記為1-site距離圖)；2)對(duì)每對(duì)發(fā)生元，將其對(duì)應(yīng)的兩個(gè)1-site 距離圖通過柵格疊加生成新的距離圖，稱為單對(duì)發(fā)生元距離圖(記為1-pair-site距離圖)，代表該距離圖中只有一對(duì)發(fā)生元；3)對(duì)于包含多對(duì)的一組發(fā)生元，再次通過柵格疊加運(yùn)算，將其對(duì)應(yīng)的單對(duì)距離圖合成為多對(duì)發(fā)生元距離圖(記為N-pair-site距離圖)；4)由N-pair-site 距離圖得到對(duì)應(yīng)的2-site V圖。

值得說明的是：步驟2中柵格疊加對(duì)應(yīng)的疊加算子為距離函數(shù)，步驟3中柵格疊加對(duì)應(yīng)的疊加算子與步驟2不同，可定義為最小值(或最大值)函數(shù)，由此得到多對(duì)發(fā)生元的最近(或最遠(yuǎn))距離圖。為便于描述，將步驟2和步驟3中的柵格疊加分別稱為第一次柵格疊加和第二次柵格疊加。本文利用ArcObjects開發(fā)了一個(gè)構(gòu)建2-site V圖和N-site V圖的實(shí)驗(yàn)程序(圖1),可快速實(shí)現(xiàn)歐氏距離變換、柵格疊加(兩次)和V圖可視化。

圖1 2-site V圖生成流程

Fig.1 Flow chart of generation of 2-site V diagram

1.1 任意距離類型的單對(duì)發(fā)生元距離圖

單個(gè)發(fā)生元在平面上的增長(zhǎng)過程可用圍繞發(fā)生元的同心等距線的1-site距離圖直觀表示。對(duì)于2-site V圖，由于區(qū)域增長(zhǎng)過程中有兩個(gè)中心，因而其等距線圖的形狀更復(fù)雜。Barequet等基于矢量方法，利用膨脹的同心橢圓和同心帶等形狀的等距線，生成了前文提到的幾種距離函數(shù)對(duì)應(yīng)的V圖[2],但在其后來的文章里提到的更加復(fù)雜的距離函數(shù)，其等距線圖很難用矢量的方法生成[5]。通過對(duì)1-site距離圖的分析，并結(jié)合距離變換和柵格疊加的特點(diǎn)，可在圖上直觀地表示平面上的一對(duì)發(fā)生元的區(qū)域增長(zhǎng)過程。與常規(guī)距離圖相比，1-pair-site距離圖是由一對(duì)發(fā)生元生成，因此每個(gè)像元值為像元到這對(duì)發(fā)生元的距離，而不是像元到一個(gè)發(fā)生元的距離。通過第一次柵格疊加可生成1-pair-site距離圖。

如圖2所示，p和q為空間上任意兩點(diǎn)，其分別生成了1-site距離圖。因此任意空間點(diǎn)v到點(diǎn)p和q的距離可通過查詢這兩個(gè)1-site距離圖中的像元值獲取。在此基礎(chǔ)上，用不同的距離函數(shù)作為疊加算子，將兩個(gè)1-site距離圖中的像元值疊加，可生成一個(gè)新的距離圖，即1-pair-site距離圖。由于疊加算子由距離函數(shù)控制，疊加算子不同會(huì)直接影響1-pair-site距離圖的外觀和性質(zhì)。因此，構(gòu)建不同距離函數(shù)下的2-site V圖，在第一次柵格疊加時(shí)，要使用對(duì)應(yīng)的距離函數(shù)作為疊加算子。例如，加、減、乘算子可用來生成距離函數(shù)分別為和、差、乘積的1-pair-site距離圖，并最終生成2-site V圖。圖2a為1-site 距離圖的生成說明，疊加算子使用的是3×3窗口，并用不同距離函數(shù)指定的疊加算子生成各類1-pair-site距離圖；圖2b為一對(duì)點(diǎn)發(fā)生元p和q利用不同的疊加算子生成1-pair-site距離圖的實(shí)例。

圖2 1-pair-site距離圖的生成

Fig.2 Generation of 1-pair-site DM

1.2 任意鄰近關(guān)系的多對(duì)發(fā)生元距離圖

與1-pair-site距離圖類似，N-pair-site距離圖是一種新的距離圖，用來模擬平面上N個(gè)點(diǎn)對(duì)的區(qū)域增長(zhǎng)過程。本文中，N-pair-site距離圖的生成過程包含兩個(gè)關(guān)鍵步驟：1)計(jì)算每個(gè)像元到所有成對(duì)發(fā)生元的距離值；2)給每個(gè)像元分配最小(或最大)距離值，可以生成N-pair-site最近(或最遠(yuǎn))距離圖。

步驟1可通過查詢1-pair-site距離圖獲得,通過查詢圖中的像元值，可獲得每個(gè)像元到這對(duì)發(fā)生元的距離。因此，從N組發(fā)生元生成的一組1-pair-site距離圖，在每個(gè)1-pair-site距離圖中，通過查詢?cè)谙嗤恢玫拿總€(gè)像元的值，可獲得每個(gè)像元分別到這N組發(fā)生元的距離。

步驟2的詳細(xì)說明見圖3a。假設(shè)有4組發(fā)生元，ID分別為p1、p2、p3、p4，利用距離乘函數(shù)分別生成這4組發(fā)生元的1-pair-site距離圖，并用ID值代表生成的4個(gè)1-pair-site距離圖。對(duì)于每個(gè)像元，都可以查詢到其在這4個(gè)1-pair-site距離圖中的像元值，即為每個(gè)像素到這些在特殊的距離函數(shù)下生成的1-pair-site距離圖的距離值。例如，這4個(gè)1-pair-site距離圖對(duì)應(yīng)的3×3像素窗口的左上角的值分別為0、2、2、2。執(zhí)行了第二次疊加之后，每個(gè)1-pair-site距離圖中的像素值通過一個(gè)特定的算子合并成一個(gè)值，并生成了4-pair-site距離圖和2-site V圖。同樣以3×3窗口的左上角像素值為例，在使用最小算子的情況下，4-pair-site距離圖的左上角像素值為0。圖3b為生成4-pair-site距離圖的實(shí)例，兩次疊加所用的疊加算子分別為距離乘函數(shù)和最近的鄰近關(guān)系。步驟2通過圖4所示的第二次疊加完成，其與第一次疊加類似，但是添加的數(shù)據(jù)和疊加算子不同。第二次柵格疊加，將一組1-pair-site距離圖作為添加的數(shù)據(jù)，在合成的新距離圖中，1-pair-site距離圖中的每個(gè)像元會(huì)生成一個(gè)新的像素值。這個(gè)合成圖即為N-pair-site距離圖。此處使用的疊加算子根據(jù)鄰近關(guān)系的不同而不同。例如，最小(或最大)算子用來尋找最近(或最遠(yuǎn))領(lǐng)域，并生成包含任意鄰近關(guān)系的N-pair-site距離圖。

圖3 N-pair-site距離圖和2-site V圖的生成

Fig.3 Generation ofN-pair-site DM and 2-site V diagram

1.3 成對(duì)發(fā)生元V圖的生成和可視化

生成距離圖后，對(duì)應(yīng)的V圖可通過連接距離圖中的最大距離值或提取等距線相遇處的像素生成。使用生成4-pair-site距離圖時(shí)的相關(guān)信息，可生成2-site V圖。如圖3a所示，N-pair-site距離圖中的每個(gè)像素的距離值均來源于某個(gè)1-pair-site距離圖,這些像素值的來源決定了V圖的空間像素分配。因此，在生成4-pair-site距離圖的過程中，直接把像素值來源的1-pair-site距離圖的ID值賦給該像素，即可同時(shí)生成2-site V 圖?？紤]3×3窗口左上角的像素值，由于4-pair-site中該像素的值0來源的1-pair-site距離圖的ID值為p1，則2-site V圖中該像素的值為p1。實(shí)際上，N-pair-site距離圖中的距離值來源決定了Voronoi區(qū)域每個(gè)像元的值。改變疊加算子，如使用最遠(yuǎn)和次鄰近的鄰域關(guān)系，可生成對(duì)應(yīng)的4-pair-site距離圖和2-site V圖(圖3b)。

V圖可將平面劃分為若干區(qū)域或多邊形，將每個(gè)點(diǎn)對(duì)的ID值對(duì)應(yīng)的顏色渲染給對(duì)應(yīng)的區(qū)域，可將V圖可視化。渲染之后的Voronoi區(qū)域圖中，能夠迅速查詢出每個(gè)區(qū)域所歸屬的點(diǎn)對(duì)和鄰近關(guān)系，然而發(fā)生元的傳播方式和每個(gè)發(fā)生元到各個(gè)區(qū)域的距離等信息無法從V圖中獲取。在一幅圖中展現(xiàn)V圖的發(fā)生元、傳播距離和Voronoi區(qū)域這3個(gè)要素，就不會(huì)破壞V圖的完整性。尤其是2-site V圖，相比1-site V圖，其與距離定義和鄰近關(guān)系間的關(guān)系更密切。對(duì)于柵格疊加，關(guān)鍵步驟是把發(fā)生元和V圖疊加在距離圖之上，并將V圖調(diào)整至一定的透明度。

2 實(shí)驗(yàn)結(jié)果

為驗(yàn)證該方法的靈活性，本文使用文獻(xiàn)[2，5]中討論的算術(shù)距離函數(shù)和幾何距離函數(shù)及新定義的一些距離函數(shù)，共21種(表1)。利用這些距離函數(shù)，執(zhí)行第一次柵格疊加，可生成對(duì)應(yīng)的1-pair-site距離圖(圖4)。由表1和圖4可見，21種距離函數(shù)對(duì)應(yīng)的距離圖存在形態(tài)相似情況，因此可將表1中的21種距離函數(shù)和對(duì)應(yīng)的圖6中的1-pair-site距離圖分為幾組，每組距離函數(shù)本質(zhì)上相同。如圖4(1)和圖4(10)，其分別對(duì)應(yīng)距離函數(shù)(f1)和2-site的三角形周長(zhǎng)公式(f10)，因這兩個(gè)函數(shù)的差為一常數(shù)，所以圖4(1)和圖4(10)的等距線形狀相同。類似的還有3組：(f2，f20)，(f7，f9)，(f11，f14，f15，f16)。對(duì)這4組距離函數(shù)，每組只選擇一個(gè)函數(shù)進(jìn)行后續(xù)實(shí)驗(yàn),則后續(xù)實(shí)驗(yàn)所用距離函數(shù)為16種。

表1 21種距離函數(shù)的定義

Table 1 The definition of twenty-one kinds of distance functions

距離函數(shù)說明f1d(v，p)+d(v，q)距離和f2|d(v，p)-d(v，q)|距離差的絕對(duì)值f3d(v，p)×d(v，q)距離乘積f4Max(d(v，p)，d(v，q))Min(d(v．p)，d(v，q))距離相除f5Max(d(v，p)，d(v，q))取較大距離f6Min(d(v，p)，d(v，q))取較小距離f7d(v，lpq)空間點(diǎn)v到直線lpq的距離f8d(v，pq)空間點(diǎn)v到線段pq的距離f9SΔvpqΔvpq的面積f10PcΔvpq帶參數(shù)的Δvpq周長(zhǎng)：PcΔvpq=d(v，p)+d(v，q)+c·d(p，q)且c≥-1。當(dāng)c=1，PcΔvpq為Δvpq的周長(zhǎng)f11R1c(v，p，q)Δvpq的外接圓半徑距離函數(shù)說明f12R2cv，p，qΔvpq的內(nèi)切圓半徑f13R3Ovpq包含v、p、q的最小圓的半徑f14d(o，pq)o到線段pq的距離，o為Δvpq內(nèi)切圓圓心f15SΔopqΔopq的面積，o為Δvpq內(nèi)切圓圓心f16pΔopqΔopq的周長(zhǎng)，o為Δvpq內(nèi)切圓圓心f17∠pvq夾角∠pvqf18w1·d(v，p)+w2·d(v，q)加權(quán)距離，w1和w2分別為d(v，p)和d(v，q)的權(quán)重f19d2(v，p)+d2(v，q)距離平方和f20Var(d(v，(p，q)))V到點(diǎn)p和q距離的方差：Var(d(v，p)，d(v，q))=[(d(v，p)-d)2+(d(v，q)-d)2]/2且d=(d(v，p)+d(v，q))/2f21Var(d(v，p，q))v，p，q3個(gè)點(diǎn)之間的3個(gè)距離的方差：Var(d(v，p，q))=[(d(v，p)-d)2+(d(v，q)-d)2+(d(p，q)-d)2]/3且d=(d(v，p)+d(v，q)+d(p，q))/3

圖4 21種距離函數(shù)下的1-pair-site距離圖

Fig.4 1-pair-site DMs under 21 kinds of distance functions

3 討論

對(duì)本文方法的特性作如下討論：1)由圖4和圖5可見，本文方法可以生成多種類型的2-site V圖，從而實(shí)現(xiàn)2-site V圖的多樣性。通過改變距離函數(shù)和鄰近關(guān)系，可以控制生成的2-site V圖的外觀和性質(zhì)。本方法的主要特點(diǎn)是兩次柵格疊加過程：第一次柵格疊加的疊加算子是定義的21種距離函數(shù)，第二次柵格疊加的疊加算子為鄰近關(guān)系。通過改變第一次疊加的算子，不同的距離函數(shù)會(huì)生成不同結(jié)構(gòu)的2-site距離圖(圖4)。類似地，改變第二次疊加的算子，可以生成不同鄰近關(guān)系的N-pair-site距離圖和2-site V圖(圖5)。由于對(duì)多種距離函數(shù)和鄰近關(guān)系的一般控制，本文的方法具有靈活性和可控性。2)本文方法并不局限于點(diǎn)狀發(fā)生元，其可以用于生成任意形態(tài)發(fā)生元的V圖。這種基于柵格的處理方式，由于任何發(fā)生元(點(diǎn)、弧段和面)都按照相同的方法計(jì)算距離，因而極大地簡(jiǎn)化了不同形態(tài)發(fā)生元2-site V圖的生成過程。3)本文方法可以生成N-site V圖，此時(shí)的距離函數(shù)定義為每個(gè)點(diǎn)到多個(gè)發(fā)生元的距離。例如，3-site V圖的一個(gè)距離和函數(shù)定義的距離為點(diǎn)到3個(gè)發(fā)生元的距離。只需改變第一次疊加，該方法可生成3-site V圖。4)本文方法可以利用生成的距離圖模擬多種距離函數(shù)和鄰近關(guān)系下的成組發(fā)生元的區(qū)域增長(zhǎng)過程(圖5),且本文方法簡(jiǎn)單、健全且容易實(shí)現(xiàn)，其主要步驟是距離變換和柵格疊加,計(jì)算復(fù)雜度小，穩(wěn)定性高。5)作為一種基于柵格的方法，當(dāng)發(fā)生元數(shù)量比較多時(shí)，該方法比較費(fèi)時(shí)。為了提高效率，可以結(jié)合并行計(jì)算等方法，從而節(jié)省運(yùn)算時(shí)間。

4 結(jié)語

本文提出一種基于距離變換和柵格疊加的多發(fā)生元生成方法，生成了21種距離函數(shù)下的最遠(yuǎn)、次鄰近和最鄰近3種鄰近關(guān)系下的2-site V圖，并將其擴(kuò)展生成為多發(fā)生元V圖。實(shí)驗(yàn)表明：與現(xiàn)有矢量方法相比，本文方法具有普遍性和靈活性，具體體現(xiàn)在：1)可根據(jù)任意距離函數(shù)和鄰近關(guān)系，生成多種2-site V圖；2)方法并不局限于點(diǎn)發(fā)生元，可以應(yīng)用于任意形態(tài)發(fā)生元(如弧段和面)；3)由于采用柵格運(yùn)算方式，發(fā)生元由點(diǎn)類型擴(kuò)展到任意形態(tài)類型，并沒有增加算法的復(fù)雜度；4)可以在成對(duì)發(fā)生元V圖2-site V圖的基礎(chǔ)上擴(kuò)展生成N-site V圖；5)除V圖外，本文方法生成的廣義距離圖，可用來模擬成組的發(fā)生元在諸多約束條件下的區(qū)域增長(zhǎng)過程。因此，它很可能成為分析生長(zhǎng)模型在相關(guān)應(yīng)用領(lǐng)域(如材料科學(xué)和植物生態(tài)學(xué))的一個(gè)有力工具。

[1] BAREQUET G,DICKERSON M T,SCOT DRYSDALE R L.2-Point site Voronoi diagrams[J].Discrete Applied Mathematics,2002,122(1):37-54.

[2] CHEN Z G,XIAO Y Y,CAO J.Approximation by piecewise polynomials on Voronoi tessellation[J].Graphical Models,2014,76(5):522-531.

[3] EMIRIS I Z,MANTZAFLARIS A,MOURRAIN B.Voronoi diagrams of algebraic distance fields[J].Computer-Aided Design,2013,45(2)：511-516.

[4] HANNIEL I,BAREQUET G.On the triangle-perimeter two-site Voronoi diagram[A].6th International Symposium on Voronoi Diagrams in Science and Engineering[C].2009.

[5] DICKERSON M T,EPPSTEIN D.Animating a continuous family of two-site Voronoi diagrams (and a proof of a bound on the number of regions)[A].Proceedings of the 25th Annual Symposium on Computational Geometry[C].2009.

[6] ASANO T,TAMAKI H.Angular Voronoi diagram with applications[A].3rd International Symposium on Voronoi Diagrams in Science and Engineering[C].2006.

[7] BAREQUET G,DICKERSON M T,EPPSTEIN D,et al.On 2-site Voronoi diagrams under geometric distance functions[A].8th International Symposium on Voronoi Diagrams in Science and Engineering[C].2011.

[8] VYATKINA K,BAREQUET G.On 2-site Voronoi diagrams under arithmetic combinations of point-to-point distances[A].7th International Symposium on Voronoi Diagrams in Science and Engineering[C].2010.

[9] DICKERSON M T,GOODRICH M T.Two-site Voronoi diagrams in geographic networks[A].16th ACM SIGSPATIAL International Conference on Advances in Geopraphic Information Systems[C].2008.

[10] VACAVANT A.Fast distance transformation on irregular two-dimensional grids[J].Pattern Recognition,2010,43(10)：3348-3358.

[11] CHEN J.A raster-based method for computing Voronoi diagrams of spatial objects using dynamic distance transformation[J].International Journal of Geographical Information Science,1999,13(3)：209-225.

A Raster-Based Method to Generate Two-Site Voronoi Diagrams

JIANG Wei1,WU Yan-lan2,TAN Shu-dong3,MA Yi-wen4

(1.WuhanGeomaticInstitute,Wuhan430022;2.SchoolofResoucesandEnvironmentEngineering,AnhuiUniversity,Hefei230601;3.NationalMarineDataandInformationService,Tianjin300171;4.WuhanLandResourcesandPlanningBureau,Wuhan430014,China)

In contrast with the regular (1-site) Voronoi Diagram,the 2-site VD has more variants due to the change of the distance function.Generating the 2-site VD with respect to arbitrary distance functions and constraints remains a challenge in the field.This paper proposes a flexible and general approach to generate 2-site VD by combining the distance transform and raster overlay into a unified framework.This framework is characterized by the two procedures of raster overlay：the first overlay procedure whose operator is used to control the distance function,and the second overlay procedure whose operator is specified by the neighbor relationship.By manipulating the two overlay operators,the nearest-(furthest-,etc.) neighbor 2-site VDs with respect to the various distance functions can be obtained.The proposed approach was implemented and tested with 21 kinds of distance functions.The results show improved flexibility and robustness over existing vector-based approaches and emphasize the convenience of extending to general sites andN-site VD.The proposed approach also producesN-pair-site distance map：a new type of distance map,providing an easy and convenient way to simulate the region-growing process of the sites previously grouped into different pairs.

distance function;Voronoi diagram;distance transform;growth model

2014-12-22；

2015-03-11

國(guó)家自然科學(xué)基金項(xiàng)目(41271443);安徽省自然科學(xué)基金項(xiàng)目(1308085MD52)

江威(1988-)，男，碩士研究生，研究方向?yàn)榈貓D學(xué)與地理信息系統(tǒng)。*通訊作者E-mail：wylmq@sina.com

10.3969/j.issn.1672-0504.2015.05.009

P208

A

1672-0504(2015)05-0039-05