10
5.3 Voronoi-图的特性及其在蜂 Voronoi窝定位中的优点
Voronoi多边形所组成的 多边形所组成的Voronoi-图具有许多 多边形所组成的 图具有许多 十分优良的性质， 十分优良的性质，这里总结了与空间关系及其 计算相关的， 计算相关的，特别是与蜂窝通信系统移动终端 定位有关的几种性质， 定位有关的几种性质，以便更好地理解其在空 间关系计算和在蜂窝通信系统移动终端定位中 的应用。陈军总结了Voronoi-图与 图与GIS密切相 的应用。陈军总结了 图与 密切相 关的几条重要性质，如侧向邻近、 关的几条重要性质，如侧向邻近、局域动态性 等，其中一些性质与蜂窝通信系统移动终端定 位也十分相关，在此一并列出。 位也十分相关，在此一并列出。
8
80年代后期，加拿大Laval大学的 年代后期，加拿大 大学的C.M.Gold 年代后期 大学的 教授等最先将Voronoi-图用于研究 图用于研究GIS动态空 教授等最先将 图用于研究 动态空 间数据模型。此后，有关Voronoi-图的理论方 间数据模型。此后，有关 图的理论方 法和应用成为研究的热点内容。90年代以来， 法和应用成为研究的热点内容。 年代以来， 年代以来 领域， 在GIS领域，Voronoi-图已开始应用于空间数 领域 图已开始应用于空间数 据模型、空间分析(如网络分析 如网络分析、 据模型、空间分析 如网络分析、最短路径分 统计分析、空间相关分析、聚类)、 析、统计分析、空间相关分析、聚类 、空间 查询(如邻近查询 空间推理、 如邻近查询)、 查询 如邻近查询 、空间推理、地形建模与可 视化、地图综合与数字化等多个方面。Wright 视化、地图综合与数字化等多个方面。 认为其是未来GIS的一个重要发展 和Goodchild认为其是未来 认为其是未来 的一个重要发展 方向。 方向。
2
5.2 Voronoi-图的概念 Voronoi一般的Voronoi-图是以任意相邻三 图是以任意相邻三 一般的 点不在同一直线的若干点组成的点 集为生长点， 集为生长点，以这些点的所有相邻 两点的中垂线组成的连续多边形。 两点的中垂线组成的连续多边形。
Voronoi-图与 图与Delaunay三角网互为对偶 。 图与 三角网互为对偶 见图5-1。 见图 。
11
1) 线性特性
Voronoi-图的 图的Voronoi 边和 图的 Voronoi 结点的个数随空间生长目标 个数n成线性比例增加 成线性比例增加， 个数 成线性比例增加，具有并不复 杂的结构。 杂的结构。
12
Voronoi-图是具有 个多边形和至少三 图是具有n个多边形和至少三 图是具有 个节点的平面图(planar graph)。设其中 个节点的平面图 。 的生长点、 边和Voronoi 结点的 的生长点、Voronoi 边和 个数分别为n， ， （ ）。由于 个数分别为 ，ne，nv（3≤n<∞）。由于 ）。 每一条Voronoi边有两个节点，每一节点 边有两个节点， 每一条 边有两个节点 至少属于三条边，因此有2ne≥3nv。 至少属于三条边，因此有2ne≥3nv。运用 欧拉规则（ 欧拉规则（Euler’s relation）n+ nv- ne= ） 2，则有 ， ne≤3i-图实质上是基于临近原则形成 图实质上是基于临近原则形成 的一种空间剖分结构， 的一种空间剖分结构，由空间剖分后形 成的多边形集合构成， 成的多边形集合构成，每一多边形对应 一个生长点。 一个生长点。多边形区域内的每一点到 与之对应的点目标的距离比到任何其它 目标都近， 目标都近，刻划了空间点的临近区域于 影响区域的边界。 影响区域的边界。Voronoi-图是一种基 图是一种基 本的几何结构， 本的几何结构，它十分接近于自然现象 的本质，干旱开裂的农田， 的本质，干旱开裂的农田，是一种典型 的Voronoi-图。因此 图 因此Voronoi-图是解决相 图是解决相 关几何问题的有力工具， 关几何问题的有力工具，具有广泛的应 用。
3
图5-1 Voronoi-图与D-三角网(实线为V-图， Voronoi-图与D 三角网(实线为V 虚线为D 三角网) 虚线为D-三角网)
4
Voronoi-图和 图和Delaunay三角网的形式化数学 图和 三角网的形式化数学 定义是： 定义是： 为平面上的点， 设x为平面上的点，则区域 为平面上的点 V(i)={x∈E2|d(x,vi)≤d(x,vj), j=1,2,...,N, j≠i}称为 ∈ 称为 Voronoi多边形（简称 多边形）。各点的 多边形（ 多边形）。 多边形 简称V-多边形）。各点的 Voronoi多边形共同组成 多边形共同组成Voronoi-图。 图 多边形共同组成 Delaunay三角网的定义：有公共边的 三角网的定义： 三角网的定义 有公共边的Voronoi 多边形称为相邻的Voronoi多边形。连接所有 多边形。 多边形称为相邻的 多边形 相邻的Voronoi多边形的生长点所形成的三角 相邻的 多边形的生长点所形成的三角 网称为Delaunay三角网（简称 三角网）。 三角网（ 三角网）。 网称为 三角网 简称D-三角网 D-三角网的外边界是一个凸多边形，它由节 三角网的外边界是一个凸多边形， 三角网的外边界是一个凸多边形 点集中的凸集形成，通常称为凸壳。 点集中的凸集形成，通常称为凸壳。
第五讲 Voronoi-图的特点及 Voronoi其在空间定位中的应用
5.1 引言 5.2 Voronoi-图的概念 图的概念 5.3 Voronoi-图的特性及其在蜂窝定位中的 图的特性及其在蜂窝定位中的 优点 5.4 Voronoi-图生成算法 图生成算法 5.5 Voronoi-图移动定位中的具体应用 图移动定位中的具体应用 5.5 Voronoi-图生成演示 图生成演示
5
对不同n维 图进行了定义， 对不同 维Voronoi-图进行了定义，对 图进行了定义 研究多维Voronoi-图及其应用具有参考 研究多维 图及其应用具有参考 意义；另外，依据不同的距离、权重、 意义；另外，依据不同的距离、权重、 阶数等还可以分别对其扩展生成各种不 同的Voronoi-图，如距离 同的 图 如距离Voronoi-图、加 图 权Voronoi-图、高阶 图 高阶Voronoi-图、 图 Poisson Voronoi-图等广义 图等广义Voronoi-图 图等广义 图 （generalized Voronoi图）。 图
1
5.1 引言
Voronoi-图是被普遍接受和广泛采用的用 图是被普遍接受和广泛采用的用 于分析研究区域离散数据的有力工具， 于分析研究区域离散数据的有力工具，也活 跃于所有与2D及以上分析有关的领域 及以上分析有关的领域。 跃于所有与 及以上分析有关的领域。 Voronoi-图具有许多优良的特性 Voronoi-图具有许多优良的特性。 图具有许多优良的特性。 图引入到无线电定位技术中， 把Voronoi-图引入到无线电定位技术中， 图引入到无线电定位技术中 主要对大区制和中等区制的蜂窝移动通信系 统整个覆盖区域和基站覆盖区域进行自动、 统整个覆盖区域和基站覆盖区域进行自动、 动态、快速的划分， 动态、快速的划分，以加速蜂窝系统移动终 端定位过程，提高定位精度和准确度。 端定位过程，提高定位精度和准确度。
17
删除生长点d 只影响其邻近生长点a、 、 、 图5-3 删除生长点 只影响其邻近生长点 、c、e、g
18
对 Voronoi-图生长目标的添加亦为局 图生长目标的添加亦为局 部操作。这一特性使得Voronoi-图的构 部操作。这一特性使得 图的构 建具有局域动态特性。 建具有局域动态特性。这一特性对于移 动通信环境改变， 动通信环境改变，如新建或拆除建筑物 和通信基站等后，快速、动态、 和通信基站等后，快速、动态、高质量 的生成Voronoi-图，提供了极大的方便， 的生成 图 提供了极大的方便， 从而对适应于射线跟踪定位的数据库和 序列-位置数据库的建立和维护具有特别 序列 位置数据库的建立和维护具有特别 的意义， 的意义，非常有利于蜂窝通信系统移动 终端射线跟踪定位。 终端射线跟踪定位。
9
在空间关系应用方面， 在空间关系应用方面，Voronoi-图也得到了 图也得到了 许多学者的重视。 运用Voronoi-图将空间 许多学者的重视。Gold运用 运用 图将空间 目标之间邻近问题转化为空间目标的voronoi多 目标之间邻近问题转化为空间目标的 多 边形之间的邻近问题来处理， 边形之间的邻近问题来处理，将空间目标之间 的邻近定义在voronoi多边形具有公共边的两个 的邻近定义在 多边形具有公共边的两个 空间目标之间， 空间目标之间，从而为空间邻近问题的解决提 供了一个统一的方法。陈军等在基于Voronoi供了一个统一的方法。陈军等在基于 图的空间邻近定义的基础上，对现有流行的空 图的空间邻近定义的基础上， 间关系形式化描述框架9交模型进行了改进 交模型进行了改进， 间关系形式化描述框架 交模型进行了改进， 使用空间目标的Voronoi区域代替其补，提出 区域代替其补， 使用空间目标的 区域代替其补 了新的基于Voronoi-图的空间关系模型，从而 图的空间关系模型， 了新的基于 图的空间关系模型 克服了原模型中的许多不足。 克服了原模型中的许多不足。
7
早在17世纪 就采用了类Voronoi-图 早在 世纪 Descartes 就采用了类 图 表达太阳系及其环境中的物质分布。 表达太阳系及其环境中的物质分布。Gauss 于 1840年发现二次型（quadric forms）可以看作 年发现二次型（ 年发现二次型 ） 是在空间中平行多面体分布的点的Voronoi 图； 是在空间中平行多面体分布的点的 Dirichelet在此基础上给出了二次型可归约性 在此基础上给出了二次型可归约性 （reducibility）的简单证明；Voronoi则将其 ）的简单证明； 则将其 扩展至高维空间； 扩展至高维空间；荷兰气象学家泰森 （A.H.Thiessen）1911年采用其划分每一气象 ） 年采用其划分每一气象 观测站的最近区域， 观测站的最近区域，以改进大范围平均降水量 的预测能力。为了纪念这些科学家，后人将之 的预测能力。为了纪念这些科学家， 图或Dirichelet 铺盖 称为 Voronoi-图或 图或 ）、泰森多边形 （tesselation）、泰森多边形（Thiessen ）、泰森多边形（ polygon）。 ）。