地理多要素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