（计算机应用技术专业论文）关于高阶voronoi图快速生成算法的研究.pdf

摘要 高阶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 图在实际应用中的推广。本文介绍了k ( 1 4 k n ) 阶最近点v o r o n o i 图，七阶最远点v o r o n o i 图和七阶有顺序v o r o n o i 图的定义及性质， 对k 阶v o r o n o i 图，k 阶有顺序v o r o n o i 图在生成算法方面进行了深入研究，并在分析 已有高阶v o r o n o i 图生成算法的基础上，依据“限定上界( f i x e du p p e rb o u n d ) ”定理， 提出了一种基于屏幕自适应分区实现局部查找k 个邻近点的快速生成七阶v o r o n o i 图以 及k 阶有顺序v o r o n o i 图的算法。除此之外，该算法还能用于生成多种不同形式的高阶 v o r o n o i 图。这种生成k 阶v o r o n o i 图的算法思路清晰，数据结构简洁，在保证图形效 果的前提下，生成速度得到了显著提高。该算法已在v i s u a lc + + 环境下实现，从而验证 了算法的有效性。 关键字；计算几何v o r o n o i 图高阶v o r o n o i 图自适应 i i i a b s t r a c t h i g h e r - o r d e rv o r o n o id i a g r a mi s a l l i m p o r t a n tg e n e r a l i z a t i o no fo r d i n a r yv o r o n o i d i a g r a m i th a sw i d e s p r e a da p p l i c a t i o n si nt h ep r o b l e mo ff i n d i n gk - n e a r e s tn e i g h b o r si na p l a n a rp o 硫s e t h o w e v e r , t h ep r e v i o u sa l g o r i t h m so fc o n s t r u c t i n gh i g h e r - o r d e rv o r o n o i d i a g r a mh a v ec o m p l e xd a t as t r u c t u r ea n dh i g ht i m ec o m p l e x i t y d u et ot h e s ef e a t u r e s h i g h e r - o r d e rv o r o n o id i a g r a mi sl i m i t e di np r a c t i c a lu s e t h i sa r t i c l ei n t r o d u c e st h ed e f i n i t i o n a n dp r o p e r t i e so fk - n e a r e s t ( 1 k n ) p o nv o r o n o id i a g r a m ，t h ek - f a r t h e s t p o m v o r o n o i d i a g r a ma n dt h eo r d e r e do r d e rkv o r o n o id i a g r a m a c c o r d i n gt ot h et h e o r e mo f f i x e du p p e r b o u n d ”，af a s ta l g o r i t h mb a s e do i la d a p t i v es e g m e n t a t i o ns c i i ia n dl o c a lv i e w o fk n e i g h b o r si sp r o p o s e d t h i sa l g o r i t h mn o to n l yc a nc o n s t r u c tm a n yk i n d so fd i f f e r e n t h i g h e r - o r d e rv o r o n o id i a g r a m ，b u ta l s oh a sc l e a ri d e a s ，s i m p l ed a t as t r u c t u r ea n di t s c o m p u t a t i o n a ls p e e di sn o t a b l yi n c r e a s e d ，o nt h ep r e m i s eo fh i g hd i a g r a mq u a l i t y f i n a l l y , t h i sa l g o r i t h mh a sb e e na c h i e v e di nv i s u a lc + + ，s ot h ev a l i d i t yo ft h i sa l g o r i t h mi s e a s i l y v e r i 6 e d 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 r yv o r o n o id i a g r a m h i g h e ro r d e rv o r o n o id i a g r a m a d a p t i v e i v 学位论文原创性声明 本人所提交的学位论文关于高阶v o r o n o i 图快速生成算法的研究，是在导师的 指导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡 献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：剖；五埔 a 口p 孑年r 月心日 指导教师确认( 签名) ：豕较丽参 么巾汐年，月日 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ：纠轻确 上嘞年r 月f 牛日 指导教师( 签名) ：丕坎丽夸 7 0 - o 莎年，月加日 1 1 绪论 v o r o n o i 图n 1 是计算几何的一个重要分支，在计算几何的理论研究和应用研究中起 着重要的作用。平面上由n 个点生成的v o r o n o i 图是一种非常重要的几何结构，许多涉 及求解与距离相关点集或其它几何对象的问题，最终都可归结为v o r o n o i 图的问题。 v o r o n o i 图在计算机辅助设计、模式识别、地理信息处理、城市规划、生态学、经济学、 天文学等诸多领域都有重要应用。它成功的解决了寻找最近点，最远点，求最大空圆， 求n 个点的凸包，求最小树等一系列的问题，在计算几何的理论和应用中发挥着巨大的 作用。 随着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 图扩 展到m 维空间，定义了高阶v o r o n o i 图等等。 高阶v o r o n o i 图作为普通v o r o n o i 图的一种重要推广形式，在理论和实际中起着相 当重要的作用。早在1 9 7 5 年，s h a m o s 和h o e y 就提出了k 阶v o r o n o i 图的概念瞳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 图领域研究的重点。 本文依据“限定上界( f i x e du p p e rb o u n d ) ”定理1 ，提出了一种基于屏幕自适应 分区和局部查找k 个邻近点的k ( 1 k n ) 阶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 图生成算法进行了分析并提出了一种基于 屏幕自适应分区和局部查找k 个邻近点的k ( 1 k n ) 阶v o r o n o i 图的快速生成算法；第 四章将本文提供的算法与以往一些v o r o n o i 图生成算法进行了效率比较，更加验证了该 算法的优越性。最后是文章的结束语、致谢、参考文献及附录。 2 第1 章v o r o n oi 图的简介 1 1 v o r o n o i 图产生的历史 v o r o n o i 图的历史是相当古老的。许多不同的自然结构都与v o r o n o i 图十分接近， 并且这些结构曾经被很多早期的科学家甚至普通人注意过。早在1 9 0 8 年，俄国数学家 g v o r o n o i 在对二次型的研究中首先使用了这种图1 ，后被计算机研究者称之为 v o r o n o i 图。1 9 4 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 图已被纳入计算几何的范畴，成为计算几何的一个重要分支。随 着计算机科学与技术的飞速发展，尤其是计算机在图像处理方面的广泛应用，使得计算 几何的研究，越来越受重视并日益蓬勃发展起来。计算几何在计算机辅助设计、计算机 图形学、数字图像处理、地理信息处理、机器人等许多领域都有重要应用。它已成功解 决了找最近点，求最大空圆，求n 个点的凸包，求最小树等问题。另外，v o r o n o i 图在 模式识别、生态研究、城市规划、最优化配置、物理学等许多领域也有广泛的应用。 1 2v o r o n o i 图的定义 定义1 ：设s = 协，p 29 * * e ，p 。) 为二维欧氏空间 ( 平面) 上的点集，将由 圪( p ，) = n p i d ( p ，p ，) 为二维欧氏空间( 平面) 上的点 集，r 是s 中任意k ( 1 k n ) 个点构成的集合， 定义r 的k 阶最近点v o r o n o i 区域为： 图26 0 个点的2 阶v o r o n o i 图 v ( r ) = p i v v f ，v ws - f ，d ( p ，1 ，) d ( p ，w ) ) ( 2 ) 其中a ( p ，1 ，) 是点p 到点1 ，的欧氏距离。显然，v ( f ) 是那些到r 中任意点，比到s r 中任 意点w 都近的点的集合。k 阶最近点v o r o n o i 图，是s 中所有这样的r 所形成的v o r o n o i 区域的并，记作砌气( s ) ，即场岱) = u v ( f ) ，f c s ，l r l = k 。当k = l 时，即为定义l 所 给出的v o r o n o i 图。k 阶v o r o n o i 图的顶点和边分别称为k 阶v o r o n o i 顶点和k 阶v o r o n o i 边。 5 k 阶最近点v o r o n o i 图有如下性质忉： 性质1 对平面上任意一点p ，如果 d ( p ，p 1 ) d ( p ，p k 1 ) a ( p ，p i ) = a ( p ，p k + i ) a ( p ，p k + 2 ) d ( p ，p 。) ( 3 ) 则p 必在k 阶最近点v o r o n o i 图的v o r o n o i 边上，其中a ，p 2 ，以为生成元。 证明：由( 3 ) 式，有 d ( p ，p 1 ) d ( p ，p k - 1 ) d ( p ，n ) d ( p ，p i ) o = 七+ 2 ，k + 3 ，刀) 故由定义2 知p e 矿( a ，陬l ，儿) 同理由 d ( p ，p 1 ) a ( p ，p l - 1 ) a ( p ，p h l ) d ( p ，p i ) ( f = k + 2 ，k + 3 ，万) 得p y ( p l ，一，p h ，p m ) 因此p y ( p l ，一，p k - l ，p 七) i q v ( p , ，p 七1 ，p k + 1 ) 故p 必在k 阶v o r o n o i 图的v o r o n o i 边上，证毕。 2 2 2k 阶最远点v o r o n o i 图 定义3 ：设e 为欧氏平面，s 是e 上一个n 个点的集合。假设任何四点不共圆，任何三 点不共线。设s = a ，p ：，以) 为二维欧氏空间( 平面) 上的点集，r 是s 中任意k ( 1 k n ) 个点构成的集合，定义r 的k 阶最远点v o r o n o i 区域为： f v ( r ) = a ( p ，叻) ( 4 ) 其中d ( p ，v ) 是点p 到点1 ，的欧氏距离。显然，v ( r ) 是那些到r 中任意点v 比到s - f 中任意点w 都远的点的集合。k 阶最远点v o r o n o i 图，是s 中所有这样的r 所形成的最 远点v o r o n o i 区域的并，记作v o r , ( s ) ，即v o r t ( s ) = u f v ( f ) ，fcs ，if | _ k 。当k = n 一1 时，即为定义l 所给出的v o r o n o i 图。k 阶最远点v o r o n o i 图的顶点和边分别称为k 阶 最远点v o r o n o i 顶点和k 阶最远点v o r o n o i 边。 k 阶最远点v o r o n o i 图有如下性质嘲： 性质2 对n 个生成元，其k 阶最近点v o r o n o i 图，也是它的n - k 阶最远点v o r o n o i 图。 6 证明：设a ，仍，p 。为生成元，p 为k 阶最近点v o r o n o i 图的v o r o n o i 边上一点，不失 一般性，由性质1 可设 d ( p ，p 1 ) d ( p ，p 七一1 ) d ( p ，p t ) = d ( p ，p t + 1 ) d ( p ，p t + 2 ) d ( p ，p 。) 因而有： d ( p ，a ) d ( p ，p 七) d ，p m ) 虽sd ( p ，p 一) a ：1 2 ，七一1 ) 可见，p 到岛的距离为最远距离，p 到以q 的距离为次远距离，依次类推，p 到p m 的 距离为第n k l 远距离，pn p k 的距离为第n k 远距离。由k 阶最远点v o r o n o i 图的 定义，若记k 阶最远点v o r o n o i 图中由p i ，n + 2 ，p 。所确定的n k 阶最远点v o r o n o i 区 域为f 矿o i ，p m ，以) ， 则有p ef v ( p k ，p “2 ，见) 同样由 d ( p ，p 1 ) d ( p ，p 七+ 1 ) 为二维欧氏空间( 平面) 上的点集，f 是s 中任意k ( 1 k ，鳓e f ，j = 1 ，2 ，后， j 为l 到n 中任意数。定义r 的k 阶有顺序v o r o n o i 区域为： o z ( r 3 = 仞i v w s r ，d ( p ，f l p ) d ( p ，p f 2 ) d ( p ，p 瑭) sd ( p ，们) ( 5 ) 其中d ( p ，p 扩) 表示点p 到点功的欧氏距离。显然，o r ( r ) 是那些到r 中任意点1 ，比到 s - r 中任意点w 都近的点的集合，且点p 到r 中点助( 助r ，j = 1 ，2 ，七) 的距离也必 须是按从小到大的次序排列。因此，o r ( r ) 被称为点易。，易2 ，p 豫的k 阶有顺序v o r o n o i 区域。k 阶有顺序v o r o n o i 图，是s 中所有这样的r 所形成的v o r o n o i 区域的并，记作 g o r | | ( s ) ，即v o r t ( s ) = u y ( r ) ，rcs ，irl = k 。当k = l 时，即为定义1 所给出的v o r o n o i 图。k 阶有顺序v o r o n o i 图的顶点和边分别称为k 阶有顺序v o r o n o i 顶点和k 阶有顺序 v o r o n o i 边。 2 3 2k 阶有顺序y o r o n o i 图的性质 性质1 平面上任意1 1 个点的k 阶有顺序v o r o n o i 图包含着该n 个点的k - 1 阶有顺序 v o r o n o i 图的v o r o n o i 边。 性质2 平面上任意n 个点的k 阶有顺序v o r o n o i 图包含着该n 个点的所有阶数小于k 的有顺序v o r o n o i 图的v o r o n o i 边。 性质3 对平面上任意一点p ，如果 d ( p ，p 1 ) s d ( p ，p 卜1 ) d ( p ，p i ) = d ( p ，p i + 1 ) d ( p ，p k + 2 ) d ( p ，p 。) ( 6 ) 则p 必在k 阶有顺序最近点v o r o n o i 图的v o r o n o i 边上，其中a ，p 2 ，p 。为生成元。 性质4k 阶有顺序v o r o n o i 图的v o r o n o i 边仍为直线段。 性质5k 阶v o r o n o i 图是k 阶有顺序v o r o n o i 图不区分点的先后顺序时的特例。 8 第3 章高阶v o r o n o ；图生成算法 3 1传统的高阶v o r o n oj 图生成算法概述 随着人们对高阶v o r o n o i 图研究的不断深入，产生了多种生成高阶v o r o n o i 图的算 法。周培德在他的计算几何一算法分析与设计中介绍了用于生成高阶v o r o n o i 图 的分治算法、垂直平分线的补线和关联三角形算法n 叫，但这些算法仅限于生成二阶 v o r o n o i 图。l e e 第一个提出平面n 个点集合的k 阶y o r o n o i 图的生成算法n 妇利用 k - 1 阶v o r o n o i 图构造k ( 1 k n ) 阶v o r o n o i 图。c h a z e l l e 和e d e l s b r u n n e r n 幻也对 利用k - 1 阶v o r o n o i 图构造k 阶v o r o n o i 图的算法进行了深入研究，并得出：对较大的 k 值，产生的效果更佳，s h a m o s 在他的计算几何导论n 3 1 中，也有一个类似的算法。 c l a r k s o n 在构造算法中引入了随机方法n 钔，之后许多研究者为了简化其算法提出了随机 增量法，不提前对点作出分配假设，随机地插入点，算法在感觉上是增量的，但所有点 必须提前获取，并存放在一个辅助的数据结构冲突表中。m u l m u l e y n 引、c l a r k s o n 与 s h o r n 6 3 也在这方面做了深入研究。构造k 阶v o r o n o i 图还有半动态算法n 7 j8 1 9 1 、离散生 成算法啪1 等。此外顾晓青等还提出了一种距离判断法一禹过对平面任意一点和所有生 成元求距离，再把n 个距离排序，对第k 近的和第k + l 近的距离比较，若两距离相等则 此点即为k 阶v o r o n o i 图的v o r o n o i 边，从而找到k 阶v o r o n o i 图的所有v o r o n o i 边。 这种方法较以前的生成算法无论是在数据结构上还是在生成效率上都有了很大的改进， 然而对平面上任意一点都要和所有生成元求距离，对系统资源也造成了浪费。 本文在分析以往生成算法的基础上，吸取其经验，力求提供一种思路简洁，结构简 单，效率较高，且保证图形效果，适用于构造多种不同类型高阶v o r o n o i 图的算法。以 下将介绍作者设计的k 阶v o r o n o i 图和k 阶有顺序v o r o n o i 图的生成算法。 3 2 预备知识 研究发现，平面内任意生成元的k 阶v o r o n o i 区域与该点的位置有关。也就是说， 要找平面上任意一点的k 个最近邻居，不必完全搜索全屏幕，而是局部搜索即可找到。 为了说明这个问题我们先介绍下面两个“限定上界( f i x e du p p e rb o u n d ) 定理： 定理1 ：假设查询点在位置p 的k 个最近邻居是p 。，p 2 ，p 七，并且d ( 克) 是这些点到p 距 离的最大值。那么查询点g 的k 个最近邻居必在以g 为圆心，以d ( 后) + 万为半径的圆内。 9 这里万是p 和q 之间的距离。 证明：根据定义可知，d ( p ，p ，) d ( k ) ，( 1 i k ) 根据三角不等式有：d ( q ，p ，) d ( 后) + 万，( 1 i k ) 也就是说，至少有k 个点到g 的距离不大于d ( 后) + 万，证毕。 定理2 ：假设查询点在位置p 的k 个最近邻居是p ，p ：，p k ，并且d ( 后) 是这些点到p 的 距离最大值，d ( 七+ 1 ) 是p 的第k + l 邻近距离。那么当8 ( d ( k + 1 ) - d ( k ) ) 2 时，查询点 g 的k 个最近邻居与p 相同，这里万是p 和q 2 f 司的距离。 证明： 据定义可知，d ( p ，p i ) d ( k ) ，( 1 s i s k ) 根据三角不等式有：d ( q ，p t ) d ( j i ) + 万，( 1 f 七) 对于这k 个邻近点以外的任意一点c 根据三角不等式有： d ( 后+ 1 ) 一万d ( c ，g ) 当万p ( 七+ 1 ) 一d ( k ) ) 2 时，对于这k 个邻近点以外的任意一点c 都有： d ( q ，死) d ( 后) + 艿d ( 后+ 1 ) 一万d ( c ，g ) ，( 1 f 后) 即a ，p 2 ，p j t g r ：q 的k 个最近邻居，证毕。 本文依据v o r o n o i 图的性质和以上定理设计了一种快速生成高阶v o r o n o i 图的算 法，该算法利用屏幕自适应分区实现了局部查找k 个最邻近点，思路简洁，结构简单， 不仅保证了准确的图形效果而且使生成效率得到了很大的提高。下面是算法的设计思 想： 首先根据屏幕上生成元个数对屏幕进行分区。对于每一个分区，分别以左上角点为 参照点，计算该点到所有生成元的距离并记录第k 和k + l 邻近距离值，如果这两个距离 相等，便将该点画出；扫描该分区所有像素，依据定理1 和定理2 确定该像素的k 个 近邻所在的范围，而不必再遍历所有生成元，最终把该点到生成元距离第k 和k + l 距离 相等的点全部画出：对每个分区执行相同的操作，这样便画出了k 阶v o r o n o i 图的所有 v o r o n o i 边。 由定理l 和定理2 以及上面的算法思想可知，合适的分区( 在保证图形效果的前提 1 0 下使程序运行速度达到尽可能快) 大小与生成元个数有关。因而，本算法采用自适应分 区根据生成元个数多少进行分区，生成元个数越多，所分区域越多，反之，分区越 少。根据反复试验得出以下经验公式： = w i d t h * ( n 1 0 0 + i ) ( 0 3 宰疗) ( 7 ) h = h i g h t * ( n 1 0 0 + 1 ) ( 0 3 * n ) 0 0 00 00 ( 8 ) 其中形，日为分区长和宽，以为生成元个数，w i d t h ，h i g h t 为屏幕长和宽。可见生成 元个数越多，屏幕分成的区域越多。 3 3 生成k 阶v o r o n oi 图的算法 输入：n 个生成元a ，p 2 ，岛和阶数k ( 1 k n ) 。 输出：n 个生成元的k 阶最近点v o r o n o i 图( 也是n k 阶最远点v o r o n o i 图) 。 生成方法如下： ( 1 ) 画出n 个生成元p l ，p 2 ，p 。 ( 2 ) 根据生成元个数n 确定分区大小，形= w i d t h * ( n 1 0 0 + 1 ) ( 0 3 宰甩) ， h = h i g h t * ( n 1 0 0 + 1 ) ( 0 3 * n ) ，其中矿，日为分区长和宽，w i d t h ，h i g h t 为屏幕长和宽， 1 1 为生成元个数。 ( 3 ) 定义数组m i n k + l 】。 ( 4 ) 对于每一个分区，先计算左上角点到各个生成元的距离a ( p ，a ) ，按从小到大顺序 取前k + 1 个，记第k 和k + l 邻近距离为d ( k ) 和d ( k + 1 ) 。扫描该分区内任意一点( x ，y ) ( 记d 1 为该点到左上角点的距离，d 2 为d l + d ( 后+ 1 ) ) 。如果d l ( d ( 后+ 1 ) 一d ( 后) ) 2 ，依 定理2 可知该点与左上角点有相同的k + 1 个近邻。分别计算该点与左上角的前k + l 近邻 点的距离并存入数组m i n k + 1 】，记录第k 和k + l 近邻距离d ( k ) 和d ( k + 1 ) ，若 d ( 七+ 1 ) 一d ( k ) ( d + 1 ) 一d ( k ) ) 2 ，说明点( x ，y ) 的k + 1 个近邻必在以( x ，y ) 为圆心以d 2 为半径的圆域内，在此圆域内找到的至少k + 1 个邻近点中取第k + l 和k 近邻距离做差， 若差小于孝，则画出该点。 ( 6 ) 对每个分区作如上操作，得到n 个生成元的k 阶最近点v o r o n o i 图。 该算法已用v i s u a lc 抖编程实现，下面是用该算法生成的高阶v o r o n o i 图： 图33 卟点的2 阶v o r o n o i 图 图48 0 个点的了阶v o r o n o i 图 3 4 k 阶有顺序v o r o n oi 图生成算法 k 阶有顺序v o r o n o i 图是k 阶v o r o n o i 图经过推广而生成的，所以通过改进k 阶 v o r o n o i 图的生成方法，可得到一种生成k 阶有顺序v o r o n o i 图的算法。算法的开始部 分与k 阶v o r o n o i 图的生成法相同，即：先对平面上任意点p ，计算p 与n 个生成元之 间的距离，然后经过比较，按从小到大顺序取前k + 1 个距离值进行处理。然后，不仅仅 只将第k 个距离值和第k + 1 个距离值进行比较，而是将前k + 1 个距离值按从小到大顺序 逐个比较，只要其中第广个距离值和第，+ 1 个距离值相等( ，= 1 ，2 ，k ) ，便将该点画 出。遍历屏幕上所有像素点p ，便画出了k 阶有顺序v o r o n o i 图的全部v o r o n o i 边，即 生成了n 个生成元的k 阶有顺序v o r o n o i 图。 k 阶有顺序v o r o n o i 图的生成算法如下： 输入：n 个生成元a ，仍，p 。和阶数k ( 1 k n ) 。 输出：n 个生成元的k 阶有顺序v o r o n o i 图。 生成方法如下： ( 1 ) 画出n 个生成元p l ，p 2 ，p 。 ( 2 ) 根据生成元个数n 确定分区大小，形= w i d t h * ( n 1 0 0 + 1 ) ( 0 3 * n ) ， h = h i g h t * ( n 1 0 0 + 1 ) ( 0 3 * n ) ，其中形，日为分区长和宽，以为生成元个数，w i d t h ，h i g h t 1 2 为屏幕长和宽。 ( 3 ) 定义数组r a i n k + 1 和变量r 。 ( 4 ) 对于每一个分区，先计算左上角点到各个生成元的距离d ( p ，p ；) ，按从小到大顺序 取前k + 1 个，记录第k 和k + l 邻近距离d ( k ) 和d ( k + 1 ) 。扫描该分区内任意一点( x ，y ) ( 记d l 为该点到左上角点的距离，d 2 = d l + d ( 七+ 1 ) ) 。如果d l ( d ( 后+ 1 ) 一d ( k ) ) 2 ，说 明该点与左上角点有相同的k + 1 个近邻，分别计算该点与此k + 1 个近邻的距离。 ( 5 ) 按从小到大顺序取前k + 1 个距离值，将其依次赋给r a i n 1 ，r a i n 2 ，m i n k 和 m i n k + 1 】；将r 赋值为o ；如果m i n r + 1 一m i n r 】 l 时生成高阶v o r o n o i 图( k 阶最近点v o r o n o i 图) ，下表列出了本算法与 其它一些v o r o n o i 图生成算法在同一台计算机( i n t e lp e n t i u m4 ，2 4 1 g h z ) 上的运行时 间比较： 表1 本算法与其它一些v o r o n o i 图生成算法速度比较( 单位：秒) 生成元离散生成k 阶v o r o n o i 生成算法( 顾)本算法 个数算法( 1 阶) 1 阶3 阶8 阶1 阶3 阶8 阶 6 08 4 0 81 3 7 71 8 4 32 9 0 l0 9 0 11 0 8 11 5 4 9 i 0 07 8 6 02 1 0 92 9 7 54 7 1 51 2 1 41 5 4 52 2 4 8 3 0 07 7 6 76 2 5 78 5 5 41 3 2 5 02 9 1 03 3 1 4 4 2 9 l 由上表可见，本算法作为一阶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 图生成算法思路简单且效率较高，而本算法与顾晓青的高阶生成算法相比，随着阶数的 增加速度有更加明显的提高。 此外，本算法生成的k 阶有顺序v o r o n o i 图与顾晓青生成k 阶有顺序v o r o n o i 图相 比，速度也有较大提高。本文针对k 阶有顺序v o r o n o i 图与顾晓青的算法也进行了比较， 1 4 如下图所示： 6 0 a4 暑2 3 缸 l 0 2 04 06 08 01 0 0 1 2 0 1 4 0 1 6 0 1 8 0 母点数 图72 阶有顺序v 图本算法与顾 小青算法生成时间比较 2 04 06 08 0i 0 0 1 2 01 4 01 6 0 1 8 0 母点数 图86 阶有顺序v 图本算法与顾 小青算法生成时间比较 木算法j 顾算法1 + 本算法】 小顾算法i 以上结果均在同一台计算机( i n t e lp e n t i u m4 ，2 4 1 g h z ) 上实现。 8 7 6 5 4 3 2 1 o v 垦留 结论 高阶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 图的生成方法在理论和实 际中都有相当重要的意义。本文利用屏幕自适应分区和局部查找k 个近邻的思想设计了 一种简洁而高效的高阶v o r o n o i 图生成算法。它无论是用于生成一阶v o r o n o i 图、高阶 v o r o n o i 图还是k 阶有顺序v o r o n o i 图，均有较好的图形效果且有较高的生成效率。这 是对以往v o r o n o i 图生成算法的一大改进，在实际中有很好的应用前景。文章最后还将 本算法与以往一些v o r o n o i 图生成算法进行了比较分析，从而验证了本算法的优越性。 当然，本算法还存在一些有待进一步研究的地方。如在实现屏幕自适应分区时，最 好能获得精确的计算公式，用其取代经验公式，使得分区大小使该算法达到最优。此外， 本算法在维数方面，也可以推广到高维欧氏空间，这将是今后研究的重点。 1 6 参考文献 1 2 1 周德培计算几何清华大学出版社2 0 0 0 2 m l s h a m o sa n dd h o c y c l o s c s t - p o i n tp r o b l e m s p r o c e e d i n g so ft h e1 6 t hi e e es y m p o s i u mo n f o u n d a t i o n so f c o m p u t e rs c i e n c e , 1 9 7 5 ：1 51 - 1 6 2 3 3z h e x u a ns o n ga n dn i c kr o u s s o p u u l o s k - n e a r e s tn e i g h b o rs e a r c hf o rm o v i n gq u e r yp o i n t j s s t d , 2 0 0 1 ：7 9 - 9 6 4 gv 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 6 t e r sc o n t i n u sal at h d o d ed e sf o r m e sq u a d r a t i q u e s d e u x m m em d m o i r e ：r e c h e r c h e s8 u rl e sp a r a l l d l l 0 6 d r e sp 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 5 gv 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 c r e r sc o n t i n u sal at h 6 0 r i ed 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 d m o i r e ：s u rq u e l q u e sp r o p f i e t e d sd e sf o r m e sq u a d r a t i q u e sp o s i t i v e sp a r f a i t s ，j r e i n ea n g e w ， m a t h ，13 3 ，9 7 - 17 8 ，19 0 7 6 1 0 周培德，卢开澄计算几何算法分析与设计清华大学出版社，2 0 0 0 7 儿8 9 顾晓青、张有会等关于k ( 1 k n ) 阶v o r o n o i 图生成算法的研究计算机应用与软 件，2 0 0 4 1 1 d t l e e o nk - n e a r e s t n e i g h b o rv o r o n o id i a g r a m si nt h ep l a n e i e e et r a n s a c t i o n s 0 1 1 c o m p u t e r s ，31 ：4 7 8 - 4 8 7 ，1 9 8 2 1 2 b c h a z e l l ea n dh e d e l s b r u n n e r a ni m p r o v e da l g o r i t h mf o r c o n s t r u c t i n gk t h - o r d e r v o r o n o id i a g r a m s i np r o c o c d i n g so ft h ef i r s ta c m s y m p o s i u mo nc o m p u t a t i o n a lg e o m e t r y , b a l t i m o r e ，p p 2 2 8 - 2 3 4 ，j u n e 1 9 8 5 13 f r a n c oe p r e p a r a t a ，m i c h a e li a ns h a m o s 著，庄心谷译计算几何导论。北京：科学出版社，19 9 0 14 k l c l a r k s o n n e wa p p l i c a t i o n so fr a n d o ms a m p l i n gi nc o m p u t a t i o n a lg e o m e t r y d i s c r e t ea n d c o m p u t a t i o n a lg e o m e t r y , 2 ：19 5 - 2 2 2 ，