地理多要素Voronoi圖相鄰關系下的地圖放大裁剪方法

李 佳，段 平，梁 明，呂海洋

(1. 云南師范大學旅游與地理科學學院，云南 昆明 650500； 2. 云南省地理空間信息技術工程技術研究中心，云南 昆明 650500； 3. 安徽大學資源與環境工程學院，安徽 合肥 230601； 4. 虛擬地理環境教育部重點實驗室(南京師范大學)，江蘇 南京 210023)

地理多要素Voronoi圖相鄰關系下的地圖放大裁剪方法

李 佳1,2，段 平1,2，梁 明3，呂海洋4

(1. 云南師范大學旅游與地理科學學院，云南 昆明 650500； 2. 云南省地理空間信息技術工程技術研究中心，云南 昆明 650500； 3. 安徽大學資源與環境工程學院，安徽 合肥 230601； 4. 虛擬地理環境教育部重點實驗室(南京師范大學)，江蘇 南京 210023)

針對以歐氏距離作為放大因子對電子地圖進行放大裁剪引起的信息失衡問題，提出了采用地理多要素Voronoi圖相鄰關系的地圖放大裁剪方法，可有效避免以歐氏距離作為地圖放大因子的地圖信息失衡問題。將電子地圖中的地理要素分為點、線、面，對于點要素，構建它的Voronoi圖；對于非點要素，即線和面要素，構建它們的近似Voronoi圖，當用戶對電子地圖中感興趣地理要素目標放大時，只需要提取該目標的多要素Voronoi圖相鄰要素的近似Voronoi圖，并計算它們的最小外包矩形，將最小外包矩形區域用于最終的地圖放大裁剪區域，則可較好地顧及用戶感興趣地理要素目標周圍的地理要素信息，可提高地圖的易讀性。采用本文方法對某區域電子地圖進行了試驗，結果表明，地理多要素Voronoi圖相鄰關系的地圖放大裁剪方法能夠較好地顧及目標周邊地理要素信息，避免了以歐氏距離為放大因子的地圖信息失衡。

電子地圖；Voronoi；相鄰關系；地圖放大；地圖裁剪

電子地圖正日益成為一種技術參數和應用有效的地圖產品形式[1]。相比傳統的紙質地圖，電子地圖可承載更多的地理要素信息，同時也衍生出一些需要研究和亟待解決的問題，如地圖標注相互遮蓋與沖突[2]、地圖的版權[3]、地圖的符號[4]，地圖的更新與定位[5-6]、地圖的可視化等[7]。電子地圖可視化表達是電子地圖學研究的核心，其研究目的是對地圖進行放大或縮小時以最清晰易懂、層次分明，內容適宜地呈現給用戶。

當前電子地圖放大操作是以歐氏距離作為放大比例因子。當用戶對電子地圖中某個地理要素目標感興趣時，需要以該目標為中心坐標，按照一定的歐氏距離放大因子將原始小比例尺地圖放大到大比例尺地圖，在放大過程中如果歐氏距離放大因子過大，則目標信息充滿整個屏幕，導致目標周圍信息量太小，目標周邊東南西北4個方向的地圖信息在地圖裁剪過程中丟失，最終影響地圖的易讀性；如果歐氏距離放大因子過小，則目標周圍信息量太大，同樣也會影響地圖的易讀性且需重復放大操作，最終也可能出現歐氏距離放大因子過大出現的情況，即:信息失衡。

信息失衡問題是地圖放大過程中的一個常見問題[8-9]，因缺少用戶感興趣地理要素目標周邊的地理要素信息，最終影響了用戶對地圖的認知，因此需要在有限的屏幕上呈現給用戶感興趣地理要素目標及其周邊區域信息，以提高地圖的易讀性。空間相鄰關系是人們認識空間相鄰兩個對象之間關系的一種手段，可使用戶能夠較好地顧及感興趣地理要素目標的周邊地理要素信息[10-11]。空間相鄰關系根據各地理要素目標的Voronoi圖是否存在公共邊來判斷[12]。目前對Voronoi圖的生成方法及其相鄰關系的研究主要以點要素為主[13-15]，在電子地圖放大裁剪方法中，將地標、路點、興趣點作為研究對象，即將它們抽象為地圖中的點要素，構建點要素的Voronoi圖并求用戶感興趣目標的相鄰關系作為地圖放大裁剪區域，而將水系、街區等線、面地理要素僅僅作為地圖背景對象[8-9]，而實際上電子地圖是由地理全要素(點、線、面對象)構成，用戶感興趣的目標不僅僅是點要素，同樣也對線、面地理要素感興趣，如用戶感興趣的是湖泊、道路時，它們以面、線地理要素呈現在電子地圖中，而僅以點要素Voronoi相鄰關系的地圖放大裁剪方法不能較好地解決此類問題。為了避免地理多要素電子地圖在地圖放大裁剪過程中的信息失衡問題，本文充分考慮電子地圖中的所有信息載體——即地理多要素(點、線、面對象)的相鄰關系，構建電子地圖中地理多要素的近似Voronoi圖，并提取了用戶感興趣目標的Voronoi圖及其相鄰關系的最小外包矩形(minimum bounding rectangle,MBR)，將MBR區域映射為地圖放大中的裁剪窗口，使得地圖在放大裁剪過程中較好地顧及周邊地理要素信息，避免了地圖放大裁剪中的信息失衡問題。

