空间邻近的表达及其应用

闫超德，刘 晓，李爱民

（郑州大学 水利与环境学院 地理信息工程系，河南 郑州 450001）

0 引 言

对于地理信息科学而言，空间邻近是极其重要的一类空间关系，在空间分析与查询中必不可少，甚至被认为是建立空间信息系统的基础[1-5]。虽然邻近的概念在许多领域内频繁出现，但是它的定义却繁杂不一，许多领域的研究者在使用这一概念时并没有给出严格的定义与描述，即关于邻近的含义是模糊的[1]。本文针对相离对象之间的位置关系所引起的邻近关系，首先梳理人类空间知识中邻近相关的概念，然后分别给出对应概念的形式化表达，最后探索了空间邻近在变比例尺移动地图表达中的应用。

1 人类空间知识中有关邻近的概念

邻近概念广泛存在于人类的自然语义中，并且存在一定的模糊性，至少存在5种相关的邻近概念。

1.1 最邻近

最邻近是人类空间知识中最常见的一种邻近，广泛存在于自然语义中，如“××中学是离我家最邻近的中学”。最邻近的概念是建立在度量关系之上，是指两个空间位置或对象之间存在最小的距离，距离可以是欧几里德距离，也可以是街区距离（最短路径），还可以是大地距离。最邻近的最大特点是结果的确定性，即最邻近对象一定存在且通常唯一。

1.2 范围邻近

范围邻近也是自然语义中常见的一种邻近，如“我家两公里范围内有3所学校”。范围邻近的概念是由度量关系和拓扑关系共同确定的，即按照度量关系划定一个范围（如矩形、圆或多边形），然后判断空间对象与这个范围是否相交，相交则为邻近。范围邻近最大的特点表现为多尺度性，即随着划定范围的变化，邻近对象会发生变化，当范围小于最邻近距离时，邻近对象个数为0，邻近对象的个数随邻近范围的增大而增加。当范围邻近非空时，一定包含最邻近对象。

1.3 k最邻近

k最邻近是最邻近的发展，简单地说就是距离某对象或观测点最近的k个对象，如“我家最近的三所学校分别是××、××和××”。k最邻近的概念依然是建立在度量关系之上，这种邻近通常表现为一对多，如果结果成立，则一定包含最邻近对象。

1.4 方向邻近

在自然语义中，还有一种邻近是与方向关系交织在一起的，如某一出租车要求电台查询“我行驶前方最近的医院”。显然，这种邻近是由度量关系和方向关系共同决定的，也可以称为方向约束下的邻近。

1.5 环绕邻近

环绕邻近是一个最为模糊与复杂的空间概念，如“郑州市周边的邻近城市有新乡、焦作、洛阳、许昌和开封”,如图1所示。首先这种邻近要求邻近对象分布在观测点周围（如周边各个方向），其次，要求邻近对象与观测点之间既要“通视”（不存在其他对象）又要最近（该方向范围内距离观测点最近）。显然，这种邻近中既包含有度量关系，又包含拓扑关系和方向关系。

图1 环绕邻近示意图Fig.1 The illustration of surrounding neighbor

2 邻近的形式化表达

2.1 最邻近的形式化表达

根据点集空间中最近邻近的定义[6]，由点、线、面对象组成的地理空间中，最邻近可以定义为：给定地理对象集O={o1,o2,…,on}及观测点（也可以是某地理对象，以下简称为观测点）m，oi是m的最邻近，当且仅当d(m,oi)≤mind(m,oj)，其中i≠j且oj,oj∈O。d(m,oi)表示观测点（对象）m与地理对象oi之间的最短距离。基于Voronoi图的最邻近可以定义为：oi是m的最邻近，当且仅当m∩oiv≠ （oiv指地理目标oi的Voronoi区域)。图2中，观测点m处在地理对象a的Voronoi势力范围内，所以m与a最邻近。

图2 基于Voronoi图的最邻近定义Fig.2 The definition of nearest neighbor based on Voronoi diagram

2.2 k最邻近的形式化表达

