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

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

地理多要素Voronoi圖相鄰關(guān)系下的地圖放大裁剪方法

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

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

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

電子地圖；Voronoi；相鄰關(guān)系；地圖放大；地圖裁剪

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

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

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

1 多要素Voronoi圖及其相鄰關(guān)系

用戶對(duì)地圖目標(biāo)的認(rèn)知，不僅限制于目標(biāo)本身，地圖目標(biāo)周圍的地理要素能夠增加用戶對(duì)周圍環(huán)境的認(rèn)知。地理目標(biāo)Voronoi圖的相鄰關(guān)系能夠較好地展現(xiàn)目標(biāo)及其他周邊地理要素的空間關(guān)系，可提高地圖的易讀性。電子地圖中地理要素由點(diǎn)、線、面等多要素組成，需要分別構(gòu)建多要素的Voronoi圖及其相鄰關(guān)系。

1.1 點(diǎn)要素Voronoi圖的相鄰關(guān)系

Voronoi圖的生成方法是以離散的點(diǎn)為研究對(duì)象，對(duì)于點(diǎn)要素的Voronoi圖，無論是基于矢量還是基于柵格的構(gòu)建方法都較為成熟，本文在此不再贅述。給定一個(gè)點(diǎn)(要素)集，構(gòu)建點(diǎn)要素的Voronoi圖，如果各點(diǎn)要素的Voronoi圖存在公共邊，則認(rèn)為具有公共邊的兩個(gè)Voronoi圖的點(diǎn)要素為相鄰關(guān)系。如圖1所示，(a)中五角星為點(diǎn)要素及相應(yīng)的Voronoi圖，假設(shè)(b)中深灰色區(qū)域?yàn)橛脩舾信d趣目標(biāo)的Voronoi區(qū)域，則與它具有Voronoi公共邊的點(diǎn)要素為淺灰色區(qū)域內(nèi)的五角星，深灰色區(qū)域Voronoi圖的相鄰關(guān)系范圍為淺灰色區(qū)域，共有6個(gè)相鄰的點(diǎn)要素Voronoi圖在空間上較好地分布在用戶感興趣目標(biāo)區(qū)域周邊，可提高用戶對(duì)地圖的認(rèn)知。

圖1 點(diǎn)要素Voronoi及其相鄰關(guān)系

1.2 線、面要素Voronoi圖生成及其相鄰關(guān)系

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

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

電子地圖中一般按要素的類型分層，對(duì)圖層進(jìn)行管理和可視化，分別記點(diǎn)、線、面要素圖層為：Layerpoint、Layerline、Layerpolygon，每個(gè)圖層是各相同類型要素的集合，分別記它們的集合為：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中的某一個(gè)點(diǎn)要素，是點(diǎn)集P中的元素；li表示Layerline中的某一條線要素，是線集L中的元素；si表示Layerpolygon中的某一個(gè)面要素，是面集S中的元素。電子地圖中多要素Voronoi圖的生成方法，具體步驟如下：

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

Step2：構(gòu)建所有點(diǎn)要素及從線、面要素中轉(zhuǎn)為點(diǎn)要素的Voronoi圖。

Step3：根據(jù)Step1中所建立的點(diǎn)要素與隸屬線、面要素之間的關(guān)系，依次將線、面要素所包含的點(diǎn)要素Voronoi進(jìn)行合并，近似為線、面的Voronoi圖。

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

1.2.2 線、面要素Voronoi圖的相鄰關(guān)系

圖2、圖3所示分別為線、面要素的近似Voronoi圖及其相鄰關(guān)系，圖2(a)為將線打斷成離散點(diǎn)及其相應(yīng)的Voronoi圖，圖2(b)為線要素合并后的近似Voronoi圖，假設(shè)深灰色的區(qū)域?yàn)橛脩魧?duì)線要素感興趣目標(biāo)的近似Voronoi圖，則周邊相鄰的6個(gè)淺灰色區(qū)域多邊形為它相鄰關(guān)系的線要素近似Voronoi圖，同樣對(duì)于面要素的近似Voronoi圖及其相鄰關(guān)系如圖3(a)、(b)所示，最終Voronoi相鄰關(guān)系對(duì)象在空間上均具有較好的均勻分布。

圖2 線要素的近似Voronoi圖及其相鄰關(guān)系

圖3 面要素的近似Voronoi圖及其相鄰關(guān)系

2 多要素Voronoi圖相鄰關(guān)系地圖放大裁剪

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

記用戶感興趣地理要素目標(biāo)對(duì)象為o，在已構(gòu)建多要素Voronoi圖的基礎(chǔ)上，根據(jù)o對(duì)地圖進(jìn)行自適應(yīng)裁剪操作。具體操作方法如下：

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

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

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

Step4：根據(jù)MBR的大小，從整個(gè)地圖中裁剪該區(qū)域并填充至整個(gè)屏幕。

當(dāng)需要將小比例尺地圖放大到大比例尺地圖時(shí)，選取用戶感興趣目標(biāo)Voronoi相鄰關(guān)系多邊形的MBR作為地圖放大操作的裁剪區(qū)域，從而完成地圖放大裁剪。

3 試驗(yàn)驗(yàn)證

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

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

圖4 地圖放大裁剪結(jié)果

4 結(jié) 語(yǔ)

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

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

[2] 朱長(zhǎng)青，符浩軍，繆劍，等. 一種自適應(yīng)的數(shù)字柵格地圖可見水印算法[J]. 測(cè)繪學(xué)報(bào),2013,42(2)：304-309.

[3] 李安波， 王海榮，周衛(wèi). 基于二維混沌系統(tǒng)的矢量數(shù)字地圖置亂加密[J]. 中國(guó)礦業(yè)大學(xué)學(xué)報(bào), 2015,44(4)：747-753.

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

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

[6] 李華蓉，趙一. 室內(nèi)定位導(dǎo)航地圖一體化設(shè)計(jì)[J]. 測(cè)繪通報(bào), 2015(9):32-35.

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

[8] 陳軍，閆超德，趙仁亮，等. 基于Voronoi鄰近的移動(dòng)地圖自適應(yīng)裁剪模型[J]. 測(cè)繪學(xué)報(bào),2009, 38(2)：152-155.

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

[10] 陳軍， 趙仁亮. GIS空間關(guān)系的基本問題與研究進(jìn)展[J]. 測(cè)繪學(xué)報(bào),1999(2)：95-102.

[11] 陳軍. Voronoi動(dòng)態(tài)空間數(shù)據(jù)模型[M]. 北京：測(cè)繪出版社, 2002.

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

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

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

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

[16] 李佳田，楊琪莉，羅富麗，等. 線/面Voronoi圖的分解合并生成算法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，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圖相鄰關(guān)系下的地圖放大裁剪方法[J].測(cè)繪通報(bào)，2017(10)：84-88.

10.13474/j.cnki.11-2246.2017.0321.

2017-02-17;

2017-04-12

國(guó)家自然科學(xué)基金(41561082)；安徽省地理信息工程中心創(chuàng)新平臺(tái)項(xiàng)目(Y01001529)

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

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

P208

A

0494-0911(2017)10-0084-05