（基础数学专业论文）变速城市voronoi图及其生成.pdf

j i f 北帅范人学坝l 研究生学位论义 摘要 城市v o r o n o i 图是基于考虑l 1 平面上任意两点之间花费的最短 时间而提出的，它作为、，o m n o i 图在距离方面的推广具有重要意义。 本文对城市v o f o n o i 图定义作了进一步的扩展，提出了一种新的城市 v o r o n o i 图变速城市v o r o n o i 图，给出了变速城市v o r o n o i 图的 定义、性质及相关证明，同时提出了一种基于结晶生长方式的直接 构造变速城市v o r o n o i 图的算法，该方法也完全适用于构造城市 v b r o n o i 图。结晶生长是从若干个点出发，每一点分别按照各自的生 长方式结晶式向外扩展的一种方式。该算法与生成元的个数，交通 路线的条数、类型和位置无关，简单易行，效率较高，尤其在构造 生成元个数较多，交通网络比较复杂的变速城市r o n o i 图方面具有 显著优势。 关键词计算几何v o r o n o i 图城市v o r o n o i 图变速城市 v o r o n o i 图交通网络l l 平面 一一 型! ! 婴些叁鲎竺! ：鲨塑兰兰垡堡塞 c o n s i d e r i n gt h es h o n e s tt i m eb e t w e e nt w op o i n t so nt h el 1 一p l a n e ，t h ec j t y v o m n o id i a 伊a mi sp r e s e n t e d b e i n ga i le x t e n s j o no ft h ev o m n o id i a g r a mi nt h e m e t r i c i ti so fm o r ei m p o n a n c e t 1 l i sp a p e re x t e n d st h ed e 矗n i t i o o fc n yv o r o n o j d i a g r a m ，a l l dp r e s e n t san e wc i t yv r o r o n o id i a g r a m c i t yv b r o n o id i a g r 锄w i t ha v a r i o u s 。s p e e dt r a n s p o n a t i o nn e t w o r k t h i st y p e0 ft h ev o t 咖o id i a g r a mi sd e f i e d ， a n di t sb a s i cp r o p e n j c sa r ci n v e s t i g a t e d 缸t h es a m et i m ea n a p p r o x i m a t i o n a 1 9 0 r i t l l t l li sp r o p o s e d n i sa l g o r i t h mi sb a s e do nam e t h o do fc r y s t a lg r o 州h ，a n di t i sa p p r 叩r i a t ef o rt h ec i t yv 0 r o n o id i a 舒锄c r y s “g m w t hi st h a ts t a r t i n gf r o m s e v e r a id i 骶r e n tp o i n t s 卸de a c hp o i n te x t e d so u t s i d ea l la r o u n dw i t h h e 班o w t h m e t h o do fi t so w n t h i sp i o p o s e da l g o r i t h mi s i n d e p e n d c n to fm en u m b e fo f g e n e r a t o r sa n di h e 肌m b e ro fn o d e so f t h et 啪s p o f t a t i o nn e t 、v o r k i ti ss i m p i et o i m p l e m e n ta n de 腼d e n t a n dt h ep r o p o s e da 1 9 0 五t t i ma c t sb e t t c re s p e c i a l l yf o r c o s t 川c t i n gt h i st y p eo fc i t yv b m n o jd i 雄口mw i t hm o f cg c n e r a t o r sa n dm o r c c o m p l i c a t e dt r a n s p o r t a t i o nn e m o r k k e yw o r d s ：c o m p u t a t i o n a lg e o m e t f y ，、b r o n o id i a g r 锄，c i t y 、b r o n o jd i a g r a m ，c i t y 、，o r o n o jd i a g r a mw i t hav a r i o u s s p e e dt r 觚s p o r t a t i o nn e t 、v o r k ，t h et r a n s p o r t a t i o n n e t w o r k ，l 1 - p l a i l e 铺4 蜒 l l 北帅扎人学砸l 研究生学位论史 第一章绪论 1 1 计算几何与v o r o n o i 图 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有 些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比 如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的 算法。在现代工程和数学领域，计算几何在计算机图形学、机器人技术、超大 规模集成电路设计和统计等诸多领域有着十分重要的应用。 v o r o n o i 图是一个经典的计算几何学概念。它描述的是空间点集对于包含 该点集的研究区域的一种剖分。这种剖分结果能够很好地表达点与点之间的邻 近关系以及点的影响范围等重要的空间关系信息。此外，v o r o n o i 图还有许多 良好的数学性质。 在计算几何领域中，v o r o n o j 图理论已成功解决了寻找最近点、求最大空 圆、求n 个点的凸包和最小树等问题。另外，在模式识别、气象、测绘、城市 规划和移动通信等许多领域都受到了广泛而深入的研究。 1 2 问题提出的现实背景及研究现状 l _ 2 1 问题提出的现实背景 最邻近点问题由于在现实生活中被经常用到，因此在计算几何领域受到广 泛重视。邮局问题就是一个实例：在某城市中给定一个位置，找到距离这个位 置最近的邮局。我们可以通过构造v 0 r o n o i 图对城市进行区域分割，分割后每 个邮局都对应平面上唯一一个区域，该区域就是该邮局的控制范围，此时位于 该控制范围内的任何一点到该邮局的距离比到其他邮局的距离都短，从而使该 问题得到圆满的解决。在普通v o m n o i 图中，平面上任意两点之间的距离是基 于欧氏距离的，因此，最自然的解释是我们可以以恒定速度在任何方向上以直 线方式行走。 但是现代城市为我们提供了多种行走路线，从自行车行走路线到地铁，从 公路到国内航班等。此时我们就很自然地考虑为了在最短的时问内到达某个邮 局，我们该如何选择最佳的那一个。如果我们把两点之间所用的最短时间作为 河北师范人学坝j 。研究生学位论文 两点之削的距离，那么此时我们所选择的距离往往就会涉及到选择若干种交通 路线以及在不同类型交通路线之问的徒步行走。为了解决这个问题，人们提出 了一种新的距离时间距离。那么构造基于这种距离的v o r o n o i 图就可以解 决这类问题。 1 2 2 研究现状 现实生活中的交通路线分两类：一种是具有固定站点的交通路线，如公交 车、火车和飞机等公共交通系统都有固定的进出站点；另一种是可以任意出入 交通网络的交通路线。 关于第一种类型的交通路线，y b e 珊a n 口叫在他的博士论文中已经解决这个 问题。在解决这个问题时，他并没有使用时间距离，而是通过给各个不同站点 赋予适当的权值，把问题转化为基于欧氏距离下加权v o r o n o i 图的问题。 第二种类型的交通路线，到目前为止还没有完全解决。由于交通网络的复 杂性，哪怕是交通路线的一个局部的变化，对于解决这个问题都会带来相当的 困难。0 s w i n c h h 0 1 z e r l l 】等在具有交通路线的l 1 平面( 即平面上任意两点 p g l ，) ，1 ) ，窜 2 ，y 2 ) 之间的距离定义为d ( p ，q ) ；l x l x 2 l + i y l 一y 2 1 ) 上，以平面 上任意两点之间花费的最短时间为“距离”，提出了“城市m n o i 图”的概念， 并且给出了一种基于抽象f o n o i 图的构造算法。该算法的实现依赖于抽象 v o r o n o i 图的构造1 2 一，并且算法实现与生成元的个数和交通网络中节点的个数有 关，用于编程实现的数据结构较复杂。 1 3 论文的研究内容 城市v o m n o i 图是一种特殊距离下的、b r o n o i 图，是v o r o n o i 图在距离方面 进行扩展而形成的。但是在城市v o r o n o i 图中，所有交通路线的速度都是相同 的，而在现实世界中交通路线有多种类型，且各种类型的交通路线具有不同的 速度比如：公路，铁路等。 因此本文我们给城市、b r o n o i 图中不同类型的交通路线分别赋予不同的速 度，其中同种类型的交通路线的速度是恒定的，从而提出了一种新的城市 v o r o n o i 图变速城市v 0 r o n o i 图，扩展了城市v o m n o i 图的定义，使得城市 、，o m n o i 图成为变速城市、，o m n o i 图的一个特例。另外本文也提出一种基于结晶 籀61 j 1 北师范人学倾i 卅究生学位论文 生长方式【4 1 构造变速城市v o r o n o i 图的生成算法。该算法简洁实用，效果较好， 尤其在构造生成元个数比较多和交通网络比较复杂的变速城市v 0 r o n o i 图方面 具有显著优势。 1 4 论文的结构安排 本文共分六章。 第一章为绪论，简要叙述了计算几何与v o r o n o i 图之间的关系、问题提出 的现实背景及研究现状，并且介绍了论文研究的基本内容；第二章介绍了 v o r o n o i 图及城市v o t o n o i 图的定义和基本性质，v o f o n o i 图的主要生成算法以及 生成城市v o r o n o i 图的基本思想。 第三章、第四章为本文的核心部分。第三章介绍了变速城市、b m n o i 图的 定义和基本性质；第四章给出了变速城市v o r o n o i 图的生成算法。首先定义生 长、结晶生长的概念，然后叙述了结晶生成变速城市v o r o n o i 图的基本思想并 且对该算法实现的关键步骤给出了具体的分析，最后对该算法与已有算法加以 比较和分析。 第五章给出应用实例；第六章是总结和展望，对本文的主要工作及贡献进 行了总结，并对下一步的工作进行了展望。最后是参考文献、致谢和附录。 第7 “ 北帅范人学硕：研究生学位论义 第二章v o r o n o i 图和城市v o r o n o i 图 在介绍变速城市v o m n o i 图之前，我们需要先了解一下v o r o n o j 图及城市 v o r o n o i 图的定义及其基本性质。 2 1 、，b m n o i 图 2 1 1v o n o j 图的定义及其基本性质 v o r o n o i 图最早由俄罗斯数学家v 0 r o n o i 于1 9 0 8 年提出，平面上一个点集s 的v o m n o i 图是对平面的一个划分，每个分区表示一些点的集合，这些点到s 的一个元素比到其它元素更近。其数学定义【5 1 如下： 定义l 给定平面上n 个点构成的集合sz 妇l ，p 2 ，几 ，其中任何四点不共 圆，由 r ( p ，p r ) 一 p r 2 i | 陋一p ，l c i p p 川，f 一) 定义的区域r ( p ，p f ) 称为a 的r o n o i 区域，j i p 9 4 表示p 和留两点之间的距离， 由r ( p ，p f ) ( f = 1 2 ，1 ) 及其边界给出的对平面的分割称作s 的v o m n o i 图，简 称v o m n o i 图，s 中的点a ( f ；1 2 ，n ) 称为生成元( 或母点) ，将图中的边界称 为生成元a 和p ，之间的、b r o n o i 边，不同、研o n o i 边的交点称为v o r o n o i 顶点。 该定义中p 和吁之问的距离陋一训可以是欧氏距离，也可以是其它距离( 如 厶距离等) ，图l 所示为不同距离下的v o m n o i 图。 ( a ) 欧氏趴离下的f o j 剀( b ) l j 距高下的v o m 肋i l 鳘| 幽1 小趴离 f 的、h o n o i 幽 筘8 “ 洲北帅范人学碳i j 研究生学位论义 | 芏i 中黑点为生成儿t 訇1 1 线为v o r o n o i 边 v b r o n o i 图的基本性质【6 】如下： 性质1 尺( p ，p t ) n r ( p ，p ) = 妒( f 一，) 性质2n 个点的点集s 的v o r o n o i 图至多有孙一5 个r o n o i 顶点和3 n 一6 条 、，o r o n o i 边。 性质3 每个v o r o n o i 顶点恰好是三条v o m n o i 边的交点。 以上性质具体证明详见文献【6 】。 2 1 2v o m 肿i 图的主要生成法 构造平面点集s 的、，0 f o n o i 图的算法在最近几十年中得到了快速的发展，主 要有半平面的交、随机增量算法、分治法、平面扫描算法和离散构造算法1 8 ，9 ，1 0 ，1 1 】 等。以下简要介绍几种常用算法的基本思路。 1 半平面的交：利用、研o n o i 图的定义，构造，l 一1 个半平面的交，得到点 a 的、，o r o n o i 区域，逐点构造各点的、b n o i 区域边得v o r o n o i 图。 2 随机增量算法：逐个添加生成元( 或母点) ，每次添加后更新v o t o n o i 边。 3 分治法：按点的x 坐标的中值分割点集s ，至每个子集含生成元数小 于或等于4 。每个子集各自产生、b m i 图后，不断合并相邻子集的r o l l o i 图， 直至得到点集s 的v o r o n o i 图。 4 平面扫描算法：通过平面上的一条扫描线由左至右扫描。当扫描到某一 部分时，就构造该部分的v o r o n o i 图，直至扫描终止。 5 离散构造算法：给每个生成元分别指定不同的颜色并以其为圆心，匀速 的向外扩张画圆至整个平面，不同颜色的区域相遇产生的交线图即为v o m n o i 图。 2 2 城市v o m n o i 图 2 2 1 城市v o r o n o i 图的定义及其简单性质 城市v o m n o j 图是根据已知点集对具有交通路线的岛平面施行的一种分 割，它是基于城市距离下的v o f o n o i 图。0 s w i na j c h h o l z e r 等给出了城市距离 的定义，然后根据城市距离定义了城市v o r o n o i 图。其主要定义如下： 掰9 撕 | 北帅扎人学f 顶l 研究生学位论义 设c 为交通网络，要求c 中交通路线为水平方向或垂直方向，允许在c 的 任意点处自由进出交通网络，并且c 中各条交通路线具有相同的速度，设为v ， 平面上其它区域速度为1 。该模型由a b e l l a ne ta 1 f 7 j 首次提出，城市v o r o n o i 图 正是基于该模型定义的。 对于具有交通网络c 的l 1 平面上的任意两点石，y ，q c ，y ) 表示两点x ，y 之间行驶时间最短的路径，称为x ，) ，之间的最快路径。通常情况下，最快路径 包括l l 度量下步行的直线段和在交 通路线上的行驶路段( 见图2 ) 。用 d c o ，y ) 表示行驶q c ，y ) 所用时 间。 a 一= “，： 一；1 4 ：j_ 。一：l 。曩 ；审 1 1 i 二” 黔曩r l 圉2 最快路径图中租黑线是交通路线，虚线鬏不 定义2上1 平面上任意两点p ，q 之间 ；，y 之间的鼹快路径，虚线旁边的数字表示行驶该 的城市距离定义为d c ( p ，q ) 。 段路程所精时间，设在交通路线l ：的速度恒为3 也就是说， 点p 到点q 之间的城市 距离是从点p 到点q 的最快路径的时间花费。在这里，城市距离是一个度量函 数，证明见文献【1 】。 定义3 设s = 如1 ，3 2 ，s 。 为b 平面上的点集，c 为交通网络，其中交通网 络上的速度恒为v “，0 ) ，平面上其它区域 速度为1 ，由 r e 占( 毛) i 缸i d c o ，墨) o ， 平面上其它区域速度为1 ，由 4 ，p 盘( p f ) 罱 p l d c ( p ，p 1 ) d c ( p ，p ，) i 啦j 定义的区域_ ，阳( p f ) 称为生成元p f 的变速 i ：6 o沁厶 厂、 n ：6 - ， )k ， ，。 城市f o o i 区域，由爿阳口( p i ) ( f 1 ，2 ，抖) 图6 变速城市“。图 凰中粗黑线是交通路线，粗黑线旁边 及其边界所给出的对平面的分割，称为以点 数字为该条变通路线上的速度，黑点是 n a = 1 ，2 ，1 ) 为生成元( 或母点) 的变速城 生成几，细线是变速城市v 0 。i 边 市v o m 肿i 图( 见图6 ) ，其中d c p ，p f ) 表示 点l d 到生成元p f 的城市距离。图中的边称为变速城市、b m n o i 边。 3 2 变速城市v o r o n o j 图的基本性质 性质6 1 度量下的v o m n o i 图是变速城市v o r o n o i 图当在各祭交通踌线上速度 均为1 时的特例。 性质7 城市v o r o n o i 图是变速城市v o m n o i 图当在各条交通路线上的速度相同 时的特例。 汕北师范人学麒i 。研究生学位论义 性质8 区域彳，e 口q f ) 由l 平面上到生成元p j 的时间比到s 中其它点的时问都 少的点构成。 性质9 设s = p 1 ，p 2 ，p 。) ，则爿彻( p i ) ( f 一1 ，2 ，n ) 是对平面的一种分割。 证明：首先证明当i tj 时，爿瑚( p i ) n 4 比口( p ) = 庐 若存在p o 爿瑚( p i ) n 爿唧( p j ) ，由p o 4 陀口( p f ) 和定义4 ，对任意 七一f ，1 s 七s 珂，有d c ( p o ，p f ) d c ( p o ，p ) ，所以，d c ( p o ，p i ) d c ( p o ，p i ) 。 同理， 由p o 爿，明q ) 可得d c ( p o ，p ) o 是一段较小的时间，那么t 时间后与 图1 0 这两种不同生长方式对应的结晶区域的形状如图1 l 。 4 3 6 变速城市v o m n o i 边的近似抽取 根据实际需要，当画出不同颜色区域的变速城市v o r o n o i 图后，通常还应 以某种颜色( 如黑色) 画出各区域的边界，并将其余部分置为某一背景色( 如 白色) 。这个过程称为变速城市v o m n o i 边的近似抽取。具体做法如下： s t e p l 对不同颜色区分各个区域的变速城市v o m n o i 图进行横向( 如从左 到右) 及纵向( 如从上到下) 扫描。在扫描过程中，如果某像素与其后续像素 颜色不同，就将该像素( 也可以是后续像素) 置为指定的颜色。 s t e p 2 扫描完成后，各区域边界便以指定的颜色画了出来。 s t e p 3 进行全 屏扫描，即保留指定 颜色像素点，其他颜 色的像素点全部置 囝1 2 为背景色。 这样，指定颜色像素点的集合便为变速城市v o r o n o i 图各个不同区域的边 界。扫描过程如图1 2 所示。 4 4 变速城市v o m 帅i 图的离散生成算法描述 输入：生成元集s ； p l ，p 2 ，p n ，交通网络图m 竹r 七； ，咋) i h y ，f ；1 2 ，l ， 其中z f 表示交通路线，u 表示上的速度，y 一 印出i f 1 ，2 ，) 。 输山：以s 为生成元，以c 为交通网络的变速城市v o m n o i 圈 s t e p l 建立链表l i s t l ，用米存放生成元p j ( i = 1 ，2 ，n ) 的数据，每个结点存放一个 生成元的数据，包括生成元的横坐标，纵坐标，颜色值以及指向下一个结点的指针n e x l - s t e 口2 将屏幕初始化为自色( 背景色) ； s t e p 3 对每一个生成元p f 指定颜色c j ( f - 1 ，2 ，h ) ，对速度为印e e 西( ，= 1 ，2 ，) 的交 通路线指定颜色c 。+ f ，要求c f o ；l ，2 ，h + ) 互不相同； s i e 口4 将交通网络c 在屏幕上画山； s i e d 5 建立链表l i s t ，其每个结点数据同l i s l l ，j j 米存放新生i 支点的数据； 镛2 2 “ 河北师范人学坝i ：研究生学位论义 s i e p 6 定义指针p 指向i i s t 头结点； s t e p 7 定义标j 占性布尔类型数组胁庸【删r l 也4 r 】( x m a x 为屏幕横坐标最人值 y m a x 为屏幕纵坐标最人值) ，川米标记已被访问过的交通路线上的点：定义结构类型数 编d 蟠衅】，其中数组中每个元素存放交通网络中不同交通路线的颜色蟠【f 】c d 如r 及其 速瘦c a s m 3 p e e d ； s t e p 8 当l i s t 不空时，循环执行以下步骤 使指针变量p 指向l i s t 的头结点； 将l i s t 置空； 当p 不为空指针时，执行如下循环 ，d r o = 0 ；f y 0 ) f o 嘶ty = y o ；y s e t p i ) c e l ( x 0 ，y ，c o l o