（基础数学专业论文）线段障碍城市voronoi图的结晶生成.pdf

学位论文原创性声明 本人所提交的学位论文卿私锄孙断炒毋孙苁望是在导师的指 导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用 的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：垓 壤 乒呻年，月扣日。 学位论文原创性确认书 。舶鼽执 学生牺提交的学位论文勿裆鳓5 嘶肛删周叼，是在 本人的指导下，由其独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，该论文不包含任何其他个人或集体已经发表 或撰写过的研究成果。 指导教师( 签名) ：否骼 矽7 年j 月加日 i | i 北9 i | j 范人学顾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 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 o r o n o i 图、线段障碍城市v o r o n o i 图、结晶生长 河北师范大学硕i ：研究生学位论文 a b s t r a c t t h ec i t yv o r o n o id i a g r a mw i t h1 i n es e g m e n to b s t a c l ei st h ed e v e l o p m e n t o ft h ec i t yv o r o n o id i a g r a m ，w h i c hi sb a s e do nap l a n ed i s t a n c e厶a n d r e q u i r e st h et r a f f i c1 i n ei so nt h el e v e lo rv e r t i c a la n dam o d e lw h i c hc a n p a s si na n do u tt h et r a f f i cn e tf r e e l y h o w e v e r ，i nt h er e a lw o r l d ，t h e d i r e c tt r a n s i tw i t h o u to b s t r u c t i o ni dn e a r l yi m p o s s i b l e m o s to ft h et r a f f i c n e t sa r ed i v i d e db ya 1 1k i n d so fo b s t r u c t i o n ，i nw h i c ht h es e g m e n to b s t a c l e i st h em o s ti m p o r t a n ta n dm a n yo b s t a c l e sc a nb eh a n d l e da ss e g m e n to b s t a c l e s ， t h u s ，i ti sn e c e s s a r yt os t u d yt h ec i t yv o r o n o id i a g r a mw i t hl i n es e g m e n t o b s t a c l e t h i st e s tg i v e st h ed e f i n it i o n ，t h en a t u r es o f t i er e l a t i v es i m p l ep r o v e m e n t a n dc r y s t a lg r o w t ha l g o r i t h ma n di t sp r a c t i c ep r o g r a m ，w h i c hi ss i m p l ea n d n e e d n tt h ec o m p li c a t e dd a t as t r u c t u r e i tc a nb eu s e dt oa n yo b s t a c l eo f d i f f e r e n tg e o m e t r yf i g u r e s t h et e s ta l s op r o v i d e ss o m ee x a m p l et oe x p l a i n t h ep r a c t i c eo ft h ec i t yv o r o n o id i a g r a mw i t hl i n es e g m e n to b s t a c l e ，w h i c h s o l v e st h ep r o b l e mo ft h ed i v i s i o no ft h eo b s t r u c t i o np l a n ea r e ab a s e do nt h e 厶d i s t a n c e t h et r a f f i cl i n eo nl e v e la n dv e r t i c a la n dt h ec o n s i d e r a t i o n o ft h et i m ed is t a n c e k e l n v o r d s ： v o r o n o id i a g r a m ，t h ec it yv o r o n o id i a g r a m ，t h ec i t yv o r o n o i d i a g r a mw it hli n es e g m e n to b s t a c l e ，c r y s t a lg r o w t h 2 河北师范人学顾i ：研究生学位论文 第一章绪论 1 1v 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 o r o n o i 图描述。早在1 6 4 4 年， d e s c a r t e s 就使用了类似v o r o n o i 图的结构对太阳系进行分割；第一个有关v o r o n o i 图的概念是在p e t e rg u s t a vl e j e u n e ( 1 8 0 5 1 8 5 9 ) 与6 e o r g e sv o r o n o i ( 1 8 6 8 1 9 0 8 ) 著作里出现的：数学家d i r i c h l e t ( 1 8 5 0 ) 和v o r o n o i ( 1 9 0 7 ，1 9 0 8 ，1 9 0 9 ) 在正有限二次 型的研究中正式介绍了v o r o n o i 图的概念，o i r i c h l e t 论述了二维和三维的情况，而 v o r o n o i 论述了m 维的情况船”，从那以后，人们开始考虑在空间中放置一系列点由 欧氏距离决定平面分割的结构，并称之为d i r i c h l e t 剖分或是v o r o n o i 图。 1 0 0 多年来v o r o n o i 图被应用在与几何信息相关的各个领域，尤其是计算机在图 形图像处理方面的广泛应用，它成功地解决了计算机几何上找最近点，求最大空圆， 求n 个点的凸包，求最小生成树等问题，同时v o r o n o i 图在计算机辅助设计、地理信 息处理、计算机图形学、模式识别、机器人、生态研究、城市规划、最优配置、物理 学等方面都有广泛的应用。尤其是进入8 0 年代，v o r o n o i 图在不同科学领域被发现、 研究和应用达到高潮，并有许多人对v o r o n o i 图进行综述和总结“1 ，关于v o r o n o i 图 在其它领域中的应用，不再重述。 1 2 问题提出的现实背景及研究现状 城市v o r o n o i 图基于a b e l l a n a se ta l 具体模型：平面的度量是厶度量，交通 网络路线c 是水平方向或者垂直方向，各交通路线上的速度恒定( 不妨设为v ) ，平 面上其它区域的速度为1 ，城市v o r o n o i 图中使用了时间距离的概念，可以在c 的任 意点处自由进出交通网络，由于交通路线均为横或竖又引入了时间距离的概念，从而 使v o r o n o i 图在解决城市交通问题中有了更好的方法。o s w i nh i c h h o l z e r ”。等在具有 交通路线的厶平面( 即平面上任意两点p ( x 。，y 。) ，g ( 工：，y ：) 之间的距离定义为 o ( p ，g ) = k - x 2 i + l y 。- y ：1 ) 上，以平面上任意两点之间花费的最短时间为“距离”， 3 i 北师范人学硕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 图的设想。 对于构造方法的确定，是基于结晶生成与生成元的个数、交通路线和障碍的条 数无关，同时平面上的度量是厶度量和结晶4 一邻域生长方式相吻合，至今未见在该 方面的应用研究。 1 3 论文的研究内容 首先对障碍城市v o r o n o i 图的给出其定义、性质及相关证明，并且给出基于结 晶生长方式“1 构造线段障碍城市v o r o n o i 图的基本思想和生成算法，并用v c + + 编程 实现。最后给出了应用实例说明。 1 4 论文的结构安排 本文共分为六章。 第一章绪论，简单介绍了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 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 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 o r o n o i 图的基本概念及性质。 2 1v o r o n o i 图 2 1 1v o r o n o i 图的定义及主要基本性质 v o r o n o i 图由给定的一个有限点集，根据最近成员的位置关系将空间分成些小 区域，平面上一个点集p 的v o r o n o i 图是对平面的一个划分。其中每个分区表示一些 点的集合，这些点到p 的一个元素比到其它元素距离更近。其数学定义如下； 定义1 设s = 佃。，p 2 ，n ) 为平面上的点集将由 v ( p ，) = n p l d ( p ，p i ) d ( “p j ) ，( i = 1 ，2 ，n ) 所给出的 州 对平面的分割，称为以n ( i = 1 ，2 ，n ) 为生成元( 或母 点) 的v o r o n o i 图，简称为v o r o n o i 图( 图1 ) ，其中d ( p ，p 1 ) 为p 和p 。问的欧式距离，图中的边界称为生成元p ，和p ，之 间的v o r o n o i 边，不同v o r o n o i 边的交点称为v o r o n o i 顶点。 该定义中p 和q 之间的距离d ( p ，q ) 可以是欧氏距离， 也可以是其它距离( 如厶距离等) 如图1 、2 所示，其中图 中黑点为生成元，细线为v o r o n o i 边。 v r o n o i 图的基本性质嘲如下： 圉l 欧氏距离下韵v o r o n o i 图2l i 距离下的v o r o a o i 圈 性质1 生成元p f 的v o r o n o i 区域矿( p 。) 无界的充分必要条件是n b c h ( p ) ， 其中，b c h ( p ) 表示生成元集合s 的凸壳边界。 性质2 每个v o r o n o i 点恰好是三条v o r o n o i 边的交点。 性质3 点集s 中的点p ；的每一个最近临近点确定v ( p ，) 的一条边。 2 1 2v o r o n o i 图的主要生成法 v o r o n o i 图的许多应用，促使研究人员成功地设计出多种构造v o r o n o i 图的算 法，如半平面的交、增量构造方法、分治法、离散生成算法、结晶生成算法等嘲n 岫”， 以下做一简要的介绍。 河北师范人学硕l ：研究生学位论文 ( 1 ) 半平面的交 利用v o r o n o i 图的定义，对点集s 中的每一个生成元点p ，o = 1 , 2 ，n ) ，找出该 点与其它所有生成元点之间的垂直平分线，每条垂直平分线将整个平面分为两个半平 面，这样就得到了n 一1 个半平面，这n 1 个半平面的交，构成弹个多边形区域，每个 点p j ( f = l ，2 ，疗) 分属不同的多边形区域，这就是点p 。( f = 1 ，2 ，n ) 的v o r o n o i 区域。 ( 2 ) 增量构造法 假设点集s = q 。，p ：，n ，并设已经构造出膏( 七 0 ) ，平面上 其 它区域速度为 1 ， 由 r e g ( p ，) = x l d c ( p ，p i ) d c ( p ，p j ) ，i j ) 定义的区域 r e g ( p ) 称为生成元p j 的城市v o r 9 n o i 区域，由 r e g ( p i ) ( i = 1 , 2 ，n ) 及其边界所给出的对平面的分 图7 城市v o r o n o i 图 割，称为以点p = 1 ，2 ，n ) 为生成元( 或母点) 的城市v o r o n o i 图，记为v ：( s ) ，其 中d c ( p ，p i ) 表示点p 到生成元p t 的城市距离。图7 是由6 个生成元( 图中黑点) 、4 条横向交通路线( 蓝色横向线) 和6 条竖向交通路线( 蓝色纵向线) 构造的城市v o r o n o i 图，其中黑色的细线代表v 边。 依上述定义，不难得到以下性质： 性质1 城市v o r o n o i 边上任一点到两相邻生成元所用时间相同。 性质2 设p r e g ( p f ) ，如果p o 位于从p 到p ，的最快路径上，则p 0 r e g ( p i ) 。 具体证明详见文献嘲。 性质3 r e g ( p ，) o = l ，2 ，以) 是道路连通区域。证明详见文献。”。 2 3 2 城市v o r o n o i 图生成的基本思想o ” i j 北师范人学顾i - l 旰究生学位论史 o s w i na i c h h o l z e r 嘲等给出的城市 v o r o n o i 图的基于抽象v o r o n o i 图的生成 法的基本思想：每个生成元在0 时刻发射 波形为厶一圆、以速度l 2 向外扩展的前 波，并且前波运动在两个波形的接触点处 停止。由于在交通路线上的速度比较快， 因此当前波触及到交通路线时，绕生成元 逐渐扩展的厶一圆的形状就会发生改变。 设后o ，f ) 表示以生成元s 为中心，以时间t 图g 耐心圆k ( s 。0 以及f 中图形的生成， 其中黑多边形是f 中的图形形 为半径的圆，最终目的是把k ( s ，f ) 解释为某一个图形集f 中的图形在不同时刻t 的扩 展图形，如图8 所示。， 构造f 的具体做法是：考虑前波在传播过程中在交通路段、网络节点以及生成 元处产生的图形，构造出非冗余图形集合f ，然后对f 中的图形进行调整，使f 中 图形的直骨架满足抽象v o r o n o i 图的条件，最后通过生成抽象v o r o n o i 图得到城市 v o r o n o i 图，如图9 所示。 图9 基于抽象v o r o n o i 图的城市v o r o n o i 图，其中黑点 是生成元，粗黑线是交通路线。细折线是城市v o m n o i 边 河北师范人学硕i ：研，生学位论文 第三章线段障碍城市v o r o n o i 图 3 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 i 图中，假想在平面上的度量是厶度量的自口堤下，可以在交通网络的任意点处 直接进出交通网络，而客观上障碍的存在是不可避免的，由此，“可以在交通网络的 任意点处直接进出交通网络”的假想不合现实。在现实中，需要考虑障碍的存在，在 进出交通网络时，必须绕过障碍，而不能直接进出交通网络。与城市v o r o n o i 图相比， 具有障碍的城市v o r o n o i 图能够更加真实地反映城市交通的实际情况。下面给出它的 数学定义： 定义：设s = 如。，p ：，p 。 为l l 平面上的点集，c 为平面上仅有水平方向或者垂 直方向的l l 度量的交通网络，r = g 。，g ：，g 。) 为l l 平面上的m 个互不相交的障碍 图形。其中在交通网络上的速度为v ，l ，平面上除g ，( i = 1 , 2 ，m ) 区域外其它区域的 速度为1 ，将由r c g b ( p i ) = b i d 。( p ，p i ) d b c ( p ，p j ) ，i j j 所给出的对平面的分割，称为 以点p l ( i = 1 , 2 ，n ) 为生成元，以g 。( i = l ，2 ，m ) 为障碍的城市v o r o n o i 图，记为 v 0 ( s ) ，当障碍g 。为线段时，则称线段障碍城市v o r o n o i 图。 3 2 线段障碍城市v o r o n o i 图的性质 按照障碍城市v o r o n o i 图的定义可知：障碍城市v 边上任一点，到相邻两生成 元所用时间相同( 包含绕过障碍的时间) 。同时，某个障碍可能全部或部分包含在某 个点的障碍城市y 区域内，也可能成为障碍城市y 边或障碍城市矿边的一部分。 障碍城市v o r o n o i 图还具有如下特性： 性质1 城市v o r o n o i 图是障碍城市v o r o n o i 图在无障碍情况时的特例。 性质2 区域，曙。q ，) 是厶平面上到点p ，的时间比到s 中其它点的所用时间都 少的点的集合。 性质3 r e g b ( p ，x i = 1 j , - - - , p ) 和线段障碍图形是对平面的分割即 r e g 。( n x i = 1 , 2 ，n ) 及线段障碍图形将厶平面分割成互不相交的n 部分。 事实上，只需证明不同点的v 区域互不相交且平面上非障碍区域上任一点在不 1 1 i 町北帅范人学硕 ：研究生学位论空 i 司的v 区域上。 证明：首先证明当f 时，r e 9 6 ( p ，) n r e g b ( p ，) = 矿a 若存在p 0 r e 9 6 ( p i ) n r e 9 6 ( p ，) ，由p o r e 9 6 ( p f ) 和障碍城市v o r o n o i 图的定义 可知，对任意k i , l k n ，d 如( p o ，p ，) d k ( p o ，p t ) ，所以，d 如( p o ，p f ) d 如( p o ，p ) 。 同理，由p o r e 9 6 ( p ，) 可得d k ( p o ，p ，) d k ( p o ，p f ) 。 所以r e 9 6 慨) n r e g ( p ，) = a 下证厶平面上任一点在某一障碍城市v 区域上。 设p 为厶平面上任一点， 不失一般性，假定 丸( p ，p 。) 丸( p p 2 ) s s 丸( p ，p 。) 。如果丸( p p 。) 如( p ，p 2 ) ，由上面的假设可 知丸( p ，p i ) d k ( p ，p i j i = 2 3 ，n ) ，由障碍城市v o r o n o i 图的定义可知 p r e 9 6 ( p t ) 。 如果丸( p ，p 1 ) = 丸( p ，p 2 ) 如( p ，p 3 ) ，则p r e 9 6 ( p 1 ) r 、r e 9 6 ( p 2 ) ，即p 在p l 和p 2 间的v 边上。 依次类推，如果丸( p ，p 。) = 丸( p ，p 2 ) 一一吐( p ，p 。) ，则p 在r e 9 6 ( p 。) ， r e g 。( p 2 ) ，r e g 。( p 。) 中任两个矿区域之间的矿边上，即p 为上述矿边的交点 综上所述，厶平面上的任一点，或属于某个障碍城市矿区域，或在某个障碍城 市y 边上，或为若干个障碍城市y 边的交点。所以r e g 。q ，x i = 1 ，2 ，行) 将厶平面分割 成互不相交的n 部分。 河北师范人学硕l ：研究生学位论文 第四章线段障碍城市v o r o n o i 图的结晶生成 线段障碍城市v o r o n o i 图的生成算法是一种基于结晶生长方式的生成算法。结 晶生长理论已有1 0 0 多年的发展历史，它涉及到的领 域非常广泛，人们已在各个领域中建立了许多晶体生 长的模型。在二维平面上，最常见的生长方式是以4 一 邻域或8 邻域方式生成，如图1 0 所示，其中图a 的红 色区域是以生成元像素( 黄色点) 为中心，在上下左 图l o 结晶生长方式的 右4 个方向上的邻接像素点，称其4 一邻域区域；图b 4 一邻域和8 一邻域 的红色区域是以生成元像素点为中心的8 一邻域区域 ( 是以屏幕某象素点为中心，由它的上下左右4 个方向上的邻接象素点以及左上，右 上，左下，右下4 个方向上的邻接象素点组成) 。 为了便于本文的算法的实现，现引用4 一邻域生长方式 并对其进行扩充，图1 l 中给出了生成速度恒定( v 2 z ) 时生成元生长的图例。其中标注为1 的像素点是生成元的生 长点，即结晶过程的第一次生长；标注2 的像素点是由第一 次生长得到的生长点( 图中标注l 的鼽分别按给定的速要盐罘磊篥羹曩篡 度( 本例v = 2 ) 以4 一邻域方式生长，即为结晶过程的第2 次生成。当然还有些特殊情况，如在生长过程中，若当前像素点在其生长方向上的前 一像素点为不可逾越的障碍，或当前像素点和生长方向上的前一像素点生长速度不 同，或是当前像素点在其生长方向上的前一像素点已生长过等情况，将在算法中予以 介绍。 4 1 线段障碍城市v o r o n o i 图结晶生成法的基本思想 先初始化屏幕为白色，将所有的障碍指定一种颜色，将所有交通路线指定为异 于障碍颜色的另一种颜色，对每个生成元指定不同的颜色且与障碍和网络路线颜色不 同。然后以每个生成元为生长点，以该生成元的颜色在交通路线上以速度，在平面 上其它区域以速度1 ，按各自4 一邻域方向结晶生长。各生长点在生长过程中，不同 的生长区域一旦相遇，它们将停止朝向彼此方向生长，而其它方向继续生长，同时， 当生长区域遇到障碍时，朝向障碍的方向停止生成，而其它方向继续生长。不同的生 河北师范人学顾l ：研究生学位论文 长区域及障碍产生的交线即为障碍城市v 图的边界。 4 2 线段障碍城市v o r o n o i 图结晶生成算法 线段障碍城市v o r o n o i 图结晶生成算法： 输入：生成元集s = 缶，p ：，p 。 ，交通网络图和直线障碍图形g 。 输出：以s 为生成元，以c 为交通网络，以g 为障碍的线段障碍城市y o r o n o i 图( 研。 s t e p l 建立链l i s t ，用来存放生成元点p t o = l ，2 ， ) 的数据，并对每个生成 元p 。( f = l 2 ，n ) 随机生成一种颜色( 不同于交通网络上的点及障碍图形上点的颜 色) ；其中凰f 的每个结点存放一个生成元的数据，包括生成的横纵坐标、颜色值以 及指向下一个结点的指针n e x t ： s t e p 2 建立链表1 i s t l i n e c h s h i 一用来存放横向交通路线链表；建立链表 1 i s t l i n e c h s h i 用来存放竖向交通路线链表； s t e p 3 将屏幕置为白色( 用c o = o x o o f f f f f f 表示) ； s t e p 4 将交通网络c 输入屏幕，并指定交通网络上每点的颜色为x i a n l u s e ； s t e p 5 将随机产生线段障碍图形输入屏幕，并指定所有障碍的颜色为黑色即 z h a n g a i s e = o x 0 0 0 0 0 0 ； s t e p 6 输入各个结点即生成元点。 s e t p 7 同样使用链表l i s t ，来存放新画过的点( 新的结晶生长点) 。 s t e p 8 当l i s t 不空时，循环执行以下步骤 定义指向l i s t 首结点的指针p ，并清空l i s t 链表； 矿p 不为空 ( 处理左点 i fp 所指结点左边像素点的颜色为白色 用当前点的颜色为其左边像素点着色， 并将其左点作为新的生长点存入l i s t 链表中 河北师范人学顾i 。研究生学位论文 ) e l s e i f ( p 所指结点左边像素点的颜色为交通路线颜色) f o r ( i = 1 ；i _ ，；f + + ) 用当前结点的颜色为其左边像素点着色， 并将其左点作为新的生长点存入l i s t 链表； 申请存放p 左点的结点指针p t ： 矿( p t 所指结点的左点的颜色和交通路线颜色不同) b r e a k ； ) e l s ei f o 所指结点左点的左点在交通路线上) f o r ( k = 0 ；七 n e x t ： 删除已生成的前一像素点； ) s t e p 9 纵向及横向扫描屏幕，若某一像素点颜色与其后继像素点颜色不同，将 1 s 河北师范人学硕i 研究生学位论义 其置为黑色( o x f f 0 0 0 0 0 0 ) ： s t e p l o 横向( 或纵向) 扫描全屏幕，保留黑色像素点的颜色，其它像素点颜 色均置为白色。 s e t p l l 生成元及v 图的抽取。算法结束 该算法已在v i s u a lc + + 6 0 环境下实现，以下通过图例予以说明。 舸，。2 0 个生成元、3 0 条随机线段障碍和2 条横向、3 条竖向交通路线的线段障碍城市v o r o n o i 图图例 i | 1 北师范人学颂i 研究生学位论文 阿，1 0 0 个母点、2 0 0 个线段和3 横向4 竖向交 崮通路线的线段障碍城市v o r o n o i 图图例 4 3 线段障碍城市v o r o n o i 图结晶生成算法实现的关键技术 按算法设计，需对生长点的每个4 一邻域邻接点的颜色进行判断，分三种情况进 行讨论： ( 1 ) 若生长点生长方向上的邻接点颜色为白色，则将该邻接点作为新的生长点， 存入生长点链表，同时，用生长点的颜色为该邻接点着色； ( 2 ) 若生长点生长方向上的邻接点颜色为蓝色( 即交通路线色) ，则按交通路 河北师范人学硕i ：研究生学位论文 线的速度生长，在此需考虑两种情况：一是，当生长点生长方向上交通路线像素个数 不小于在交通路线上的生长速度时，需将自邻接点开始的生长方向上生长速度个像素 点作为新的生长点，存入生长点链表，同时，用生长点的颜色为这些点着色；二是， 当生长点生长方向交通路线像素个数小于生长速度时，只将生长方向上的交通线路上 的点，作为新的生长点，存入生长点链表，同时，用生长点的颜色为该邻接点着色； ( 3 ) 若生长点生长方向上的邻接点不为白色，也不为交通路线颜色，则需判断 生长方向上邻接点的邻接点( 即生长点在生长方向上的第二个点) 的颜色，若该点为 交通路线色，则重复上述情况( 2 ) 。 说明：在算法中情况( 3 ) 是不可缺少且十分重要的，是因为生长点生长方向上 的邻接点有可能已被同种颜色的其它生长点生长，从而影响交通路线方向上的正常生 长。可以通过图1 4 所示的生成元在进入交通路线生长时的模拟过程。其中图中蓝色 区域为交通路线，红色为生成元。图a 为初始时刻，初始生成元标记为0 。4 一邻域 图1 4 生长点进入交通路线时的模拟生长 结晶生长过程按左、右、上、下的顺序生长，则生成元0 经一次结晶生长，如图b 所示，产生了新的生成元1 、2 、3 、4 ，再次生长时，将按照l 、2 、3 、4 的顺序继续 生长，1 生长了5 、6 、7 ，2 生长了8 、9 、1 0 ，当3 生长时，由于左、右、下均已被 其它生成元生长，只能生长上结点1 1 ，而此时在交通路线上的生成元4 ，由于其左右 己被l 和2 生长，无法实现在交通路线的快速生长，而只能生长其下结点，这就使得 在横向交通路线上，按照左右上下的顺序无法实现快速增长( 但对于竖向交通路线可 以) 。我们可以想象一下，以向左生长为例，如果左边的点已经被生长，有两种可能： 一是被其它颜色的生成元生长；二是被相同颜色的生成元扩展( 如上例中4 的左点被 l 扩展) 。如果是第一种情况，则此生长点在此方向的生长结束；如果是第二种情况， 从上面图中可以发现，虽然4 的左点被l 生长，但是由于其左点的左点是生长方向上 的交通路线上的点，应该按照交通路线上的生长速度生长。所以，不考虑情况( 3 ) ， 1 8 河北师范大学硕i 。研究生学位论文 就会提前结束生长点在该方向上的正常生长。 4 4 与已有算法的比较 通常可以处理障碍问题的算法有高速前进法、离散生成法、几何划分法、冒泡 算法，它们的优缺点已在2 2 2 中介绍。 本文扩展了o s w i na i c h h o l z e r 等给出的城市v o r o n o i 图的定义，所给出的算法 解决了带障碍的城市v o r o n o i 区域划分问题，该算法较其它算法有明显的优点； ( 1 ) 算法实现与生成元的形状、交通路线条数、障碍的个数和形状以及它们的 具体位置无关； ( 2 ) 算法实现与生成元的个数无关，因此，增加生成元的个数基本上不影响图 形生成速度； ( 3 ) 该算法在构造生成元个数较多，障碍较多的城市v o r o n o i 图方面具有显著 优势； ( 4 ) 这是一种很好的可视生长过程的划分算法。 本算法仍存在不足之处。如：算法的时间复杂度仍与屏幕上的像素点个数有关， 这使得算法在效率提高上有局限性；再如，对交通路线的处理仅限于横向和竖向两个 ，一j i 句等。 河北师范大学硕i 研究生学位论立 第五章应用举例( 邻近就医问题) 这个问题类似于传统的“入学问题”。在一个交通繁杂、人口密集的城市里，若 某人突发疾病，要尽快找到医院就医，就要考虑到哪所医院用的时间最短一这是障碍 城市v o r o n o i 图的一个应用。我们只需以每个医院为生成元，在障碍城市v o r o n o i 图中，找到病人所在的v o r o n o i 区域中的医院即可。 下图1 5 是石家庄市区的一小区域，其中有四所医院( 图中标识) ，图中蓝色线 路是“民心河”。我们抽取其中四所医院，五条横向和四条纵向马路( 蓝色的线条) 及一条河流，且考虑到裕华路和体育南大街这两条主干路，通行车辆较多，不可随处 自由进入，故将其两边均加设护栏( 黑色线条) ，抽取后的图形如图1 6 所示； 图1 5 石家庄市区部分交通路线图 加i fl 护 芒 二k 邕的横iq 变逶缱 的 交 i 零 通 线 、伊 图1 6 抽取出的蓝色马路、黑色护栏和黑色河流及四所医院 2 0 河北9 巾范人学硕f + 研究生学位论文 设图1 6 中蓝色交通线上行速为3 ，其它地方向( 除黑色的障碍外) 行速为1 时， 以四所为生成元的障碍城市v o r o n o i 图为图1 7 。分别到四所医院所用时问最短的城 市v 区域为图1 8 中黑色曲线所围区域。 1i 飞 i ll l 、 、一 _ 一 i 、 图1 7 图中黑点为生成元，蓝色线为交通路线，黑色线为障碍 图1 8 左图带蓝色交通路线的效果图；右图为抽取出蓝色交通路线的效果图 河北师范人学硕i ：研究生学位论文 6 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 i 图扩展到障碍城市 v o r o n o i 图，给出了线段障碍城市v o r o n o i 图的定义、性质及相关证明，同时，从4 一邻域结晶生长方式出发，给出了线段障碍城市v o r o n o i 图构造方法及实际应用。 6 2 进一步要研究的工作 随着科学技术的发展和计算几何应用的普及，城市v o r o n o i 图作为其重要的新 兴分支，可研究的问题还有很多。譬如，在构造城市v o r o n o i 图时，能否打破交通路 线只能是横向和竖向的限制，而能对任意方向的交通路线进行处理；再如城市交通中 常遇到单向交通路线行驶问题，则需要考虑交通路线的方向等，这些均能扩展线段障 碍城市v o r o n o i 图实际应用，均值得深入研究。 i 町北师范人学硕仁研究生学位论j 参考文献 1 s p a t i a lt e s s e l l a t i o n ：c o n c e p ta n da p p l i c a t i o no fg o r o n o id i a g r a m s h t s u y u k io k a b e ，b a r r yb o o t s ，k o k i c h i s u g i h a r a ，s u n gn o kc h i u 2 g v o r o n o i ，n o u v e l l e sa p p l i c a t i o n sd e sp a r a m s t e r sc o n t i n u sal at h 6 0 r i e d e sf o r m e sq u a d r a t i q u e s p r e m i e rm 6 m o i r e ：s u rq u e l q u e sp r o p r i e t e 6 sd e sf o r m e s q u a d r a t i q u e sp o s i t i v e sp a r f a it s ，j r e i n ea n g e w ，m a t h ，1 3 3 ，9 7 1 7 8 ，1 9 0 7 3 v o r o n o i ，n o u v e l l e sa p p l i c a t i o n sd e sp a r a m e t e r sc o n t i n u sal at h 6 0 r i ed e s f o r m e sq u a d r a t i q u e s d e u x i s m em 6 m o i r e ：r e c h e r c h e ss u rl e sp a r a l l 6 1 1 0 e d r e s p r i m i t i v e s ，j r e i n ea n g e w m a t h ，1 3 4 ，1 9 8 2 8 7 ，1 9 0 8 ：1 3 6 ，6 7 1 8 1 ，1 9 0 9 4 刘金义，刘爽，y o r o n o i 图应用综述工程图形学报2 0 0 4 ，第2 期 5 o s , i na i c h h o l z e r ，f r a n za u r e n h a m m e r 。a n db e l e np a l o p q u i c h k s tp a t h s ， s t r a i g h ts k e l e t o n s ，a n dt h ec i t yv o r o n o id i a g r a m d i s c r e t ea n dc o m p u t a t i o n a