基于ArcEngine的似Voronoi多邊形生成方法

摘要：Voronoi圖是對空間的一種無縫分割方式，是GIS空間分析中一個十分重要的工具，但是目前尚缺乏一些高效穩(wěn)定的構建任意地理實體（點、線、面）Voronoi圖的方法。本文在ArcGIS軟件穩(wěn)定生成點集V圖功能的基礎上，采用ArcEngine組件技術，利用C#開發(fā)語言構建了任意地理實體的似Voronoi圖。

關鍵字：似Voronoi圖；ArcEngine；空間分析

Voronoi結構是由俄國數(shù)學家M.G.Voronoi于1908年發(fā)現(xiàn)并以他的名字命名的。它的實質是一個不規(guī)則多邊形剖分結構，每個多邊形內的點到相應離散點的距離比其他離散點的距離要近。然而，Voronoi圖的起源最早可以追溯到17世紀。1644年，R.Descartes用類似Voronoi圖的結構顯示太陽系中物質的分布。數(shù)學家G.L.Dirichlet于1850年同樣研究過它，所以有時把Voronoi圖又叫Dirichlet Tessellation[1]。在地理學界最先應用Voronoi圖的是荷蘭氣象學家A.H.Thiesssen，他利用 Voronoi圖研究氣象觀測站隨機分布，所以這個多邊形也被稱為泰森（Thiesssen）多邊形[2]。

Voronoi圖是對空間的一種無縫分割方式，是一種十分重要的空間分析工具[3]。到20世紀60年代，Voronoi圖概念在自然科學和社會科學中已被廣為接受，但在算法研究領域，多數(shù)集中在離散點集上，目前仍然缺乏一些簡單的高效穩(wěn)定的構建任意發(fā)生元Voronoi圖的方法，為此本文利用文獻[3， 4]的思想，采用ArcEngine組件技術構建了任意地理實體（點、線、面）的Voronoi圖，以滿足地理信息系統(tǒng)中空間分析的需要。

1.Voronoi圖生成方法

Voronoi圖按照對象集合中元素的最近屬性將空間劃分成許多單元區(qū)域，有著按距離劃分鄰近區(qū)域的普遍特性，因此它應用領域非常廣闊，也得到了廣泛研究，產生了生成V圖的多種方法。對其構造算法的研究，從對象的幾何屬性分類，有點生成方法、線生成方法[5， 6]和面生成方法[5， 7]；從生成算法的方式分類，有直接方法和間接方法[2]；從生成算法的特點分類，有矢量方法和柵格方法[3]。

2.基于GIS軟件生成任意目標似Voronoi圖的總體思想

目前，點狀要素的Voronoi圖生成算法已經成熟，雖然我們尚不能直接構建復雜地理實體的Voronoi圖，但是可以將復雜形狀的地理實體分解為點集來處理。文獻[3]給出了一般圖形Voronoi圖的構建方法——近似構造法，其基本思想是，用有限點來逼近原始圖形（目標對象），從而代替原始圖形，然后構建這些離散點集的Voronoi圖，最后消除一些多余的Voronoi邊和多余的Voronoi頂點，最終得到原始圖形的逼近Voronoi圖。

基于GIS軟件的基本步驟：

第一步，對于每個原始目標（線、面）Ai，用有限的點集Pi來逼近Ai的邊界，即在Ai邊界上增加節(jié)點，并轉換為點集；

第二步，構建所有點集P的Voronoi圖V；

第三步，從V中消除那些屬于同一目標點集所產生Voronoi邊和那些孤立的點；

第四步，輸出V圖。

但是，這種方法只能生成以點集包絡矩形（Envelope）為邊界的V圖，因此它只能作為一種表現(xiàn)形式，不能作為空間分析的工具。因為所有的地理分析都是在一定的區(qū)域范圍內進行的，而區(qū)域的形狀是多樣的。為了生成目標區(qū)域邊界V圖，還必須將上述第三步后的V圖與目標區(qū)域求交，但是如果V圖的包絡矩形的范圍小于目標區(qū)域包絡線范圍，這種情況下得到的V圖見圖1（粗線為目標區(qū)域邊界），很明顯這種V圖也不能滿足地理分析的需要，因此在上述第三步中須生成以目標區(qū)域包絡矩形為邊界的V圖。

對于近似構造法，擬合點數(shù)量越多，近似程度就越好，但是由于受時間、空間的限制，不可能無限度地使用大量擬合點，因此近似構造法關鍵的問題是如何設置擬合點，文獻[3]并沒有給出設置擬合點的原則。關于如何設置擬合點可以參考文獻[ 4]，文獻提出了用點近似V圖與一般V圖中對應Voronoi多邊形的面積作為近似程度的度量的觀點，即用兩者面積差的大小來衡量近似程度的高低，并建立了面積差與擬合點間距的數(shù)學模型。

3.基于ArcEngine實現(xiàn)任意目標似V圖的算法

ArcEngine是ESRI公司推出的一組完備的并且打包的嵌入式GIS組件庫和工具庫，不依賴ArcGIS Desktop桌面平臺，直接安裝ArcEngine Runtime和DeveloperKit后，即可利用其在不同開發(fā)語言環(huán)境下開發(fā)，具有簡潔、靈活、易用、可移植性強等的特點。因此，我們可以充分利用ArcGIS軟件穩(wěn)健生成點狀要素Voronoi圖、多邊形的融合等功能來實現(xiàn)任意復雜地理實體的普通Voronoi圖的構建。

本文利用ArcEngine（10.1）組件，采用C#.Net（2008）開發(fā)語言，實現(xiàn)了任意復雜地理實體的普通近似Voronoi圖。其算法流程圖如圖2所示。

