（基础数学专业论文）power图扫描生成算法的研究.pdf

河北师范大学硕士研究生学位论文 学位论文原创性声明 本人所提交的学位论文p o w e r 图扫描生成算法的研究，是 在导师的指导下，独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体， 均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：多f 3 、髟 砌7 年r 月知日 学位论文原创性确认书 学生至盟! 塑所提交的学位论文p 。w e r 图扫描生成算法的研 究，是在本人的指导下，由其独立进行研究工作所取得的原创性 成果。除文中已经注明引用的内容外，该论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。 指导教师( 签名) ：爹淞 力一7 年，月伽日 第l 页 河北师范大学硕士研究生学位论文 摘要 v o r o n o i 图是计算几何的重要分支，p o w e r 图是v o r o n o i 图的一种重要推广， 它是将欧氏距离推广到p o w e r 距离而形成的一种加权v o r o n o i 图，具有很大的 实用价值。本文在现有p o w e r 图理论的基础上，给出了一种生成p o w e r 图的新 算法一扫描生成法，该算法隶属于离散生成方法。它利用屏幕的光栅特性，计 算屏幕上每个像素点与生成元的p o w e r 距离，然后比较、排序，根据p o w e r 边 上的点到某两生成元的p o w e r 距离相等这一特点，从而画出p o w e r 边，生成 p o w e r 图相比p o w e r 图的其他算法，该算法不仅思路清晰，程序设计简单， 而且无需复杂的辅助数据结构，节省了大量的预处理时间和存储时问，并且可 推广到高阶p o w e r 图的情况。 作为应用举例，利用该算法生成的p o w e r 图，分析了石家庄市某区网通营 业厅的覆盖区域问题，并就其分布的合理性进行了讨论。 关键词：计算几何，v o r o n o i 图，p o w e r 图，扫描生成算法 第2 页 河北师范大学硕士研究生学位论文 a b s t r a c t v o r o n o id i a g r a mi sa l li m p o r t a n tb r a n c ho ft h ec o m p u t a t i o n a lg e o m e t r y p o w e r d i a g r a mi so n ek i n do f i m p o r t a n te x t e n s i o no f y o m n o id i a g r a m i ti so n ek i n do f w e i g h t e d v o r o n o id i a g r a mt h a te x t e n df r o me u c l i d e a nd i s t a n c et op o w e rd i s t a n c e ，a n dh a st h ev e r yg r e a t p r a c t i c a lv a l u e t h i sp a p e rg i v e so n ek i n do f n e wa l g o r i t h mg e n e r a t i n gp o w e rd i a g r a m s c a n n i n gp r o d u c t i o na l g o r i t h mo nt h eb a s eo fp o w e rd i a g r a mt h e o r y t h ea l g o r i t h m s u b o r d i n a t e st ot h ed i s c r e t eg e n e r a t i n gm e t h o d i tm a k e su s eo ft h ed i f f r a c t i o ng r a t i n g c h a r a c t e r i s t i co ft h es c 职掰lt oc a l c u l a t ep o w e rd i s t a n c eb e t w e e ne a c hp i c t u r ee l e m e n ta n dt h e g e n e r a t o ro nt h es c r c c l l c o m p a r i n ga n ds o r t i n gw e l ed o n e ，t h u si td r a w sp o w e rb o u n d a r ya n d c o n s t r u c t sp o w e rd i a g r a ma c c o r d i n gt ot h i sc h a r a c t e r i s t i co f e q u a lp o w e rd i s t a n c ef r o mp o i n t o np o w e rb o u n d a r yt o5 0 m et w og e n e r a t o r s c o m p a r e dw i t ho t h e ra l g o r i t h m s ，t h i sm g o f i t h mh a s n o to n l yc l e a rm e n t a l i t ya n ds i m p l ep r o g r a md e s i g n , b u ta l s od o e sn o tn e e dt h ec o m p l e x c o n t r i b u t o r yd a t as t r u c t u r e ，a n da l s os a v e dt h em a s s i v ep r e t r e a t m e n tt i m ea n dt h es t o r a g et i m e ， a n dm a ye x t e n dt ot h eh i g h e ro r d e rp o w e rd i a g r a ms i t u a t i o n a st h ea p p l i c a t i o ne x a m p l e w eu s ep o w e rd i a g r a mb yt h i sa l g o r i t h mt oa n a l y z et h e r e g i o n - f o v e r i n gq u e s t i o n so f c n ct op a s st h es e l l i n ga r e ao ns o m ea r e ai nt h es h i j i a z h u a n g , a n d h a v ec a r d e do nt h ed i s c u s s i o na b o u ti t sd i s t r i b u t i o nr a t i o n a l i t y 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 y , v o r o n o id i a g r a m t p o w e rd i a g r a m s c a n n i n gp r o d u c t i o na l g o r i t h m 第3 页 河北师范大学硕士研究生学位论文 第一章绪论 1 1 计算几何与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 图与p o w e r 图 随着更多学者研究的不断深入，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 维欧氏平面内的v o r o n o i 图扩展到m 维空间的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 o w e r 距离等。 正是在v o r o n o i 图蓬勃发展的背景下，出现了p o w e r 图，p o w e r 图是普通 v o m n o i 图的扩展，它以点为生成元，对每个生成元加权，将欧式距离推广为 p o w e r 距离而生成。 1 3 论文的研究内容 本文首先简要介绍了什么是v o r o n o i 图，p o w e r 图与v o r o n o i 图的关系， v o r o n o i 图的性质、构造方法、应用等，然后又介绍了p o w e r 图定义、性质、已 有生成方法，在此基础上，本人所作的工作是： 第6 页 河北师范大学硕士研究生学位论文 提出了一种直接由p o w e r 图定义、性质入手的扫描生成算法，详细介绍了 该算法的基本思想、算法流程以及该算法的优势，相比生成p o w e r 图的其他算 法，该算法不仅思路清晰，程序设计简单，而且无需复杂的辅助数据结构，节 省了大量的预处理时间和存储时阃( 详细算法请见第四章) 。 应用举例：利用扫描法构造的p o w e r 图对石家庄市某区域的网通营业厅的 分布现状与覆盖区域进行了分析。 最后对p o w e r 图，给出了在v i s u a l c h 6 0 环境下实现的算法的源程序。 1 4 论文的结构安排 第一章简述了计算几何与v o r o n o i 图、v o r o n o i 图与p o w e r 图之间的关系， 并且介绍了论文研究的基本内容及大致结构；第二章给出了v o r o n o i 图的历史、 定义，基本性质、生成方法、应用；第三章介绍了p o w e r 图定义、性质，已有 的生成算法以及p o w e r 图的应用：第四章详细阐述了p o w e r 图扫描生成算法的 基本思想、实现步骤( 算法) 以及与其他算法相比较该算法的优点；第五章给 出了具体的应用实例：第六章本文工作总结以及有待于进一步研究的问题；最 后是文章的参考文献和附录部分。 第7 页 河北师范大学硕t 研究生学位论文 第二章v o r o n o i 图 2 1v 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 图的结构对太阳系进行分割【l j 。数学家d 谢c h l 呱1 8 5 0 ) 和v b r o n o i ( 1 9 0 7 ，1 9 0 8 ，1 9 0 9 ) 在正有限二次型的研究中正式介绍了v o r o n o i 图的概念，并分别研究了二维、 三维和m 维的情况1 2 j 1 ，从那以后，人们开始考虑在空白j 中放置一系列点按欧式 距离对平面进行分割，并将这种平面分割图称之为d i r i c h l e t 剖分或v o r o n o i 图。 在1 9 7 5 年，s h a m o s 和h o e y 给出了构造v o r o n o i 图的算法及其相关问题【4 】。历 经数十年的研究，v o r o n o i 图的理论和算法越来越成熟，应用也越来越广泛。 2 2v o r o n o i 图的定义及其性质 2 2 1v o r o n o i 图的定义 平面上一个点集s 的v o r o n o i 图是对平面的一种划分。其精确的数学定义【5 j 如下： 定义1 给定平面上厅个点构成的集合s = 印l ，p 2 ，p 。 ，其中任何四点不共 圆。由 r ( p ，p ，) = p r 2 l l l p - p 6 l i p - p ，f ，) 定义的区域r ( p ，p f ) 称为p iv o r o n o i 区，0 p 9 8 表示p 和g 两点之间的距离， 由r ( p ，p f ) ( f = l ，2 ，一) 及其边界给出的对平面的分割称作s 的v o r o n o i 图，简 称v o r o n o i 图。s 中的点a ( f = l z ，押) 称为生成元( 或母点) ，图中的边界称为 生成元p f 和p ，之间的v o r o n o i 边，不同v o r o n o i 边的交点称为v o r o n o i 顶点。 该定义中p 和g 之间的距离怕一训可以是欧氏距离，也可以是其它距离，如 城区距离f 6 j 、棋盘距离1 6 1 等。下图所示为不同距离下的v o r o n o i 图： 第8 页 河北师范大学硕士研究生学位论文 图1 欧氏距离下的图2 城区距离下的 v o r o n o i v o r o n o i 图 2 2 2v o r o n o i 图的性质 性质1 在欧氏距离下的v o r o n o i 图中，v o r o n o i 边是由“相邻”的两个生成 元间的垂直平分线，或是该直线上的线段或射线构成。 性质2 r ( p ，p f ) n 胄( p ，p ) f f i 妒( 件m 性质3 拧个点的点集s 的v o r o n o i 图至多有2 月一5 个v o r o n o i 顶点和3 n 一6 条v o r o n o i 边。 性质4 每个v o r o n o i 顶点恰好是三条v o r o n o i 边的交点。 以上性质具体证明详见文献【4 】。 2 3v o r o n o i 图的构造法 自从1 9 7 5 年s h a m o s 和h o e y 在总结前人方法的基础上，系统给出了构造 v o r o n o i 图的算法后，关于v o r o n o i 图的算法的研究就方兴未艾。传统的算法包 括半平面的交的算法、随机增量算法、分治算法、平面扫描算法等。近期又出 现一些新的算法，如：离散生成法、结晶法等，均具有较高的效率，且算法的 构造新颖实用。以下简要介绍几种常用算法的基本思路。 1 半平面的交的算法州：半平面的交是生成v o r o n o i 图的最直接的方法。 它直接利用v o r o n o i 图的定义，构造n 1 个半平面的交，得到点p 的v o r o n o i 区域，逐点构造各点的v o r o n o i 区域便得v o r o n o i 图。 该算法的时间复杂度为o ( n 2 ) 。 第9 页 河北师范大学硕士研究生学位论文 2 随机增量算法嘲：与第一个算法相比，随机增量算法去掉了很多冗余的 东西，因而显得快速有效。它通过逐个添加生成元( 或母点) ，每次添加后更新 v o r o n o i 边得到v o r o n o i 图。 该算法时间复杂度为：最好情况是o ( n ) ，最坏情况是0 0 2 ) ，平均情况是 o ( n l o g n ) 。 3 分治法1 7 i ：按点的x 坐标的中值分割点集，直至子集含生成元数小于 或等于4 。每个子集各自产生v o r o n o i 图后，不断合并相邻子集的v o r o n o i 图， 直至得到v o r o n o i 图。 分治法时间复杂度为o ( n l o g n ) 4 平面扫描算法例：通过平面上的一条扫描线由左至右扫描。当扫描到某 一部分时，就构造该部分的v o r o n o i 图，直至扫描终止。 5 离散构造法( 9 1 ：对每一个生成元指定一种颜色，以每个生成元为圆心， 匀速向外扩张画圆，直至整个平面，不同颜色的区域相遇产生交线，此交线图 即为v o r o n o i 图。 6 结晶法吲：是一种模拟晶体生长的离散生成算法。对每个生成元，以生 成元为生长点，以指定的颜色( 即生成元的颜色) 和相同的速度向外进行4 一模 板和8 模板的结晶生长各生长点在结晶过程中，不同结晶区域产生的交线图 即为v o r o n o i 图。 2 4v o r o n o i 图的应用 v o r o n o i 图的应用工作开始于1 9 世纪6 0 年代，随着v o r o n o i 图理论的日益 成熟，经过一个多世纪的发展，v o r o n o i 图理论已经广泛应用于社会各个领域。 v o r o n o i 图在计算几何中，用来解决最近邻近问题( 包括：最近邻近查询问题、 最大化最小角的三角剖分问题、最大空圆问题、最小生成树问题等) ；在计算机 图形学、图像处理与模式识别中，a c i n 等帅i 将v o r o n o i 图应用在半色调图像生 成中，d a r s a 等州用v o r o n o i 图进行图像的多分辨率表示及重构，以压缩图像， b i s c h o f 等【1 2 用v o r o n o i 图进行基于灰度的图像分割，还可用v o r o n o i 图生成形 第1 0 页 河北师范大学硕士研究生学位论文 体的骨架等；在物理、化学和分子生物学中，j u l l i e n 等m 1 应用两种计算模型模 拟玻璃体的微观结构，d e f a b r i t i i s 等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 图( 生成元是线段、多边形或多面体等) ：另外，v o r o n o i 图在移动 通信、平面装饰图案设计、机械制造、数学规划等众多领域都有重要应用。同 时，也有不少应用对v o r o n o i 图理论提出了新的要求，等待理论上的新成果问 世。 第1 i 页 河北师范大学硕十研究生学位论文 第三章p o w e r 图及其应用 在普通的v o r o n o i 图中，我们假设生成元除了位置外是完全相同的，即每 个生成元点的权值一样。在实际应用中，有时这种假设是不合理的，比如一个 地区污染源的散发量，一辆家庭用轿车排出的尾气与一座大型化工厂排出的污 染物显然是不等量的，即轿车和化工厂的权值是不同的因此由不同的权值反 映不同生成元的性质更加合适，更加符合实际情况，所以我们有必要引入加权 v o r o n o i 图和p o w 盯图的定义。 3 1p o w e r 图的定义 p o w e r 图是在加权v o r o n o i 图的基础上将欧氏距离推广到p o w e r 距离而生成 的平面剖分图，下面先引入平面加权v 0 r o n o i 图和p o w e r 距离的定义。 3 1 1 加权v o m n o i 图的定义 定义2 设生成元集合为s = p ，p 。) cr 2 ( 2 n o o ) ，权值集合为 w = w ，w 。 ，w ，为生成元p 的权值( i = 1 , 2 ，1 ) 。加权v o r o n o i 图由下 式加权距离定义 d 。( p ，p ) = i i p - p i i - w ， 我们称这个距离为加权距离或简称a w 一距离。加权距离下由p ，控制的区域 记为v ( p i ) = n d o m ( p i ，p ，) ，其中 t j d o m ( p j ，p j ) = p i d 。( p ，p j ) d 。( p ，p j ) 我们称v o r 。( p ，d 。，r 2 ) = v ( p ) ，v ( p 。) 为带权集 w ，w 。 的集合p 生成 的加权v 0 r o n o i 图，称集v o r ( p 。) 为与p i 关联的加权v o r o n o i 域。 将上述距离推广到p o 嘲距离m i ，就得到p o w e r 图的定义。下面先介绍 p o w 盯距离的定义。 3 1 2p o w e r 距离的定义 定义3 已知二维欧式空间r 2 中的点集s = p ；i i - j ，n ) ，p 的权为 第1 2 页 河北师范大学硕士研究生学位论文 w 。( 哪 w i 佃) ，平i s _ l = 任意一点p 芒s 和p ie s 之间的带权距离定义为： d w ( p ，p ；) = l l p - p 旷一w ； 上式定义的带权距离称为p o w e r 距离，其中l i p - p 。8 为p 和p 间的欧氏距离。 3 1 3p o w e r 图的定义 定义4 设s = p i ，p 2 ，p 。 为二维欧氏空间( 平面) 上的点集，对每个生 成元p i 赋以权重w i ( i = 1 , 2 ，n ) 。用p o w e r 距离 d ，( p ，p ) = l l p - p 0 2 - - w 。 定义的v o r ( p d ，) = v o = v ( p a ，v ( p 。) 称为由集合s 生成的加权p o w e r 图，或简称为 s 的p o w e r 图，称集合v ( p ) 为与p i 相关联的 p o w e r 多边形。 图3 所示为二维平面上的p o w e r 图，其中黑 点代表生成元，细线代表p o w e r 边。 3 1 4p o w e r 球 图3p o - e r 图 定义5 我们把以p ，为圆心，为半径的球称作与p 相关联的p o w e r 球， f 0p 点位于b 内1 用鱼表示显然有“( p ，p ，) = 0 p 点位于6 f 上 b 0p 点位于岛外l 当w i 非负时，p o w e r 距离d ，( p ，只) 可以看作由p 点出发，到与p ，相关联的 3 2p o w e r 图的性质 性质1 对平面上任意一点p ，如果d ，( p ，p 。) = d w ( p ，p 2 ) d w ( p ，p 3 ) d w ( p ，p 。) ，则p 必在p o w e r 图的p o w e r 边上，其中p i ，p 2 ，p 。为生成 第1 3 页 河北师范大学硕士研究生学位论文 或射线构成。 性质3 三个不共线生成元决定的三条p o w e r 边交于一点。 性质4v ( p ) 是一凸多边形或为空。 以上性质的证明参见文献【1 5 】及【1 6 】 3 3p o w e r 图已有生成算法 p o w e r 图的传统的构造方法是正则三角化构造法，近些年比较流行离散生 成法，下面先逐一简要介绍p o w e r 图的这些生成算法。 3 3 1 正则三角化构造法l l ，i ： 该算法利用p o w e r 图与正则三角化互为对偶的原理，在点集的正则三角化 的基础上构造p o w e r 图。 点集的正则三角化是点集的d e l a u n a y 三角化的推广。点集s 的正则三角化 记为r ( s ) ，r ( s ) 中的任意一个三角形都是正则的，因此三角形的正交中心是 p o w e r 图的一个顶点；r ( s ) 中的边是p o w e r 图的对偶边，设在r ( s ) 的数据结构 中，三角形可以通过邻接关系互相访问，由p o w e r 图与正则三角化互为对偶的 原理，对r ( s ) 的任意一条边，p o w e r 图中有且仅有一条此边的对偶边，设( e , e ) 是一对对偶边，e g ( s ) ，e 点集s 的p o w e r 图，e 的计算方法如下：( 1 ) 当e 在点集s 的凸包内部时，e 是r ( s ) 中两个相邻三角形的邻边，连接这两个三角 形的正交中心形成的线段即为e ；( 2 ) 当e 是点集s 的凸包的边界边时，e 只是 r ( s ) 中一个三角形的边，此时，e 是从三角形的外心出发，向垂直于e 边的方 向离点集s 的凸包远离的一条射线；计算r ( s ) 的顶点的p o w e r 单元，设s 为 r ( s ) 的所有顶点，对任一点p s ，其p o w e r 单元尸( 只) 计算方法如下：设r ( s ) 中以c 为顶点的所有边的集合为e ( 只) ，绕e 点顺( 逆) 时针遍历e ( 只) 中的每 条边p ，计算其对偶边0 ，并将得到的所有对偶边顺序首尾连接，形成的多边 形即为尸( 尸) 。 第1 4 页 河北师范大学硕士研究生学位论文 3 3 2 离散生成法【9 i ： 离散生成法是在光栅显示器上直接生成。该算法的基本思想是，对每个生 成元点指定种颜色，使不同生成元点之间颜色互不相同，然后生成p o w e r 球： 对每个生成元点p ，以它为圆心，嵋( w i 是生成元见的权值) 为半径用指定 的颜色( 即赋予p 的颜色) 画圆，并将位于圆内部的像素点涂上该颜色；接下 来再以p 为圆心，仍然用它的颜色，依据权重逐渐向外扩展画圆( 即以相同的 p o w e r 速度向外扩展) 画圆过程中先进行检查：如该点已有颜色( 已被涂过) ， 则越过；否则以指定的颜色画圆。当屏幕上所有的像素点都画上了颜色时，结 束。此时不同颜色区域的边界即为p o w e r 图的近似曲线。 3 4p o w e r 图的应用 加权v o r o n o i 图经常用在市场面积分析中用来决定工厂或商店的市场面积， 权值帆用来表示交通费用或者货物产品的工厂价钱：在城市空间影响范围界定 中p o w e r 图也大有用途，比如1 9 6 7 年l l l e r i s 采用了p o w e r 图来决定丹麦的城市 中心的功能区1 9 1 ；另外，p o w e r 图在晶体生长、肥皂泡制作的植物和泡沫的细 胞结构中也有很多应用，p o w e r 图还用在有机化合物的晶体结构模型中，如二 维多晶体的谷物生长、金属玻璃、全球蛋白质和肌肉纤维等等。 第1 5 页 河北师范大学硕士研究生学位论文 第四章p o w e r 图的扫描生成算法 生成p o w e r 图的方法，无论是传统的正则三角化构造法还是现在流行的离 散生成法，尽管算法各异，但总的来说不论从程序设计思路还是数据结构等方 面都相当繁复。因此，寻找一种思路简洁，结构简单，效率较高，且保证图形 效果，也适用于高阶p o w e r 图的算法，一直是p o w e r 图生成方法的研究方向。 本文就力求提供一种这样的生成方法。 下面介绍作者完成的生成p o w e r 图的方法一扫描生成算法。 4 1 算法的基本思想 由p o w e r 图的定义及性质可知，p o w e r 边是由到相邻两生成元的p o w e r 距 离相等的点构成，将这些点逐个画出，则可直接生成p o w e r 图。具体做法是： s t e p l 对于屏幕上任意像素点p ，分别计算出p 到n 个生成元p ，n ，n 的 p o w e r 距离。 s t e p 2 从这n 个p o w e r 距离中，取出最小值和次最小值。如果这两个p o w e r 距离之差的绝对值小于事先指定的某阈值，便将该点p 画出，否则跳过该像素 点，处理下一个像素点。 当p 从上到下，从左到右遍历屏幕上所有像素点，便得到p o w e r 图( 参见 图9 ) 。 4 2p o w e r 图的扫描生成算法描述 输入：生成元集合s = p i ，p 2 ，p 。) ，权重集合w = w ，w ：，w 。 ，其中 w ；为生成元p j 的权重。 输出：以s 为生成元集，w 为权重集的p o w e r 图 算法如下； s t e p l 画出n 个生成元p l ，p 2 ，以； s t e p 2 定义数组m i n 2 及p lm i n 2 ： s t e p 3 i - 0 ，j = 0 ： s t e p 4 求屏幕上坐标为( i ，j ) 的像素点p 与生成元p 之间的p o w e r 距离 第1 6 页 河北师范大学硕士研究生学位论文 以( p ，p , ) = n p - p ，0 2 一嵋( i - l ，2 ，n ) ； 经过逐个比较，取前两个较小值并依次赋给m i n o ，m i n 1 ，同时记录对应这 两个p o w e r 距离的生成元p - m i n o ，p - m i n 1 】 s t e p 5 计算m ( 见4 3 ) ，如果lm i n o m i n 1 i d e l t a + m ( d e l t a 为事 先指定的一个小正数，用来控制线的宽度，将d e l t a + m 作为阙值) ，便将该点 p ( i ，j ) 画出，否则不画： s t e p 6 j = j + l ，如果j 0 ( 若不然，可以 转化成这种情况，见文献【1 5 】) 则p 到两生成元只，最间的p o w e r 距离的差的绝对值： m 2 l d 。( p ，p 1 ) 一d w ( p ，p 2 ) i = l ( x x ) 2 + ( y - y 。) 2 一w 。卜【( x x ：) 2 + ( y y ，) 2 一w ：l = j ( x x ) 2 一( x x ：) 2 - ( w 。一w ：) i = i x ；一x ；一2 x x + 2 x x ：- ( w 一w ：) i = | ( x l x 2 x x l + x 2 - 2 x ) - ( w i - - w 2 i 如果w i = w 2 ，由p o w e r 图的定义，x = ( x l + x 2 ) 2 ，由上式可见m 值为o ：如 第1 7 丽 河北师范大学硕士研究生学位论文 果w i w 2 ，则m o 。由于只，b 两生成元间的距离为i x l x 2 i ，n - - j 见，p o w e r 边上任意点到相邻两生成元的p o w e r 距离差的绝对值与这两个生成元之间的距 离大小有关 更一般地，设只，b 为具有p o w e r 边的任意两生成爪p 元，p o 为只，b 间的p o w e r 边与只，b 的连线的交点， p ( p p 0 ) 为p o w e r 边上任意一点。由p o w e r 图的性质知： p p o 上p ip 2 ，不妨设w i o w 2 o 。 f ；p op 2 图5 因此，p 到两生成元只，b 间的p o w e r 距离的差的 绝对值： l 订2 l d ，( p ，p 1 ) 一d 。( p ，p 2 ) i = 卜p i l 2 一w 。一( i i p _ p 26 2 一w ：1 = i p p o9 2 + o p o p l l l 2 一w 一q p p 08 2 + i i p o p 2 1 1 2 一w 2 ) l = 9 p j p , 1 1 2 一i l p ；一p j i l 2 一( w 一w 2 ) i = | ( | l p 0 一p l6 + i i p o p d ) ( 1 e o p , i i i i p o p ：1 1 ) 一( w 。一w ：l = i u p , - p d ( i p o - p , i i - i i p o - v d ) - ( w 。一w ：) l = i l t v , - p d ( 1 l p 。一p 20 2 1 t p o p 2 1 b 一( w 。一w ：) i 如果w ，= w ：，由p o w e r 图的定义，8 p o - v 2 1 = l i p , - p 2 1 1 陀，由上式可见m 值为o ； 如果w 。w ：，则m o a 由于只，b 两生成元间的距离为把- p 20 ，可见，p o w e r 边上任意点到相邻两生成元的p o w e r 距离差的绝对值与这两个生成元之间的距 离大小有关。 如果在算法中不考虑m 的因素，则画出的p o w e r 边粗细不均。如图6 ( a ) ( b ) 所示，只与b 或足与只问的距离较大，画出的p o w e r 边不连续；图6 ( b ) q a 丑、 b 距离较近，画出的p o w e r 边较粗。考虑进m 的因素后，画出的p o w e r 边粗 细较均匀。如图7 所示。 第1 8 丽 河北师范大学硕士研究生学位论文 重【)量t b 图6 生成元距高对p 钾盱图的影响 重( )曩i b 图7 考虑因素后生成的p o v e r 图 其中m = ( ( x i x 2 ) 1 地1 - y 2 ) 2 ) 7 0 第1 9 页 河北师范大学硕士研究生学位论文 4 3 2 动态确定阈值 为了解决两相邻生成元问的距离对p o w e r 图的影响，设置的阈值应与相邻 两个生成元之间的距离有关，具体做法是： 设p l ( x l ，y 1 ) ，p 2 ( x ：，y 2 ) 是有p o w e r 边的两个相邻生成元，阈值可取为 d e l t a + m ，其中d e l t a 为事先指定的一个小正数，m 由上面的公式给出。在 程序设计中，为减少计算量，我们采用如下经验公式，也取得了比较好的效果： m = ( ( x i - x 2 ) 2 + ( y 1 y 2 ) 2 ) 7 0 在这里仅是给出m 的一个经验值。 另外，当所选阙值中的d e l t a 偏小时，生成元自j 的p o w e r 边画出后断断 续续；而d e l t a 偏大时，只、p 2 徊j 的p o w e r 边画出后就比较粗重。因此可通 过调整d e l t a 的值来总体改变p o w e r 边的粗细。 4 3 3 相邻生成元的权重对p o w e r 图的影响 对于两个权重分别为w ，w ：的相邻生成元p l ( x i , y 。) ，p 2 ( x 2 ，y 2 ) ，若 w l = w 2 ，则p j 、p 2 之间的p o w e r 边恰是p l 、p 2 的垂直平分线( 见图8 ( a ) ) ；若 w i w 2 ，则p l 、p 2 之白j 的p o w e r 边偏向p 2 ，即p i 的p o w e r 多边形区域较大( 见 图8 ( b ) ) ；当w l ，w 2 相差比较大时，生成元p 2 位于p l 的v 区域内，图8 ( c ) 示例 了这种情况，其中p l ( 1 0 0 ，1 0 0 ) ，p 2 ( 2 0 0 ，2 0 0 ) ，b ( 2 5 0 ，2 5 0 ) ，w l m - = m ， w 2 = 0 ，w 3 = 0 田瑚 第2 0 页 囝o ) f 1 0 0 0 河北师范大学硕士研究生学位论文 围“) - = 踟 图8 权重对p o w e r 图的影响 4 4 与其它算法的比较 如前所述，生成p o w e r 图的已有算法常见的有：正则三角化构造法与离散 构造法，下面将本算法与前二者做一个比较： 正则三角化构造法需借助于p o w e r 图的直线对偶图，几何结构复杂，不易 实现，在该算法中，当定点集s 有退化情况( 即点集s 中有三点共线或存在四点 到平面上同一点的p o w e r 距离相等) 出现时，需要另外进行讨论；生成元的多少 对于近似效果影响很大，当生成元增加到一定程度，会带来空间及时问的效率 低下，误差积累造成精度难以控制等问题。并且，由对偶图到p o w e r 图的映射 也是不可避免的过程。 而离散生成法虽有效避免了正则三角化构造法的上述不足。由每个生成元 本身出发，定点集s 是否退化对算法不产生影响；由于光栅扫描显示器的显示 屏幕由有限个像素点构成，而算法时间复杂度只与像素点个数有关，增加生成 元个数基本不影响图形生成速度，因而可使效果达到理想程度。但此方法需提 前做大量辅助工作，包括设置距离表、边界的抽取及区域涂满的判定等辅助 工作量较大且数据结构较复杂。 因此，本文所提供的算法与以上两种算法相比较，明显具有以下特点： 1 仅从p o w e r 图的定义、性质出发，无需借助于复杂的几何结构，思路简 第2 1 页 河北师范大学硕士研究生学位论文 洁明了； 2 程序设计上也不需要复杂的辅助数据结构，设计简单，易操控，节省了 大量预处理时间和存储空间； 3 生成元个数的多少不影响执行效率； 4 该算法可推广至任意阶数和任意生成元数的高阶p o w e r 图。 4 5 作图实例( 用vc + + 6 o 实现) 本文提供的算法己在v i s u a lc + + 6 0 环境下编程实现，图9 所示为由该算法 生成p o w e r 图的过程实例，图l o 是由该算法生成的1 5 0 个生成元的p o w e r 图。 其中各生成元的坐标由r a n d ( ) 随机产生，权重由r a n d o 3 5 0 随机产生。 囝( ) 髓瓠差同岿! 成元囝c b ) 生成p 皑盯图的过程 圈c c ) 生成p 一圈 图9 扫描法生成p o w e r 图的过程图 第2 2 页 河北师范大学硕士研究生学位论文 图1 0 扫描法生成1 5 0 个 生成元的p o t e r 图 其中黑点代表生成元细线代表p o w e r 边 第2 3 页 河北师范大学硕士研究生学位论文 第五章p o w e r 图的应用实例 5 1 应用实例 如下是石家庄东南地形图，本文以石家庄市东南区域网通营业厅分布为例， 通过扫描生成算法构造p o w e r 图的模型分析其分布控制区域。 石家庄市东南区域网通营业厅分布如图1 l 所示。从图中可以看出，石家庄 市东南区域有五所网通营业厅。 图1 1 石家庄市东南区域网遁营业厅分布图 其中红色数字标注的为网通营业厅 居民交纳电话费时，选择到营业厅交费是比较方便的，人们选择营业厅交 费的时候，一般会遵循“就近原则”。因此，营业厅的覆盖区域应由平面欧氏距 离决定，同时，影响其覆盖区域的因素还有附近居民的使用人数、服务设施的 先进程度等等。因此，综合上述各因素为其赋不同的权值分别代表它们的不同 影响能力，这样就构造出以几家营业厅为生成元的p o w e r 图模型，结果如图1 2 和图1 3 所示，图1 3 中数字代表它们的不同权值。 第2 4 页 河北师范大学硕士研究生学位论文 图1 2 以网通营业厅为生成元构造的p o i c r 图 图1 3 以网通营业厅为生成元 生成的p o w e r 图 其中数字代表各营业厅的权值，黑点代表生成元，细线代表p o w e r 边。 第2 5 页 河北师范大学硕士研究生学位论文 由p o w e r 图理论，权值较大的生成元的覆盖区域应较大，但由图1 2 和图 1 3 可见，东岗路三禾营业厅权值较小( 比广安营业厅权值小) ，但它的覆盖区 域却较大( 比广安营业厅覆盖区域大) ，这样就造成了东岗路三禾营业厅附近广 大居民交费困难，时常出现多次去交费才能交上的情况，或者要去较远的营业 厅去交，严重影响居民生活，从这个意义上来说，营业厅分布不合理，在该区 域应增设营业厅，以满足人们的需求。 5 2 应用前景 在具体应用当中，我们可以根据实际情况综合各方面的因素，给每个营业 厅赋以合理的权重值，用p o w e r 图模型来分析营业厅覆盖区域情况，并根据实 际情况调整营业厅的布局，使现有资源得到充分利用。 另外，如前所述，p o w e r 图已经在社会某些领域得到一定应用，随着计算 机技术的深入发展及广泛应用，p o w e r 图的应用范围必将更广，比如，城市规 划问题，各商场、医院、政府部门等重要场所的设置，可以把这些场所设为生 成元，给它们赋以不同的权值，从而生成p o w e r 图，利用该图分析各场所覆盖 区域，从而给它们以合理的位置，更加方便人民的生活。再比如，绿化问题， 可以以某些绿化带作为生成元，赋以合理的权值，通过生成的p o w e r 图分析绿 化带的覆盖区域，从而计算出人均绿地面积，就可以分析出该区域的绿化率是 否达标。 总之，随着计算机技术的发展以及p o w e r 图理论自身的不断成熟，展望未 来，它必将在社会各个领域得到更广泛的应用。 第2 6 页 河北师范大学硕士研究生学位论文 第六章总结与展望 6 1 本文工作总结 p o w e r 图作为v o r o n o i 图的一种重要推广，它是加权v o r o n o i 图将欧氏距离 推广到p o w e r 距离形成的，具有很大的实用价值。本文在现有的p o w e r 图理论 基础上，给出了p o w e r 图不同于以往算法的一种新算法扫描生成法，该算法 利用屏幕由离散像素点构成这一特点，计算屏幕上的每个像素点与生成元的 p o w e r 距离，然后比较排序，根据p o w e r 边上的点到两相邻生成元的p o w e r 距 离相等的特点，从而画出p o w e r 边，生成p o w e r 图。该算法简洁易懂，不需要 复杂的数据结构，并且可推广到高阶