（基础数学专业论文）线段加权voronoi图的离散生成.pdf

学位论文原创性声明 本人所提交的学位论文线段加权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 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 i s u a lc + + 语 言实现的主要源程序。 关键词：v o r o n o i 图 线段加权离散 4 河北师范大学硕士研究生学位论文 a b s t r a c t l i n e s e g m e n tw e i g h t e d v o r o n o i d i a g r a m i sa l l i m p o r t a n t g e n e r a l i z a t i o no ft h eo r d i n a r yv o r o n o id i a g r a mi nt w os i d e so fb u i l d i n g e l e m e n ta n dw e i g h t t h ea u t h o ro ft h i sa r t i c l es h o w su sh o wt og e n e r a t e l i n es e g m e n tw e i g h t e dv o r o n o id i a g r a mw i t had i s c r e t ec o n s t r u c t i o n t h e m a i ni d e a so f t h et h e s i sa r e f i r s t l y , 0 1 1t h er e s u l to f r e s e a r c h e dv o r o n o i d i a g r a m s ，t h et h e s i se x p a n d s t h ep o i n t e db u i l d i n ge l e m e n tt ol i n es e g m e n t ， a tt h es a n l et i m e ，w ep r o v i d et h ed e f i n i t i o no fl i n es e g m e n tw e i g h t e d v o r o n o id i a g r a m ；s e c o n d l y , w ep r o v i d et h em a i ni d e ao ft h ed i s c r e t e c o n s t r u c t i o n ，b u i l d i n g a r i t h m e t i co ft h ed i s c r e t e c o n s t r u c t i o n ，k e y t e c h n i q u e ，c o m p a r ea n da n a l y s e s w i t ho l dm e t h o di nl i n es e g m e n t w e i g h t e d v o r o n o id i a g r a m ；t h i r d l y , w eu s el i n es e g m e n tw e i g h t e d v o r o n o id i a g r a mt os o l v ep r o b l e m so fv i r e s c e n c ea n dw a t e ra r e a s p a r t i t i o n ；a tl a s t ，w eg i v et h em a i n r e s o u r c ep r o g r a m sw h i c hc o n c e r n e di n t h i sp a p e ra n dr e a l i z ew i t hv i s u a lc + + l a n g u a g e k e y w o r d s ：v o r o n o id i a g r a m ，l i n es e g m e n t , w e i g h t e d ，d i s c r e t e 河北师范大学硕士研究生学位论文 第一章绪论 1 1v o r o n o i 图简介 v o r o n o i 图是计算几何的一个主要分支，在计算几何的理论研究和应用研 究中起着重要作用 1 1 1v o r o n o i 图的产生背景 v o r o n o i 图是俄罗斯数学家g v o r o n o i f l z j 于上世纪初提出的，在对二次型 的研究中首先使用了这种图，后被人们称之为v o r o n o i 图，也有人称之为 d i r i c h l e t 区域。而气象学家将该图的二维形式命名为t h i e s s e n 多边形纠，物 理学家则将其三维形式用来纪念w i g n e r 和s e i t z ! ” 1 1 2v 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 图在各方 面的扩展，其中包括：生成元的多样化，由点为生成元扩展为线段、圆弧、圆、 甚至是任意多边形；生成方法的多样化，除一些经典算法外又增加了如：离散构 造法。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 i 图、广义v o r o n o i 图研究等等。 1 2 论文的研究内容 线段v o r 晶o i 图是将普通v o r o n o i 图的生成元由点扩展为线段；而加权 v o r o n o i 图是对y o r o n o i 图的生成元赋以权重值而形成的肿j ；那么如何将这种 以线段为生成元加权后的v o r o n o i 图用离散的方法来生成，生成算法中使用哪 些关键技术，线段加权v o r o n o i 图有哪些应用，都是本文要解决的问题。 6 河北师簸大学硬士研究生学位论文 1 3 论文的组织结构 本文共分五部分 第一章为绪论，简单介绍了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 图 最简单、最基本的v o r o n o i 图，是平面上的以点为生成元的v o r o n o i 图。 2 1 1v o r o n o i 图的定义 定义2 1 1 ：给定平面上的点集s = p 。，p ：，p ，将由 圪( n ) = n d d ( p ，b ) d ( p ，乃) ) j ( f = 1 2 ，栉) 所给出的对平面的分割，称为以点 p ( f = l ，2 ，疗) 为生成元( 或母点) 的 v o r o n o i 图，简称为v o r o n o i 图( 见图l ，图 中黑点为生成元) ，其中a ( p ，只) 为点p 和点p 。 图iv o r o n o i 图 河北师范大学硕士研究生学位论文 之间的e u c l i d 距离。该图的顶点和边分别称为v o r o n o i 点和v o r o n o i 边。 显然，区域吒 ) 是由平面上所有到n 的距离比到s 中其它点的距离都小 的点组成的集合。 2 1 2v o r o n o i 图的基本性质f 1 2 j 性质lv o r o n o i 边由相邻两母点问的垂直平分线或该直线上的线段、射线 构成。 性质2k ( 只) n 吒( n ) = m ( f j ) 性质3 圪( 只) ( f = l ，2 ，疗) 是对平面的一个分割，即将平面分成互不相 交的n 个部分。 以上性质证明见文献1 2 1 性质4 生成元只的v o r o n o i 区域矿( 只) 无界的充分必要条件是 p ，eb c h ( p ) ，其中，b c 日( p ) 表示生成元集合s 的凸壳。 性质5n 个点的点集s 的v o r o n o i 图至多有2 n 一5 个v o r o n o i 点和3 n 一6 条 v o r o n o i 边。 性质6 点集s 中的点只的每一个最近临近点确定矿( 只) 的一条边。 2 2v 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 图来解决与“最近邻近”相关的问题，其中包 括：最近邻近点问题，最大空圆问题、最小生成树及最大化最小角的三角剖分等 问题。 在最优化配置领域中，解决了使交通费用最小、操作时间最少的设施配置闯 题，包括城市运输、机器人运动设计、超大规模集成电路芯片的设计及设备规划； 解决了使利用者限制最小的优化配置，如校区的合理划分问题；最短光缆线路问 题；平均使用时间最少的点设置，如：公交车站牌设置问题：移动设施服务点的 最优配置，如：移动车问题；基站配置与信号测试点选址问题等等。 在模式识别、数据压缩领域中，特别是识别文字、图像时，往往要先对其做 8 河北师范大学硕士研究生学位论文 细化处理，抽取出要识别对象的骨架，根据骨架来识别图像，还可利用骨架恢复 原始图像，压缩原始图像，而这个骨架的主体其实就是v o r o n o i 图 在其它许多方面如：数据压缩、图像处理、移动通讯中的频率分配、树皮和 皮肤纹路的模拟、神经网络、城市及地域规划以及在物理学、化学、生态学、经 济学、结晶学、调查学、静态学、考古学、地质学等学科都有着广泛的应用。 第三章v o r o n o i 图的几种主要生成算法 构造平面点榘s 的v o r o n o i 图的算法有许多种。其中传统的算法包括半平 面的交、随机增量算法、分治法、平面扫描算法等。近期出现的一些新的算法， 诸如：离散生成法、结晶法等，均具有较高的效率，构造算法的思路及数据结构 相当新颖实用。 本章介绍几种：维平面上的普通v o r o n o i 图的构造方法。首先简单介绍半 平面的交、随机增量法等传统算法，随后重点介绍离散生成算法。 3 1 构造v o r o n o i 图的经典传统算法 l 、半平面的交”1 半平面的交是生成v o r o n o i 图的最直接的方法。利用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 图。 2 、增量构造法”1 对定义2 1 1 中s 的n 个生成元，按定方式对其排序，如从p t 到p 。设 v 表示前i 个生成元点p j ，p ；的v o r o n o i 图。从v 1 开始，每增加一个生成元点 p ( i n ) ，对v 进行局部重新剖分，得到v ( 见图2 的图( a ) ) 。在由v 一- 扩展至 v ( n = 3 ，4 ，) 过程中，有两个关键步骤( 见图2 的图( b ) ) ： 图2 增量构造法的两个步骤 9 河北师范大学硕士研究生学位论文 第一步：寻找最近邻元。从v 对应的生成元点p l ，”，p 。中，寻找与新增 生成元点p 。最近的生成元点p 。，。 第二步：局部更新。从线段p , p 。，的垂直平分线开始，找此垂直平分线与 v o r o n o i 多边形v t t ( p i ，) 的交点，并确定与其邻近的v o r o n o i 多边形v 。( p “。) ) 。 然后画边p p n 的垂直平分线，并找其与v o r o n o i 多边形v 。( p 。，) 的另一令交 点和邻接的多边形v 一( p 。) ；循环一周，就可获得p ；的v o r o n o i 多边形v ；。 逐个添加生成元( 或母点) ，每次添加后更新v o r o n o i 边 3 、分治法“1 用分裂线按点的坐标的中值分割点集，至每个子集含生成元数小于或等于 4 。每个子集各自产生v o r o n o i 图后，不断合并相邻子集。 4 、平面扫描算法“” 通过平面上的一条扫描线由左至右扫描。当扫描到某一部分时，就构造该 部分的v o r o n o i 图，直至扫描终止。 3 2 v o r o n o i 图的离散构造算法i j i l 3 2 1 离散v o r o n o i 图的定义 为了准确表述v o r o n o i 图的离散构造算法，先将v o r o n o i 图用离散的形式定 义如下：设屏幕上任一像素p 的坐标为( x , y ) ，( o 工k ，o j ，1 ) ， 其中x 和y 均为整数，k 和1 分别为屏幕坐标系中x 坐标和y 坐标的最大值。两 像素点p l ( 五，y 1 ) 、p 2 ( x 2 ，y 2 ) 的距离定义为d ( p i ，p 2 ) = ( 毛一茸2 ) 2 + o ，l j ，2 ) 2 。 设p l ，p 2 ，办为屏幕上的n 个点，则只的离散v o r o n o i 区域定义为 li d ( p , p ，) d ( b p ，) f o r_ ，7 i v n ( p i ) 2 叫 o r ip ( p ，p ，) = d ( p ，p ) d ( p ，艮) 7 撕o j ) 惫l 将由上述定义得到的v o r o n o i 图称 为= 维离散v o r o n o i 图，p i ，a ，p n 称 为母点或生成元 3 2 2 离散v o r o n o i 图的性质 ( 1 ) 吒( p f ) n v ( p ，) = o ( i c j ) ( 2 ) v o r o n o i 边由穿插于像素间的 图3 - l 离散v o r o n o i 图的v 0 r o n o i 区域 1 0 河北师范大学硕士研究生学位论文 折线构成。 ( 3 ) v o r o a o i 区域是由到区域中母点的距离比到其它母点的距离都小的像素 组成。如果屏幕上某一像素到两生成元点的距离相等，则该像素属于下标较小的 生成元点所在的v o r o n o i 区域( 见图3 1 ) 3 2 3 离散v o r o n o i 图的画法 1 、基本思想 画离散图的基本思想是：首先对每一个生成元点指定一种颜色，使不同生 成元点之间的颜色互不相同。对每个母点，从母点附近开始，围绕母点以指定的 颜色画点，但在画点之前要先行检查：如果该点已经有了颜色，就越过：否则就 以母点对应的颜色画点当屏幕上所有的像素都画上了颜色时，结束。这时，不 同颜色像素之间即为v o r o n o i 边。图3 2 是具有三个母点的离散v o r o n o i 图生成 过程的示意图。 图3 2 平面v o r o n o i 图的离散生成过程 还要注意一点，按照定义，到若干个生成元点距离相等的像素，属于下标 较小的生成元点的v o r o n o i 区域。因此，画图时先从下标小的生 成元点画起，即按生成元点的下标从小到大画圆。 从母点开始逐渐向外扩展顺序的示意图见图3 3 。 2 ，制作距离表 制作距离表的目的是可以利用它在生成元周围画圆，且便图3 5 画圆顺序 于程序实现， 距离表由满足如下条件的 缸，缈和，组成；血，砂 均为自然数，a x 2 缈， ，2 = ( a x ) 2 + ( 妫2 ，并按 肼 l2 356t0g“垃1 31 4l sl a l ll2223，3 4 4，45i55 a r0i o i2o iol， to ，i2 f ll2si oi ，l i tl 为嚣岛拍 舯f i t1 0t g 舶复烈为墨打3i踅 ss6ttst6t 矗i 43oi2，oi42，5o4 a ， ， 匏飘冀玎柚4 1 薯糖铀堍譬冀乱“笛 河北师范大学硬士研究生学位论文 r 2 值由小到大的顺序捧列。 对于任一生成元点p “力，从距离表中按顺序取出一组( k 缈) ，并对如下 点进行处理： 1 当缸0 ，缈= o 时，处理如下4 点：( x + a x ，y ) ，( x , y 一缸) ，o 一缸，力， ( j ，+ a r ) ； 2 当a x 0 ，a y 0 且缸= 妙时，处理如下4 点：( x + a x , y + a y ) ， + 缸，y a y ) ，0 一缸，y 一缈) o 一缸，) ，+ 缈) ； 3 当缸0 ，缈o 且缸4 y 时，处理如下8 点：o + 觇y + 缈) ， + 缸，y 一缈) ，o 一缸，y a y ) ，( x - 缸，y + a y ) ， + 缈，y + 缸) ， o + 缈，y 一缸) ，o 一缈，y 一缸) ， 一缈，y + 缸) 。 3 ，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 ) 对以不同颜色区分v o r o n o i 区域的v o r o n o i 图进行横向( 如从左 向右) 扫描，如果某像素点与其后续像素点颜色值相同，就将该 像素( 也可以是后续像素) 置为白色，否则将其置为黑色； ( 2 )对全屏幕进行纵向( 如从上到下) 扫描，扫描过程进行同样的处 理； ( 3 )两次扫描完成后，v o r o n o i 边便以指定的颜色画了出来。最后， 对全屏幕进行最后一次扫描( 横向或纵向都可以) ，扫描过程中， 除黑色像素点外，其它像素点全部置为统一背景色( 如白色) 此 时，v o r o n o i 边便以黑色直线段明确表示出来了。 上述的扫描方向不是唯一的，当作v o r o n o i 边的像素也可选择后一个。或两 个都选，扫描过程最多只存在一个像素点的误差。 河北师范大学硕士研究生学位论文 图3 4 显示了v o r o n o i 边抽出过程中的三次平面扫描结果，其中每一个小方 格代表一个像素点。 图3 4v o r o n o i 边的近似抽出 第四章线段加权v o r o n o i 图的离散生成 4 1 加权y 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 图的概念。 4 1 1 点生成元加权的i o r o n o i 图 定义4 1 1 设只( f = 1 , 2 ， ) 为二维欧氏空间( 平面) 上的n 个互不相同 的点， ( f = 1 2 ，脬) 是给定的1 1 个正实数，称 咖轳【 p 掣 半 为点只的权重为 的v o r o n o i 区域，其中d ( a a ) 为p 和n 间的e u c l i d 距离。 如果，_ ，时，v d p , ，4 ) n ( 乃 ) 非空且非单点集，则称( 只，五) n 氏巳乃) 为 只和见间的加权v o r o n o i 边，其中( p ，丑) 是( 乃五) 的闭包。两条以上v o r o n o i j 可北师苑大学硕士研究生学位论文 边的交点，称为加权v o r o n o i 点也就是加权v o r o n o i 区域的顶点将 屹( 只，名) ( j = l ，2 ，丹) 及其边界，称为以只( ，= 1 2 ，一) 为生成元， ( ，= 1 ，2 ，力 为权重的点生成元上加权的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 2 线段加权的v o r o n o i 图l 将加权v o r o n o i 图的生成元由点扩展为线段，就得到了线段加权v o r o n o i 图。 一、线段加权v o r o n o i 图的定义 定义i 设厶o = l ，2 , - - - , 疗) 为二维欧氏空间( 平面) 上的疗条互不相交的线段， 槲二川是给撕个正娥枞，= 【= | p 掣 五时，e 时，# y 1 m a x ； 1 7 河北师范大学顼士研究生学位论文 ( 注：w m a x 为各生成元权重值的最大值。) ( 2 ) i f ( d x l = = d y l ) 处理包括d x l = o 或d y l = o 的四种情况 l ，2 ，3 。4 i n tx = p 一 x 土d x l ： i n ty = p 一 y d y l ： i f ( p d c 一 g e t p i x e l ( x ，y ) = 0 ) p d c 一 s e t p i x e l ( x ，y ，f - c o l o r ) ： p - d 2 = d i 2 ： ) e l s ep - a 2 = d i 2 ： ( 注：s e t p i x e l ( x ，y ，p - c o l o r ) 表示将( x ，y ) 点置为c o l o r 色) e l s e 其它八种情况 1 ，2 ，3 ，4 i n tx = p 一 x d x l ： i n ty = p 一 y d y l ： if ( p d c 一 g e t p ix e l ( x ，y ) = = c o ) p d c 一 s e t p ix e l ( x ，y ，p - c o l o r ) ： p - d 2 = d i 2 ： e l s ep - a 2 = d i 2 ： 1 1 5 ，6 ，7 ，8 x = p x d y l ： y = p - y d x l ： i f ( p d c - g e t p i x e l ( x ，y ) = - - c o ) i p ) c - s e t p i x e l c o l o r ) ： p - d 2 = d i 2 ： 河北师范大学硕士研究生学位论文 j e l s ep - a 2 = d c i 【2 】： i f ( ( p - a 2 ) ( ( p 一 d 2 ) + 2 * s q r t ( p - d 2 ) + 1 ) ) 当一周全画满 时则从l 中删除此生成元； 步9 分别横向及纵向扫描全屏幕，若某一像素点与其后继像素点颜色不 同，将其置为黑色； 步1 0 横向( 或纵向) 扫描全屏幕。将黑色像素点保留原色，其它像素 点置为白色； 步l l 画出线段生成元：结束。 4 3 实现算法的几个关键技术 4 3 1 两条线段是否相交的判断 将生成元推广至线段后，首先遇到的问题就是如何生成互不相交的若干条 线段生成元。那么具体函数的做法是：先画出两条线段来，判断其是否相交，相 交则舍去，不相交则添加。再添加第三条线段时，用同样的方法可以判断出它是 否与前两条相交，依此类推即可。这样解决问题的关键就转化为如何判断两条线 段是否相交。 那么如何判断两条线段是否相交昵? 设：线段l经过已知点( z i o ，乃。) ，( 一，m 。) ，其参数方程为 x - - - 2x i o l l ! x 。，l l 一翟 f l i y = m o + ，i ( m l 一月o ) 线段2 经过已知点0 。，y 。) ，( x 2 ，乃。) ，其参数方程为 x - - x ，。2 0 + t z ( x 2 , - x ，2 ，o ： f 2 f 0 ，1 】 【y = + t 2 ( y 2 i 一儿o ) 。1 联立线段l 和线段2 解以z ，y ， ，t ：为参数的四元一次方程组并确定t ，t 2 的范围， 如果f le 【o ，l 】且f 2 【o ，1 1 ，那么两线段相交；如果f 。仨【o ，l 】或r 2 【o ，1 1 或 ，t 2 薯【o ，1 1 ， 则两线段不相交。 1 9 河北师范大学硬士研究生学位论文 两线段可能平行，这时两条直线的斜率相等即苎l 二丛：丝l 二2 翌，平行时又 一i x l o工2 l x 2 0 分为两种情况：( 1 ) 平行不重合，可添加：( 2 ) 重合，舍去。 这样我们就可以通过判断两条线段是否相交来添加若干条线段生成元。 4 3 2 母点的设置原则 如何在线段生成元上提取母点，是实现算法的又一关键技术。将所有生成 元的端点设置为母点，生成元上的母点个数原则上与生成元边界长度成正比，等 间距提取，若间距过小则生成速度慢且有些母点被提前删去，影响作图效果。若 问距过大，虽然生成速度加快了，但生成元形状却不能有效的体现，所以母点选 取应适当。 4 3 3v 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 区域涂满的判定方法。 由于屏幕由离散的像素点构成，在某生成元线段上取若干母点，当对某个 母点逐渐向外扩展画圆的过程中，对距离表中某一r 2 值，用相应的缸和值画 圆，其结果一般不是封闭的圆周。此时需继续从表中取下一组缸和缈，继续填 涂，这样反复进行一定次数之后，才能形成封闭圆周。于是，对屏幕上某个生成 元母点。在按距离表顺序取值进行画圆的过程中，从某一r 2 ( 用d 2 表示，称d 为 内径) 值开始画点，存在一个能形成封闭圆周的最小的另一r 2 值( 用c 2 表示， 称口为外径) ，显然，当外径与内径的差大于或等于i ( 即口1 + d ，也就是 口2 d 2 + 2 d 2 + 1 ) 对，该填涂过程就能形成一个封闭的圆周。 图4 2 显示了当r 2 - - 1 6 ，口2 = 2 5 时形成封闭圆周的示意图。 图4 2 封闭圆周的形成 河北师范大学硬士研究生学位论文 设屏幕上有疗个生成元母点，按上述方法轮流对每个生成元母点进行一层层 向周围呈圆形填涂。当对某生成元母点p 填涂一周时，如有未被填涂的像素点， 就继续填涂下去。若该过程中，发现莱圆周上的所有像素点都被填涂，就将该生 成元母点从所需处理的生成元母点集合中删去。 4 。3 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 边，其 余部分均置为背景色( 如白色) ，把这种过程称为y 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 图的区域边界便以指定的颜色( 黑色) 画了出来。最后进行全屏 幕扫描，只保留黑色象素点，其它颜色的象素点全部置为背景色( 如白色) 。这样， 线段加权y o r o n o i 图的边界就被以黑色线段或曲线的形式提取了出来。其结果便 为由指定颜色画出的线段加权v o r o n o i 图。 4 4 作图实例( 用v c + + 6 o 语言实现) ( 1 ) 不同角度两条线段加权的v o r o n o i 图 2 i 河北师范大学硕士研究生学位论文 ( 2 ) 3 0 0 条线段的v o r o n o i 图与3 0 0 条线段加权的v o r o n o i 图的比较； 4 5 与已有算法的比较和分析 目前比较成熟的v o r o n o i 图的构造法主要有两种：l 、直接以点为生成元的 v o r o n o i 图的构造法，如：分治法，逐点添加法等：2 、近似构造法。这两种方 法在历史上对于解决构造v o r o n o i 图问题曾起着重要作用，但有以下不足： 第一种方法，由于在实现过程中需要计算两生成元间的v o r o n o i 边的形状， 这对于线段生成元，该方法可以实现，但实现起来比较困难。 第二种方法是到目前为止的一个比较好的方法，能处理任意图形的生成元， 但它的问题主要是； ( 1 ) 母点多少对于近似效果影响很大，当母点数目增加到一定程度后，就会带 来诸如空间效率、时间效率严重低下，误差累积造成精度难以控制等一系列问题。 河北师范大学硬士研究生学位论文 ( 2 ) 判断并消除同一生成元上两母点闻的v o r o n o i 边的工作。实现起来也相当 复杂。 因此，与已有的v o r o n o i 图的构造法相比，本文使用的离散构造法，具有明 显的优势，主要表现在； i )由于光栅扫描显示器的显示屏幕由有限个像素点构成，而算法 的时间复杂度主要与像素点个数有关，与母点个数关系不大， 所以增加生成元的个数基本上不影响图形生成速度，从而可使 近似效果达到理想的程度； “) 算法的实现与生成元的具体形状无关： i ii ) 算法不关心生成元之间的v o r o n o i 边的几何形状，无需复杂计 算； i v ) 算法不存在误差问题。 第五章应用实例 线段为生成元的加权v o r o n o i 图在地理信息系统及城市规划等方面有着重 要应用。如：区域的划分，净化能力分析，交通道路规划等等。以下利用线段加 权v o r o n o i 图对绿化问题和水域划分问题进行简要说明。 5 1 绿化问题 随着生活水平的不断提高，人们开始关注城市空气质量，居住地周边环境， 因而建设了许多绿化带，如：绿化区，街心公园，民心河等等来净化空气，美化 环境，方便人们健身娱乐。那么我们将每个绿化带视为线段，因为绿化带中包括 草坪，树木，人工湖，民心河等，并且绿化带的面积有大有小，所以不同的绿化 带所能净化空气的能力范围不同，将每个绿化带的净化能力视为其权重。来判断 哪些区域还需要扩大绿化范围。 以石家庄市区几个绿化带为例，将其视为线段生成元，应用离散构造法生 成v o r o n o i 图，对其净化区域和覆盖状况进行简要分析。 河北师范大学硕士研究生学位论文 如图5 ，l l 深色部分代表绿化带， 图5 1 1 将其抽象出来视为线段，如图5 1 2 图5 1 2 利用离散的生成方法可以达到最佳划分，如图5 。1 3 图5 1 3 如图5 1 4 石家庄市区被划分为abcdefghi 九部分，仔细观察其 中v o r o n o i 点离绿化带远的区域即为需要绿化区，如图所示石家庄的中北部和中 东部即为需要绿化的区域 河北师范大学硕士研究生学位论文 图5 1 4 5 2 水域划分问题 如图5 2 1 ，黑线所示为某国家某区域的河流分布图，将每条河流抽象为线 段，每条河流的水流量大小、缓急、水质、宽窄深浅等不同，可利用价值有所不 同，如：饮用，兴建水利工程，开发旅游项目等，所以将每条河流的可利用价值 设为权重，将区域划分，根据就近的原则，合理开发和配置水资源。 将河流抽象为线段，如图5 2 2 图5 2 i 河北师范大学硕士研究生学位论文 图5 2 2 利用离散生成法得到最佳划分如图5 2 3 ， 图5 2 3 划分后区域被大致分为abcdefg 七部分，如图5 2 4 ，当地的居民可以根 据这一划分合理分配利用水利资源，从而达到节约能源的目的。 图5 2 4 j 可北师范大学硕士研究生学位论文 第六章总结与展望 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 图在绿化问题和水域划 分问题中的两点应用。 6 2 进一步研究工作 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 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 e t e r sc o n t i n u sal at h d o 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 d 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 s f o r m e sq u a d r a t i q u e s p o s i t i r e sp a r f a i t s ，j r e i n e a n g e w ，m a t h ，1 3 3 ，9 7 1 7 8 ， 1 9 0 7 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 e 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 d e u x i 6 m em d m e i r e ：r e c h e r c h e ss u rl e s p a r a l l d l l 0 6 d r e s p r i m i t i v e s ， j r e i n e a n g e w m a t h ，1 3 4 ，1 9 8 2 8 7 ， 1 9 0 8 ：1 3 6 ，