1 多要素Voronoi圖及其相鄰關系

用戶對地圖目標的認知，不僅限制于目標本身，地圖目標周圍的地理要素能夠增加用戶對周圍環境的認知。地理目標Voronoi圖的相鄰關系能夠較好地展現目標及其他周邊地理要素的空間關系，可提高地圖的易讀性。電子地圖中地理要素由點、線、面等多要素組成，需要分別構建多要素的Voronoi圖及其相鄰關系。

1.1 點要素Voronoi圖的相鄰關系

Voronoi圖的生成方法是以離散的點為研究對象，對于點要素的Voronoi圖，無論是基于矢量還是基于柵格的構建方法都較為成熟，本文在此不再贅述。給定一個點(要素)集，構建點要素的Voronoi圖，如果各點要素的Voronoi圖存在公共邊，則認為具有公共邊的兩個Voronoi圖的點要素為相鄰關系。如圖1所示，(a)中五角星為點要素及相應的Voronoi圖，假設(b)中深灰色區域為用戶感興趣目標的Voronoi區域，則與它具有Voronoi公共邊的點要素為淺灰色區域內的五角星，深灰色區域Voronoi圖的相鄰關系范圍為淺灰色區域，共有6個相鄰的點要素Voronoi圖在空間上較好地分布在用戶感興趣目標區域周邊，可提高用戶對地圖的認知。

圖1 點要素Voronoi及其相鄰關系

1.2 線、面要素Voronoi圖生成及其相鄰關系

1.2.1 線、面要素Voronoi圖生成方法

目前沒有生成線、面要素Voronoi圖的算法，可以構建線、面要素的近似Voronoi圖。線要素在數據結構組織上是由線段的起點和終點組成，即點要素組成，面要素是由多條線要素組成，而線要素也是由點要素組成。因此只需首先提取線、面要素的點要素，然后分別生成點要素的Voronoi圖，最后把點要素所隸屬線、面要素的Voronoi圖合并為多邊形將其近似為線、面要素Voronoi圖[16]，在此基礎上，同樣可以按照Voronoi圖是否存在公共邊來判斷各要素之間的相鄰關系。但是如果線要素過長、面要素較大則會導致構成它們的基本點要素較少，生成點要素的Voronoi圖將其合并成多邊形時，多邊形呈非完整閉合。為了避免該情況的出現，本文對線、面要素首先通過加密點預處理，在此基礎上生成多要素的Voronoi圖。

電子地圖中一般按要素的類型分層，對圖層進行管理和可視化，分別記點、線、面要素圖層為：Layerpoint、Layerline、Layerpolygon，每個圖層是各相同類型要素的集合，分別記它們的集合為：P={p1,p2,…,pi,i=1,2,3,…，n}，L={l1,l2,…,li,i=1,2,3,…，n}，S={s1,s2,…,si,i=1,2,3,…，n}，其中pi表示Layerpoint中的某一個點要素，是點集P中的元素；li表示Layerline中的某一條線要素，是線集L中的元素；si表示Layerpolygon中的某一個面要素，是面集S中的元素。電子地圖中多要素Voronoi圖的生成方法，具體步驟如下：

Step1：對線、面要素進行等間距的點集加密，首先設置等間距距離Δx，然后依次從集合L和S中取出元素，根據Δx將線、面要素離散化成點要素，最后建立點要素與隸屬線、面要素之間的關系。

Step2：構建所有點要素及從線、面要素中轉為點要素的Voronoi圖。

Step3：根據Step1中所建立的點要素與隸屬線、面要素之間的關系，依次將線、面要素所包含的點要素Voronoi進行合并，近似為線、面的Voronoi圖。

將生成的多要素(點、線、面)Voronoi圖放在臨時多邊形圖層LayerVoronoi中，便于后期放大裁剪的MBR求取，它的集合為V={v1,v2,…,vi,i=1,2,3,…，n}，vi表示LayerVoronoi中的某一個Voronoi多邊形。

1.2.2 線、面要素Voronoi圖的相鄰關系