k最邻近也称k最近邻[7]，在计算机科学中k最邻近的定义是基于度量给出的，其实质是查找距离q最邻近的k个点。给定点集S与查询点q，如果S′ S,Pi∈S＇(j＜k),pj∈S-S′(j＜n),d(q,pi)≤d(q,pi)那么称S′为查询点q的k个最邻近点[8]。扩展至由点、线、面地理对象组成的地理空间，观测点的k最邻近可以定义为：给定地理对象集O与观测点m，如果O′ O,oi∈O-O′(i＜k),oj∈O-O′(j＜n),d(m,oj)≤d(m,oj),那么O′称为观测点m的k个最邻近地理对象。

2.3 范围邻近的形式化表达

给定地理对象集O、观测点m和限定范围R，如果O′ O,oi∈O',oio∩R≠ ，那么称O′为观测点m的范围邻近（其中oio表示地理对象oi的内部）。

2.4 环绕邻近的形式化表达

目前，可以较好地描述环绕邻近的方法有两种，它们分别是基于Voronoi图和Delaunay三角网的描述方法。

2.4.1 基于Voronoi图的空间邻近表达

20世纪90年代以来，以加拿大拉瓦大学Gold教授为首的一批专家开始研究利用Voronoi图方法表达和判断相离空间目标之间的侧向相邻关系。其基本思想是，将N个空间目标作为N个生长元，将整个连续空间划分为Voronoi铺盖，则每一空间目标唯一地被一个Voronoi区域包含，将具有公共Voronoi边的目标之间的关系定义为Voronoi邻近关系[1,5,9]。李成名等人根据空间目标的类型，进一步将线目标及其邻近地理目标之间存在的关系定义为侧向邻近关系[10]。为了弥补九交模型[11]在描述空间关系方面存在的理论缺陷，陈军等提出了以对象的Voronoi区域代替对象补的V9I模型[12-14]，该模型可以区分出相离对象之间的邻近关系，集中了交叉方法与交互方法的优点，使空间关系描述更加合理且易于操作[15]。根据V9I模型，观测点与地理目标之间的Voronoi邻近关系可以表达成如下形式：

对于地理对象oi(oi∈O)和观测点m，如果存在oiv∩mv≠ （oiv表示地理对象oi对应的Voronoi区域，mv表示观测点m对应的Voronoi区域），那么称oi与观测点m具有Voronoi邻近关系。图3中，观测点m与地理对象a、b、d之间具有Voronoi邻近关系，也称为直接邻近。

图3 Voronoi邻近示意图Fig.3 Illustration of Voronoi neighbor

Voronoi图是依据最邻近准则，把地理空间中的每一点分配给距离其最近的空间目标后所形成的一种空间剖分面片图，两目标间的Voronoi区域的个数同样也反映了它们之间的邻近程度。由此陈军、赵仁亮等人提出了k阶Voronoi邻近的概念[3，16-17]。

设P是二维笛卡尔空间有限凸域上空间目标P1,P2,…,Pn的集合，Pi，Pj∈P（i≠j；i,j=1,2,…,n），在其剖分后所形成的Voronoi图（Pv）上，Pi，Pj的Voronoi区域分别为Piv,Piv,将Pi与Pj之间Voronoi区域的最少个数k称为空间目标Pi与Pj的Voronoi距离，记为dv(Pi，Pj)，且dv(Pi，Pj)≥0；当Pi=Pj，dv(Pi，Pj)=0。在图3中，dv(m,a)=1；dv(m，b)=1；dv(m，c)=2；dv(m，d)=1；dv(m,e)=2。从图3中可以看出，Voronoi距离值的大小反映了两目标间的邻近情况，当值为0时，两目标最邻近；当值为1时，两目标较邻近；值越大，说明邻近程度越弱。利用Voronoi距离，可以定义一种新的邻近关系，即Voronoi k阶邻近[3]。

设P是二维笛卡尔空间有限凸域上空间目标P1,P2,…,Pn的集合，Pi，Pj∈P（i≠j；i,j=1,2,…,n），Pi，Pj的Voronoi区域分别为Piv,Piv，如果Piv,Piv存在，且dv(Pi，Pj)为k，则称Pi与Pj之间存在k阶邻近关系，记为＜Pi,kAdj, Pj＞，那么

图3中，观测点m与目标a、b和d之间为一阶邻近，而与目标c和e为二阶邻近。

2.4.2 基于Delaunay三角网的邻近表达

Delaunay三角网是一个连通图，其中每一点都是连通的，因此，Delaunay三角形的每一条边都隐含着两个点之间的邻近关系。杜晓初等基于Delaunay三角网分别给出了地理目标之间的邻近和k阶邻近的定义[18-19]，根据该定义观测点k阶Delaunay邻近定义如下：