算法流程具體描述如下：

（1）要素邊界插入節(jié)點。獲取需要生成V圖的圖層（主要指線、面圖層）后，通過要素Densify（double，double）方法給要素邊界按一定距離插入節(jié)點，該方法的第一個參數(shù)是距離閾值，其值可以根據(jù)實際對Voronoi圖精度的需要來確定；第二個參數(shù)是最大偏差值，偏差為0 時表示距離閾值按邊界曲線計算。

（2）將節(jié)點生成點要素。首先通過InMemoryWorkspaceFactoryClass類在計算機內存中創(chuàng)建工作區(qū)，然后通過IFeatureWorkspace.CreateFeatureClass方法建立一個點要素類，并生成點圖層，最后將IPointCollection接口獲得的要素邊界節(jié)點存入點圖層中。

（3）構建點集V圖。利用ITinNodeCollection.ConvertToVoronoiRegions方法生成點集V圖，該方法有五個參數(shù)，第一個IFeatureClass為空的面要素類，用于寫入V多邊形；第二個參數(shù) ITinFilter為過濾條件（本文設置為null，即讓所有的點都參與V圖計算）；第三個參數(shù)IPolygon為Clip多邊形，值得注意的是，如果將此參數(shù)設置為目標區(qū)域多邊形，那么就不用進行（5）的操作，通過實驗發(fā)現(xiàn)這種方式的效率極低，因此，本文將此參數(shù)設置為目標區(qū)域的包絡矩形；第四個參數(shù) string為Tin中點集索引字段；第五個參數(shù) string位Tin點集標識字段，也就是點集V圖融合字段。

（4）點集V圖融合操作。這步是將（3）中產生的點集V圖按標識字段進行融合，用到的方法主要是ITopologicalOperator.ConstructUnion，該方法的唯一參數(shù)是IEnumGeometry，即按標識字段獲得的V多邊形集合，合并操作完成后，需刪除點集的Voronoi多邊形，否則會產生冗余多邊形。

（5）V圖求交。這屬于GIS矢量圖層的疊加操作，在ArcEngine中也有多種方法可以實現(xiàn)，本文提供兩種簡便方法，第一種是采用ITopologicalOperator.Intersect的方法；第二種是通過Geoprocessor類調用ESRI.ArcGIS.AnalysisTools.Intersect工具，這種方法相對第一種更加簡單，效率較高。

4.實例與分析

為了驗證該方法的可行性，筆者以數(shù)字湘西州1：2000DLG數(shù)據(jù)中面狀要素（居民地）為例予以說明，并與利用ModelBuilder數(shù)據(jù)建模工具建立的似V圖模型進行時間復雜性的對比分析。本文選取的距離閾值分別為：4m、8m、12m、16m、20m，節(jié)點個數(shù)分別為：13542個、8452個、6831個、5707個、5366個。然后分別用AE算法和似V圖模型構建了Voronoi多邊形，實際計算結果如表1所示（Pentium（R）處理器 @ 3.20GHz，2.00內存），圖3是依據(jù)計算結果繪制的折線圖。

從計算結果中可以清楚的看出，雖然都是基于ArcGIS軟件，但采用AE的方法在時間效率上明顯高于似V圖模型（ArcToolBoxs中的分析工具）。通過對生成似V圖的每一步分析發(fā)現(xiàn)，在構建以目標區(qū)域包絡矩形為邊界的點集V圖上耗時較多，AE算法約占整個算法的85%，而似V圖模型則占90%左右。該方法易于實現(xiàn)，但其時效性由ArcGIS軟件自身決定。關于插值距離如何確定，可以參考文獻[4]的公式（3.3），也可根據(jù)其應用領域的精度要求進行設置。

結束語

Voronoi圖可以提供諸如影響范圍、鄰近、局域動態(tài)、幾何重要度衡量等重要特性，因而具有廣泛的應用領域。本文基于ArcEngine構建任意地理實體似Voronoi圖的方法，能夠穩(wěn)健地生成復雜地理實體（線狀要素和面狀要素）的近似Voronoi圖，在一定誤差范圍內基本上能滿足大多GIS分析的需要。

參考文獻

[1] 楊承磊. 多邊形的Voronoi圖及其應用研究[D]. 山東大學， 2004.

[2] 王家耀，李志林，武芳. 數(shù)字地圖綜合進展[M]. 北京： 科學出版社， 2011.

[3] 王新生，劉紀遠，莊大方，等. 基于GIS的任意發(fā)生元Voronoi圖逼近方法[J]. 地理科學進展. 2004， 23（4）： 97-102.

[4] 張有會，淺野哲夫，小保方幸次. 關于一般圖形Voronoi圖的近似構造法的研究[J]. 數(shù)值計算與計算機應用. 2002， 9 （3）： 216-225.

[5] 王新生，李全，郭慶勝，等. Voronoi圖的擴展、生成及其應用于界定城市空間影響范圍[J]. 華中師范大學學報（自然科學版）. 2002， 36（1）： 107-111.

[6] 董蕊. 線段加權Voronoi圖的離散生成[D]. 河北師范大學， 2006.

[7] 李成名，陳軍. 面條目標Voronoi圖生成的動態(tài)距離變換策略[J]. 遙感信息. 2000（1）： 6-11.

作者簡介：張奎（1986-），男，碩士，2012年畢業(yè)于武漢大學地圖學與地理信息系統(tǒng)專業(yè)，目前主要從事“數(shù)字城市”建設與應用和測繪管理等工作。