圖2、圖3所示分別為線、面要素的近似Voronoi圖及其相鄰關系，圖2(a)為將線打斷成離散點及其相應的Voronoi圖，圖2(b)為線要素合并后的近似Voronoi圖，假設深灰色的區域為用戶對線要素感興趣目標的近似Voronoi圖，則周邊相鄰的6個淺灰色區域多邊形為它相鄰關系的線要素近似Voronoi圖，同樣對于面要素的近似Voronoi圖及其相鄰關系如圖3(a)、(b)所示，最終Voronoi相鄰關系對象在空間上均具有較好的均勻分布。

圖2 線要素的近似Voronoi圖及其相鄰關系

圖3 面要素的近似Voronoi圖及其相鄰關系

2 多要素Voronoi圖相鄰關系地圖放大裁剪

在生成電子地圖多要素的Voronoi圖基礎上，提取用戶感興趣目標(查詢且需要放大的目標)要素相鄰關系的Voronoi圖并將其合并為一個多邊形，計算它的MBR用于地圖裁剪區域，最終以自適應窗口方式裁剪地圖，可避免以歐氏距離作為放大因子的地圖信息失衡問題。

記用戶感興趣地理要素目標對象為o，在已構建多要素Voronoi圖的基礎上，根據o對地圖進行自適應裁剪操作。具體操作方法如下：

Step1：在集合V中查找包含o的vi。

Step2：在LayerVoronoi上，查找與vi相鄰的其他vj,i=1,…,n，i≠j。

Step3：將vi與vj合并成多邊形，并計算多邊形的MBR。

Step4：根據MBR的大小，從整個地圖中裁剪該區域并填充至整個屏幕。

當需要將小比例尺地圖放大到大比例尺地圖時，選取用戶感興趣目標Voronoi相鄰關系多邊形的MBR作為地圖放大操作的裁剪區域，從而完成地圖放大裁剪。

3 試驗驗證

采用Microsoft Studio 2008和ArcGIS Engine9.3為開發平臺，試驗硬件配置為Inter Core i7處理器，CPU為2.29 GHz，內存為4 GB，試驗數據為昆明市某一部分區域的電子地圖，如圖4(a)所示。

分別采用以歐氏距離作為放大因子和地理多要素Voronoi相鄰關系作為放大因子的地圖放大裁剪方法對電子地圖進行放大操作。如圖4中用戶感興趣地理點要素目標為“市師范學院”，以“市師范學院”為中心，采用歐氏距離為放大因子對地圖放大裁剪后，如圖4(b)所示，“市師范學院”周邊信息丟失，尤其是西南、西北方向信息基本缺失，信息失衡現象嚴重，而正北方向保留的信息也不完整，嚴重影響了用戶對感興趣地理要素目標及其周邊信息的認知和理解。而采用地理多要素Voronoi相鄰關系的地圖放大裁剪方法結果如圖4(d)所示，“市師范學院”周邊信息在地圖放大裁剪過程中保存較為完整，其主要原因是采用了Voronoi相鄰關系，點要素“市師范學院”的Voronoi圖與其他地理多要素的Voronoi圖具有Voronoi相鄰關系，如圖4(c)所示為電子地圖多要素的Voronoi圖生成結果，其中“市師范學院”的Voronoi圖為深灰色區域，而與它具有公共邊的Voronoi相鄰關系有點要素Voronoi圖和線、面要素近似Voronoi圖，共計6個Voronoi多邊形(淺灰色區域)，均較好地分布在“市師范學院”的周邊，圖4(c)為本文方法實現的中間過程，最終結果是將所求取的MBR區域映射到原始地圖中進行放大裁剪操作，以圖4(d)顯示給用戶，用戶在對“市師范學院”進行放大時，周邊的地理要素均較好地呈現在“市師范學院”周邊，豐富了用戶對“市師范學院”的空間認知，增強了用戶對感興趣目標的空間認知。

圖4 地圖放大裁剪結果

4 結 語

本文分析了以歐氏距離作為放大因子對電子地圖放大操作引起的信息失衡問題，針對此類問題，引入地理多要素Voronoi圖及其相鄰關系，構建了電子地圖地理多要素的Voronoi圖，提取了用戶感興趣地理目標的Voronoi相鄰關系及其相對應的相鄰Voronoi多邊形MBR用于地圖自適應裁剪區域，有效地避免了地圖在放大過程中信息失衡的問題，通過試驗驗證了該方法的可行性，該方法可為電子地圖放大裁剪操作提供一種新的思路。

[1] 龍毅，溫永寧， 盛業華.電子地圖學[M].北京：科學出版社，2006.

[2] 朱長青，符浩軍，繆劍，等. 一種自適應的數字柵格地圖可見水印算法[J]. 測繪學報,2013,42(2)：304-309.

[3] 李安波， 王海榮，周衛. 基于二維混沌系統的矢量數字地圖置亂加密[J]. 中國礦業大學學報, 2015,44(4)：747-753.