P为某一观测点m与n个地理对象pi的集合，在P对应的约束Delaunay三角网T中，如果m与pi地理目标之间的最小Delaunay距离为k，则称该地理目标与观测点之间的关系为k阶Delaunay邻近关系，记为＜m，Neighbor(k)，pi＞，即

特别地，当k=1时，这两个目标的关系是邻近关系。图4中，观测点m与p1和p2为一阶邻近关系，与p3为二阶邻近关系。

图4 Delaunay邻近示意图Fig.4 The Illustration of Delaunay neighbor

2.5 方向关系约束下的邻近形式化表达

设观测点m的邻近对象集为o（可以是邻近中的任何一种），根据方向约束条件C确定的约束区域为D（根据四方向、八方向等方法划定），如果o′o,oi∈O',oio⌒R≠ ，其中，oio表示地理对象oi的内部，那么称o′是观测点m的方向约束下邻近对象。

3 基于Voronoi邻近的变比例尺移动地图表达

3.1 变比例尺移动地图模型及存在问题

变比例尺地图是指，在一幅地图内放弃统一的比例尺，让比例尺随着区域的重要性而变化，这种地图制图方法可以充分利用地图图幅的空间，提高地图的信息负载量和功能[20-22]。针对小屏幕移动地图，Harrie将小屏幕地图空间划分为3个区域，将用户当前位置附近区域作为焦点区域，采用大比例尺重点表达，而将外围区域采用小比例尺次要表达，两个区域中间部分采用变比例尺表达，按照区域范围划分方式不同，可以分为圆形（如图5所示）与矩形两种变比例尺表达模型[23-24]，式（1）是圆形窗口的变比例尺地图表达模型。

图5 圆形变比例尺模型示意图Fig.5 The illustration of circular variable scale model

其中，S1为焦点区域比例尺，Ss为外围区域比例尺。

但是，由于该模型的焦点区域大小及其比例尺大小都是事先设定的，对于地理信息密集或复杂的区域，可能比例尺显得过小（导致焦点信息过量或过度综合），而对于地理信息稀疏区域，焦点区域的比例尺可能显得太大（导致焦点信息太少）。显然，要想显著引起用户对焦点区域信息的注目，必须根据用户位置周围的信息分布确定合理的焦点区域地图比例尺。

3.2 基于Voronoi邻近的变比例尺移动地图表达

变比例尺地图焦点区域的合适比例尺问题，其核心是合理确定焦点地图内容。那么，哪些地理要素应该放置在核心区域呢？对于移动地图的用户，最有可能关注的首先是用户周围的POI以及邻近范围的道路网。基于该思路，本文提出通过Voronoi邻近关系计算，动态计算当前位置邻近范围内的POI以及路口，根据邻近范围的大小确定焦点区域比例尺，一方面保证焦点区域内放置的是用户真正关心的信息，另一方面也保护焦点区域内信息量的适度。具体实现步骤如下：

步骤1：获取用户当前位置；`

步骤2：依据邻近关系计算邻近的POI及路口范围；

步骤3：根据邻近范围确定最大包围圆半径R（以当前位置为中心）；

步骤4：计算焦点区域合适比例尺（分母）R/r0；

步骤5：依据式（1）进行变比例尺地图表达。

图6是基于模拟器生成的郑州东区会展中心附近变比例尺手机地图，图6a基于静态焦点区域比例尺模型生成，图6b基于Voronoi邻近区域计算采用动态焦点区域比例尺模型生成。由于焦点区域比例尺设置合理，既保证了焦点区域容易注目，还增加了外围地图的参考信息量。在改善变比例尺移动地图的易读性同时，提高了变比例尺地图的表达效率。

图6 两种模型对比Fig.6 The comparison between two models

4 结束语

空间邻近是空间关系的重要组成部分，将在空间分析、位置服务以及地图制图等领域有广泛应用前景。本文通过梳理人类空间知识中相关的空间邻近概念，然后结合相关学科的研究成果给出相关概念的形式化表达，最后结合移动地图的变比例尺表达，研究了基于空间邻近的焦点范围选择、焦点区域比例尺计算，不仅改善了移动地图的易读性，还提高了变比例尺地图表达的效率。