[4] 吳明光， 余粉香， 陳泰生，等. 地圖符號的XML Web Services共享方法[J]. 中國圖象圖形學報, 2011,16(12)：2211-2216.

[5] 唐建智，裴蓮蓮，任海英，等．一種房屋電子地圖快速更新的方法及其實現[J]. 測繪通報,2017(1): 79-82．

[6] 李華蓉，趙一. 室內定位導航地圖一體化設計[J]. 測繪通報, 2015(9):32-35.

[7] 江南, 曹亞妮, 趙軍喜,等. 不同密度區電子地圖多尺度顯示模型的建立與應用[J]. 武漢大學學報(信息科學版)，2013, 38(4)：465-469.

[8] 陳軍，閆超德，趙仁亮，等. 基于Voronoi鄰近的移動地圖自適應裁剪模型[J]. 測繪學報,2009, 38(2)：152-155.

[9] 閆超德，趙仁亮， 陳軍，等. 基于鄰近的移動地圖自適應可視化方法[J]. 武漢大學學報(信息科學版), 2006, 31(12)：1112-1115.

[10] 陳軍， 趙仁亮. GIS空間關系的基本問題與研究進展[J]. 測繪學報,1999(2)：95-102.

[11] 陳軍. Voronoi動態空間數據模型[M]. 北京：測繪出版社, 2002.

[12] 李成名， 陳軍. 基于 Voronoi 圖的空間鄰近定義與查詢[J]. 武漢測繪科技大學學報, 1998,23(2)： 128-131.

[13] 李成名，陳軍. Voronoi 圖生成的柵格算法[J]. 武漢測繪科技大學學報, 1998, 23(3)： 208-210.

[14] 李佳田，陳軍， 趙仁亮，等. 基于線性四叉樹結構的 Voronoi 圖反向膨脹生成方法[J]. 測繪學報, 2008,37(2)：240-249.

[15] 李佳田，羅富麗， 余莉，等. 梯度 Voronoi 圖及其構建算法[J]. 武漢大學學報(信息科學版)，2016, 41(2)：163-170.

[16] 李佳田，楊琪莉，羅富麗，等. 線/面Voronoi圖的分解合并生成算法[J]. 武漢大學學報(信息科學版)，2015,40(11)：1545-1550.

MethodofMapZoomingandClippingUsedbyNeighborhoodRelationshipofGeographicalMulti-factorVoronoiDiagram

LI Jia1,2，DUAN Ping1,2，LIANG Ming3，Lü Haiyang4
(1. College of Tourism and Geographical Sciences, Yunnan Normal University, Kunming 650500,China; 2. Geospatial Information Technology Engineering Research Center of Yunnan Province, Kunming 650500，China; 3. School of Resources & Environment Engineering, Anhui University，Hefei 230601，China; 4. Key Laboratory of Virtual Geographic Environment (Nanjing Normal University), Ministry of Education, Nanjing 210023，China)

Aimed at the problem of information imbalance caused by the amplification of the electronic map with the Euclidean distance as the amplification factor, a method of map zooming and clipping based on multi-factor Voronoi diagram has been proposed in this paper. This method can effectively avoid the problem of the map information imbalance, which is based on the Euclidean distance as the map magnification factor. The geographical elements are abstracted as points, lines, polygons and divided into two categories: point elements and non-point elements. For point elements, construct the Voronoi diagram of point elements. For the non-point elements, namely, line and polygon elements, constructing their approximate Voronoi diagram. When the user amplify the geographical elements of the target which is interested in, only need to extract the multi-factor of the target Voronoi diagram adjacent elements. And then calculate their minimum bounding rectangle (MBR). The MBR area is used in the map clipping region, and it can keep the surrounding geographical information of the users who interest in the geographical elements of the target. The method is adopted of this paper to test some regional electronic map. The result shows that The natural neighbor method based on the multi-factor Voronoi diagram can better take into account the target and its surrounding information when amplify the map. This method can improve the legibility of the map, to avoid the Euclidean distance as the map zoom factor and multiple operations.

electronic map; Voronoi; neighborhood relationship; map zooming; map clipping

李佳，段平，梁明,等.地理多要素Voronoi圖相鄰關系下的地圖放大裁剪方法[J].測繪通報，2017(10)：84-88.

10.13474/j.cnki.11-2246.2017.0321.

2017-02-17;

2017-04-12

國家自然科學基金(41561082)；安徽省地理信息工程中心創新平臺項目(Y01001529)

李 佳(1984—)，女，博士，講師，主要從事近景攝影測量和地圖制圖的研究工作。E-mail：keguigiser@163.com

段 平。E-mail：dpgiser@163.com

P208

A

0494-0911(2017)10-0084-05