（计算机科学与技术专业论文）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 图生成首尾相连的螺旋 扫描路径也可以应用到近年来得到快速发展的实体制造技术。 关键词：v o r o n o i ，路径，规划，算法 a b s t r a c t a b s t r a c t t h ep u r p o s eo ft h i ss t u d yi sg e n e r a t i o ne n d - t o e n ds p i r a ls c m m i n g p a t hb a s e do n t h ev o r o n o id i a g r a m t h ef o c u so ft h et h e s i si sa l g o r i t h m sa n ds t r a t e g i e si n t e r r e l a t e d i nt h ep r o c e s so fg e n e r a t i n gs p i r a l o f f s e t t i n gg r o u n d e do nv o r o n o id i a g r a m p r e s e n t i n gt h e d e f t n i t i o n so fa s s o c i a t e db i s e c t o ra n dn o n - a s s o c i a l 【e db i s e c t o r a e c o r d i n ga si n i t i a l i n t e r s e c t i o n sc a n d i d a t e s ，d i v i d e sc o n t o u rb i s e c t o r si n t ot w o g r o u p s ：f l g s o c i a t e da n dn o n a s s o c i a t e db i s e c t o r sf o rd e c r e a s i n gt h en u m b e ro f c a n d i d a t eb i s e c t o r sw h e ns e a r c h i n gi n n e r - m o s tp o i n t s p r e s e n t i n gt w on e wv i e w p o i n t s t h a tb a s e do nt h ed e f i n i t i o n s t h el e m m ao fc i r c u l a t i o nt i m ew h e ns e a r c h i n gf o r i n n e r - m o s tp o i n t s ；t h el e m m ao fi n n e r - m o s tp o i n tm u s tb ea s s o c i a t e db i s e c t o rw h e n s c a n n i n gn o n - a s s o c i a t e db u tn o ta l li n n e r - m o s tp o i n t sc o u l db ef o u n d s e a r c h i n g i n n e r - m o s tp o i n ta l g o r i t h mt h a tg r o u n d0 nt h el e m m a s t h ea l g o r i t h mh a sl e s si n i t i a l c a n d i d a t eb i s e c t o r sa n dl e s sc i r c o l a t i o nt i m e i nam o d e r nc n c m i l l i n ga n dr a p i d p r o t o t y p i n ga n do t h e rl a y e r e dm a n u f a c t u r i n gt e c h n o l o g y , p r o c e s s i n gp a t hp l a n n i n g p r o c e s si sa l w a y so n eo ft h em o s ti m p o r t a n te l e m e n t s ，a n dt h ek e yf a c t o re f f e c t p r e c i s i o na n de f f i c i e n c y t h ec o n c l u s i o no ft h ep r o j e c tt h a tp r e s e n t ss p i r a lt 0 0 1 p a t h p r o g r a m m i n gb a s e do nv o r o n o id i a g r a mc o u l db ea l s ou s e di nr a p i dp r o t o t y p i n g k e yw o r d s ：v o r o n o i ，p a t h ，s c h e m e ，a l g o r i t h m 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：耆仅1 萄 伊饵弓月夕日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月目年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名： 纠年弧，日鼬f五q 月 。 第1 章引言 第1 章引言 1 1v o r o n o i 图算法 v o r o n o i 图是俄国数学家g v o r o n o i v o r o n o i l 9 0 8 在研究邻近问题时提出来 的，是关于空问邻近关系的一种基础数据结构。在不同的领域，v o r o n o i 图有时 也被称为t h i e s s e n 多边形、d i r i c h r i t 网格、或w i g n e r - - s e i t z 区域等。平面上一 个点集p 的v o r o n o i 图是对平面的一个划分，每个分区表示一些点的轨迹，这些 点到p 的一个元素比到其它元素更近。平面多边形的v o r o n o i 图也是对平面的一 种划分每个分区从属于多边形的一条边，分区内的点到该边比到其它边距离 近。 在v o r o n o i 图中，被用来划分空间的各个基本图形元素一般被称为对象。最 基本的v o r o n o i 图是以平面点集p 为对象的v o r o n o i 图，v o r o n o i 图的定义可以推 广到二维或三维，也可以推广到二阶或高阶( 以两个站点或多个站点为一组划分 邻近区域) ，也可以进一步推广到对象包括线段或多边形的广义v o r o n o i 图 1 1 】【2 】【3 】【4 】。另外，关于移动点的v o r o n o i 图【5 】【酊、带权的v o r o n o i 图【7 】【8 】、以及曲面 上的v o r o n o i 图【9 】【1 0 】也被人们所研究，并且有着具体的应用背景。 随着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 m n o i 图。这些不同 形式的v o r o n o i 图分别将平面和空间根据距离的远近关系进行了一定的划分。每 个子区域分别从属于一个图形元素，并且分区内的点到该图形元素的欧几里德 距离比到其他图形元素的欧几里德距离近。最基本的v o r o n o i 图是以平面点集p 为元素的v o r o n o i 图，它将平面划分成凸多边形形状的v o r o n o i 区域，p 中的每 个元素对应一个这样的区域，使得内的任何点到p i 的欧几里德距离比到其 他元素的欧几里德距离近。同理，平面内曲面多边形的v o r o n o i 图是对有限区域 的这样一个划分：区域内的点到相应边界轮廓元素i 的欧几里德距离比到其 他轮廓元素段的欧几里德距离近。本文主要研究v o r o n o i 图在机械加工路径规划 第1 章引言 中的应用。因此，重点放在平面多边形轮廓的v o r o n o i 图生成上。 i l “1 提出利用程序设计方法中的分治i v i d e d - c o n q u e r ) 思想来构造v o r o n o i 图，这是 v o r o n o i 图构造算法上的一个里程碑。后来的许多学者在l e e 的分治算法基础上逐步设计出 了算法时间复杂度为o ( n l o g n ) ( n 为轮廓c 的线段数) 的分治算法。1 9 9 8 年，m a r t h ah e l d f ”】 在其增长算法( i n c r e m e n t a l a l g o r i t h m ) 的基础上提出了波阵面传播法，形成了一个完全不同于 分治算法思想的新的v o r o n o i 图算法。该算法对于单连通域情况的时间复杂度为o ( k l o g h ) ( k 为初始平分线个数，h 为初始交点个数) 。目前对两种算法思想的应用中大多采用双连接边 表结构( d o u b l y - c o n n e b t e d l i s i ) 存储数据。出于清晰表达整个v o r o n o i 区( v o r o n o i r e g i o 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 区，每个对象对应某个区，v o r o n o i 区由到这个对象的欧 几里德距离小于到任何其他对象的欧几里德距离的所有点组成，区域的边界由 到这个对象的欧凡里德距离等于到其他对象的最小欧几里德距离的所有点组 成。区域的边界称为v o r o n o i 边或平分线。v o r o n o i 图包含以下几个基本概念对 象( o b j e c t ) 、点到对象的欧几里德距离( d i s t a n c e ) 、边或平分线( b i s e c t o r ) 和影 响区( c o n e so f i n f l u e n c e ) 。 v o r o n o i 对象是划分平面的基础，是对点、线段或圆弧等的统称。不同类型 的对象构造v o r o n o i 图的方法和应用范围都不同。本文研究的对象限于点、线段、 圆弧三种。对于内部无孔、洞( 或称为孤岛) 的单连通域，以直线段、圆弧、 优顶点为轮廓边界元素的曲线多边形的v o r o n o i 图的构造算法主要有分治算法 1 3 1 1 4 f l l 】( d i v i d e d c o n q u e r ) 、波阵面传播法【1 5 】1 16 】【1 7 ( w a v e f r o n t - p r o p a g a t i o n ) 。其他 还有f o r t u n e ( 1 9 8 7 ) 1 1 8 】提出了具有同样时间复杂度的离散点和线段v o r o n o i 图的 扫描线法( s w e e p l i n e ) 等。 一系列不相邻线段的v o r o n o i 图可以在o ( n l o g n ) c 1 8 【1 9 】时间内构造。l e e 的分 治算法在计算简单的n 个元素的v o r o n o i 图时可以在o ( n l o g n ) 时间内完成。在 h e l d ( 1 9 9 1 1 1 7 的论文里，作者基于l e e 的思想给出了处理曲线性v o r o n o i 图的处 理细节。对于凸多边形和简单多边形的线性算法，文献【2 0 1 1 2 1 】提出了线性时间内 v o r o n o i 图算法。 2 第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 图。单个对象影响区的边界比较容易构造，算法的 核心是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 边所形成的封闭环。即需 要存储的信息是二维的。这里的“相关”是指直接或间接以特定轮廓边界为定 义边的平分线段。这种复杂的数据结构增加了工程应用的难度f 17 】 2 2 1 。波阵面传 播法最早是在1 9 9 8 年由m a r t a i nh e l d 提出【1 2 】，该算法思想来源于增长法，这里 把这两种算法归并到一起讨论。波阵面传播法的思路是：确定一个v o r o n o i 图的 起始边，将它与其他相邻轮廓元素的平分线集合相交，用最先相交的那个平分 线对起始边裁剪，裁剪后的起始边为最终v o r o n o i 图的一部分( 一个组成边) ； 迭代地进行下去，直到形成整个轮廓边界的v o r o n o i 图。论文【2 2 1 中描述的初始化 平分线以及初始化交点( 该文称“初始化候选交点”) 算法思路是：先初始化所 有平分线，再迭代处理相邻的四个元素的三个平分线得到初始交点集合i 。该算 法较为繁琐，处理量较大。 1 2 机械加工路径规划概述 在普通数字控制加工过程中，型腔加工是非常困难的，虽然有专门的型腔 加工指令但是仍不能满足特殊型腔加：【的需要( 如带岛的型腔：在型腔中有凸 台) ，而一些大型的软件价格昂贵，后处理又困难。在型腔加工中两轴半加工占 到了7 0 一8 0 ，也就是说基本上都是平面加工。 数控加工的关键环节之一是加工轨迹的规划。典型的复杂型腔一般由外轮 3 第1 章引言 廓、内轮廓( 孤岛，可有多个) 和底面三部分组成。在刀具轨迹的生成过程中， 即应保证内、外轮廓和底面的加工精度及加工效率，又要避免过切、漏切、空 走刀等现象。在计算机自动编制数控程序前，必须根据零件的轮廓，产生相应 的刀具运动轨迹。 刀具的尺寸不一样，设计产生的刀具运动轨迹也不一样。因此误差将产生 于刀具的尺寸和刀具运动轨迹的设计算法两个方面。 这时采用的方法通常是行切法或环切法。如图1 1 所示：a 图是行切法，b 图是环切法。 图1 1a 行切法 图1 1b 环切法 利用行切法加工时加工过程简单，但往复直线运动很容易产生过切现象， 并重复顺铣、逆铣过程，精度较低。 环切法是一种常用的计算加工轨迹的算法，通过构造型腔轮廓等距线实现刀 位规划。环切法加工型腔是以型腔轮廓的等距线( 也称偏置线) 作为刀具路径，所以 环切法刀具轨迹计算可以归结为型腔轮廓等距线的构造及连接目前广泛应用的 4 第1 章引言 一种方法是轮廓连续向里收缩构造等距线如图1 1 所示算法步骤如下： 步骤1 按一定的偏置量对轮廓的每条边界分别计算等距线； 步骤2 对各条等距线进行必要的裁剪或延拓，连接形成封闭曲线； 步骤3 处理曲线的自相交，对等距线做有效性测试，判断是否和岛、边界干 涉，去除多余环，得到基于上述偏置量的刀具路径； 步骤4 重复以上过程，直到遍历完所有待加工区域。 环切法是加工精度比较高的方法，问题就在于刀具路径的规划，怎样才能 产生合理的刀具路径，计算的重点在于简化等距线计算中干涉段的判断，提高算 法的可靠性和效率。国内的工作也主要采用这类方法。一般环切法的主要缺陷 是必须对等距线的连接进行判断和处理，去除多余环及自交环，进行大量有效性 测试以避免干涉，但在某些情况下，环的判断和处理是相当困难的。 p e r s s o n 最早提出将型腔的加工区域划分为若干子域每个子域分别对应轮廓 中的某一段，子域中的任一点到对应的轮廓段距离最近，在各个子域中分别构造 对应轮廓段的等距线，在子域边界处衔接，得至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 图的基础是合并树。如图1 2 所示： 5 第1 章引言 c 0 厂、 念。 ( m 图1 2a 型腔边界图1 2 b 平分线形成的二义树关系 图1 1 a 是给定的一个型腔，边界元素以相邻原则进行组合，如果相邻两边 夹角大于9 0 度，则称此两边的交点为优顶点，有两边加一顶点够成一基本单元， 反之则由单个边界元素构成一基本单元。然后建构一个二叉树( 或循环链表) ， 基本单元称为c h n 。这样每两个基本单元就可求出一角平分线，捕捉其交点就 可以求出此型腔的v o r o n o i 图。下面给定一简单型腔的v o r o n o i 图，如图1 3 所 刁i ； 图1 3 简单型腔及其v o r o n o i 图 这样就得到基于型腔边界的v o r o n o i 图，把曲线所围成的区域称之为v o r o n o i 6 第1 章引言 区域，刀具的偏置路径就在各个区内产生，其各个轨迹的交点就在平分线上。 1 3 课题研究内容及论文结构安排 1 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 图算法，使得该算法具有 更小的初始化集合； 设计更加统一、简化数据的存储结构，使得更适应于工程应用； 在分析内点特性的基础上，构造内点查找算法； 提出偏置环的连接策略； 1 3 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 图理论 本章通过归纳和总结，系统化v o r o n o i 图的基本定理、定义等基础理论、平 分线的类型及处理办法等。 第三章v o r o n o i 图算法 7 第1 章引言 本章基于m a r t i n 的波阵面传播法，提出了修改初始化算法后的单连通域 v o r o n o i 图算法；利用c + + 的面向对象优势提出了面向对象的数据结构存储方式 等。 第四章路径规划算法策略 本章论述了内点、峡、单调区的判断算法，提出桥概念、自动生成螺旋 偏置线算法以及相关问题论述。 第五章程序实现 本章给出了基于前几章理论实现的v o r o n o i 图及偏置线生成实例。 第六章结论与展望 本章回顾和总结了硕士研究阶段的工作，并对后续工作的研究方向做了 概括性的描述。 8 第2 章v o r o n o i 图理论 第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 图是以平 面点集p 为元素的v o r o n o i 图，它将平面划分成凸多边形形状的v o r o n o i 区域， p 中的每个元素p i 对应一个这样的区域v i ，使得v i 内的任何点距离p i 比距离 其他元素近。v o r o n o i 图的定义可以推广n - - 维或三维甚至是高维，也可以推广 到二阶或高阶( 以两个元素或多个元素为一组划分邻近区域) 。 v o r o n o i 图的意义在不同的科学领域被发现和重视，已有l 来年的历史。 随着计算机技术的发展，8 0 年代是v o r o n o i 图研究与应用的高潮随后，许多人 对v o r o n o i 图进行了综述或总结。a u r e n h a n m l m e r 于1 9 9 1 年发表了篇包括2 0 多篇参考文献的综述m ，详细总结了v o r o n o i 图的历史、定义、性质、算法、扩 展和应用。f o r t u n 于1 9 9 2 年侧重对v o r o n o i 图的算法进行了比较和分析p 8 1 。 为后续章节提出新的算法，本章主要归纳总结生成v o r o n o i 图必须的计算几 何基础。 2 1v o r o n o i 图定义 从计算几何的观点，v o r o n o i 图把平面分成n 个区域，每个区域包括一 个顶点，该点所在区域是到该点欧凡罩德距离最近的点的集合。设p i ( i = l ，2 ，n ) 为二维欧氏空间( 平面) 上的n 个散乱点，没有任意两个点相同，那么，散乱 点的p i 的v o r o n o i 区域v o o i ) 定义为： v i ) = ( x ：d ( x ，p i ) d ( x ，p j ) ，j i j 2 1 2 ，n 这种对平面的分割，称为以p i ( i - i ，2 ，n ) 为元素的v o r o n o i 图，通常简 称为v o r o n o i 图，如图2 1 所示。其中d ( p p i ) 为p 和p i 之间的欧几里德距离。 9 第2 章v o r o n o i 图理论 图2 1 离散点的v o r o n o i 图 由定义可知，v o r o n o i 图就是对平面上任意给定的n 个点，根据这些点的位 置，将平面分割成n 部分，得到一种由各个元素的v o r o n o i 多边形所构成的对平 面的分割图。它的几何特性有： ( 1 ) v o r o n o i 多边形内的所有点与这个多边形内元素之间的距离比到其他任 一元素的距离都近； ( 2 ) 距v o r o n o i 多边形内元素较近的其它元素与此元素之间形成v o r o n o i 多边形的边： ( 3 ) 多边形的边为距其最近的两元素问的垂直平分线。 普通点集v o r o n o i 图的直线对偶图是平面以该点点集为基础的一个d e l a t m a y 三角剖分。图2 2 示例了平面点集的v o r o n o i 图及其对偶图。 图2 2 红色为v o r o n o i 边，黑色为d e l a u n a y 三角剖分 一般图形v o r o n o i 图是将生成元素由点扩展到任意平面几何图形而形成的一 1 0 第2 章v o r o n o i 图理论 种v o r o n o i 图。 设p 为平面上点，g 为平面上的任意几何图形，定义p 与g 之问的距离为d ( p ，g ) = m i n d ( p ，q ) iq g ) ，其中d ( p ，q ) 为p 和q 之间的欧几里德 距离。设酊，鲒，朗为平面上的几何图形，将 v ( g i ) = n p lp r 2 ，d ( p ，g 。) d ( p ，癣) j l 崩 ( i - - - l ，2 ，n l 所给出的对平面的分割称为有生成元素西( i _ 1 ，2 ，r n ) 确定一般图形 v o r o n o i 图，其中d ( p ，百) 是按前面定义给出的p 到百间的距离。当把元素的 类型从平面离散的几何图形集扩展到平面连续直线和圆弧时，v o r o n o i 图的形成 没有本质区别。 当v o r o n o i 图生成元素是连续直线时，其v o r o n o i 图如图2 3 、2 4 所示。图2 3 所示多边形是一个凸多边形，它有7 个顶点和7 条边。由图中可以观察到凸多 边形p 的v o r o n o i 图是一棵树t ，它的叶是p 的顶点；角平分线上的每个点与多 边形生成元素的两条相邻元素( 轮廓段) 的距离相等，并且v o r o n o i 图中v o r o n o i 边的交点到3 个生成元素( 轮廓段) 的边的距离相等。 而内部结点是与连续生成元素的3 条边相切圆的圆心。对于任意简单多边 形也是如此，v o r o n o i 边上的每个点是圆心，该圆至少与两条边或边的延长线相 切。 图2 3 凸多边形v o r o n o i 图图2 4 带优顶点的v o r o n o i 图 一般v o r o n o i 图研究的对象是平面内离散的点或线段。出于应用考虑， 这里研究的多边形是由点( 优顶点) 、线段、圆弧这三个元素组成的的曲线所围区 域的的边界轮廓，即首尾相连、无相交或自交的j o r d a n 曲线。并且赋予这些轮 第2 章v o r o n o i 图理论 廓段方向：外轮廓逆时针方向，内轮廓顺时针方向。 将轮廓段的类型限制为直线和圆弧是出于简化计算的目的：一般曲线的的 相交程序非常复杂并且轮廓类型在偏置过程中也不是一成不变的( 如三次样条 曲线的偏置线不再是三次样条瞎线) ，这使得算法中的数学计算变的困难和不可 行。并且，现代已经成熟并应用的加工技术中，能够实现直线和圆弧的自动插 补。通过直线和圆弧近似拟合可以对以自由曲线为边界轮廓的图形进行v o r o n o i 图计算。 在计算v o r o n o i 图时牵涉到的相关概念，定理表示如下； ( 1 ) 考虑由直线段和圆弧构成的平面单连通域( 多边形) ，构成多边形的每一 个线段或圆弧称为边界元素；如果与一顶点v 相连的两个边界元素所夹的内角 大于p ，则说v 是“优”的，或称其为优顶点。在计算中，优顶点可当作半径为 零的圆弧来处理。 ( 2 ) 平面多边形的边界元素由直线段，圆弧和优顶点组成。 ( 3 ) 侧轮廓由一个或多个边界元素连接而成。对于平面多边形，集合是指平 面多边形的边界或侧轮廓。 ( 4 ) 元素e 的影响区c i ( e ) 定义为： ( a ) 圆弧的影响区是从其圆心出发，通过端点的两条射线所围区域的闭包； ( b ) 线段的影响区是以通过其端点的两条法线为边界的带状区域的闭包： ( c ) 点的影响区是整个平面。 ( 5 ) 记d 0 ，e ) 为点p 到元素e 的距离。点p 到集合x 的距离为 d 0 ，x ) = m l nm i n d ( p ，e ) 幽并 下述有关点到元素距离的讨论，都限制在元素的影响区内。 ( 6 ) v o r o n o i 图是这样一种图，其上的每一点至少与两条边界元素等距。 ( 7 ) 元素e 相对于集合o 的v o r o n o i 区v a ( e ，o ) 定义为 v a ( e ，o ) 2 p c i ( e ) ：d ( p ，e ) d ( p ，o ) ) 即v a ( e ，o ) 是到e 比到o 距离小的点的轨迹。如图2 5 中e l 的v o r o n o i 区是a b c d e a 。 ( 8 ) 一个角台o f 句v o r o n o i 图为 u v o d ( o ) = e 击ov a ( e i ，o e i ) 平面多边形v o r o n o i 图就是将多边形的内部区域划分为各个边界元素的 1 2 蔓! 童! ! 竺竺! 堕堡堡 v o r o n o i 区。 ( 9 ) 两个分别属于元素e l ，e 2 的v o r o n o i 区的公共边称为v o r o n o i 边，它上 面的点到两个边界元素的距离相等，所以也称其为平分线，记为b ( e l ，e 2 ) ，由下 式给出 b ( e l ，e 2 ) = p c i ( e 1 ) nc i ( e 2 ) ：d ( p ，e t ) = d ( p ，e 2 ) ) 即b ( e l ，e 2 ) 是元素e l ，e 2 的公共影响区内到e 1 和e 2 等距点的轨迹，也 称为元素e l ，e 2 定义该平分线。图2 5 中ab 是e 1 和e 2 的平分线。当e 1 ，c 2 o ，还应当增加一个条件：对任意pe b ( e l ，e 2 ) 和e k e o ( e k e ：e l ，e 2 ) ，有d q ，e 1 ) = d ( p ，e 2 ) d ( p ，e k ) 边界元素之间的平分线是圆锥曲线的一部分。边界 元素v o r o n o i 区的边由该元素和其它元素之闯的平分线构成。这些边界元素称为 平分线的定义元素。定义v o r o n o i 区的边为几何平分线，在偏置距离的极值点处 分割的几何平分线为解析平分线。 类似地，集合x ，y 的平分线是到x ，y 等距点的轨迹，由下式给出 b ( x ，y ) 2 p ：d ( p ，x ) 2d 0 ，y ) ) ( 11 ) 平分线表示为参数表达式，以线上的点到轮廓的距离作为参数。平分 线的2 个端点中，到边界距离较小的点，也就是对应该平分线参数区间下界的 点，称为平分线的尾；到边界距离较大的点，也就是对应该平分线参数区间上 界的点，称为平分线的头。令平分线的方向为由尾指向头，为得到唯一的参数 表达式并使参数沿平分线单调变化，有时必须把一条半分线从参数的极值点处 分为2 条解析平分线。 ( 1 2 ) v o r o n o i 边的交点称为v o r o n o i 节点。一个v o r o n o i 节点至少与2 条平 1 3 第2 章v o r o n o i 图理论 分线相连( 这种情况出现在将一条几何平分线在一点划分成2 条解析平分线的时 候) 。如果一个v o r o n o i 节点是一条平分线的头，则称该平分线为这个v o m n o i 节 点的入边；反之，称该平分线是这个v o r o n o i 节点的出边。 ( 1 3 ) 定义凹槽的封闭曲线称为外边界。如果凹槽内部还有孔或突出( 岛屿) ， 那么组成内孔或突出的封闭曲线称为内边界。 ( 1 4 ) 等距线是把边界线( 直线或圆弧) 按某一距离t 偏移所得的直线或圆 弧。 2 2 相关表达式 求两元素的平分线，就是求到这两元素距离相等点的轨迹。也就是以相同的 距离对两元素做偏置，所得偏置线的交点，以平分线上一点到定义该平分线元 素的距离t 为参数，列出平分线的参数表达式。 v o r o n o i 图是由各个边界元素之间的平分线所构成，所以建立平面连通域 v o r o n o i 图的第1 步是建立相邻边界元素的平分线。求两元素的平分线，就是求 到这两元素距离相等点的轨迹。由于包括用半径为0 的圆弧代替的优顶点，要 处理的轮廓元素包括直线段、圆弧段、优项点等，所以可以通过建立边界元素 直线和圆弧的平面方程，并由此方便地求解出直线与直线、直线与圆弧或圆弧 与圆弧的平分线【2 9 】 3 9 】【删。 所求得的平分线为直线或二次曲线，在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 边到轮廓边界的欧几里德距离 t 作为参数。t 具有明显的几何含义：即偏置距离，因此在最终目的是求偏置线 的应用中，用t 来表达v o r o n o i 图具有更深的理论和实际应用价值。文献【4 l 】采用 八个系数项以及t 把平分线方程表达成一个有着统一模式表达式。文献1 4 0 将平分 线的参数方程表达为八个系数项和m 、t 两个参数项，来保证平分线的单调性。 文献【3 9 睬用标准的直线、圆弧公式求得平分线的参数方程，形式上更加直观。 1 4 第2 章v o r o n o i 图理论 本文采用文献【2 9 】【 1 描述的平分线表达方式。为了论文的完整性、和自我包含性， 这里简要分析轮廓段的表达公式和平分线( v o r o n o i 边) 参数公式。 2 2 1 边界轮廓段表达式 设一平面多边形的边界可以分解成最简单的子集一一定义元素。最小单元 的定义元素包括单个线段、圆弧和优顶点。对于一个优顶点，它和它的左右相邻 定义元素共同定义了一个初始平分线，因此，初始平分线的计算是在两个线段、 两个圆弧、一个线段和一个圆弧以及优顶点和线段圆弧之间完成的。 边界轮廓段的形式主要有：优顶点、线段、圆弧段三种。由于优顶点又可 以被看做是半径为0 的圆因此仅需要写出直线段和圆弧段的标准表达式即可。 直线表达式：a 丰x + b 木y 十d + k 术t = o 这是直线a + x + b + y + d = 0 的距离为k * t 的曲线族。这个曲线族出现在特 定区域。这里的a 、b 、d 是标准直线公式的系数。t 代表了偏置量的大小：t 值 越大，偏置线到原始轮廓段的欧几里德距离越大( v o r o n o i 图的内点是局部t 值 最大点) 。k 是偏置方向参数，取值为士1 。k 与偏置方向相关：向左偏置时，k 取 + 1 ；向右偏置时，k 取1 。 圆弧表达式：( x x c ) 2 + ( y - y c ) 2 = ( r + k 桃) 2 这是圆弧( x x c ) 2 + ( y y c ) 2 = r 2 的距离为k * t 的曲线族( 即同心圆弧族) 。 x c 、y c 是圆弧的圆心；r 是圆弧半径；t 是偏置量参数，k 是偏置方向参数( 向 外偏置取正，向内偏置取负) 。 优顶点、直线、圆弧包含参数t 的曲线族表达式如图2 9 所示。图中( a ) 、 ( c ) 是原始定义元素及其表达公式；( b ) 、( d ) 是由原始定义元素得到的曲线族； 点画线是两个定义元素曲线族的交点集合( 即平分线) ：x c 、y c 时圆弧中心；r 是圆弧半径；a 、b 、d 、a 、b 、c 是线段公式中标准化系数；t 是偏置量；k 是 偏置方向。 1 5 第2 章v o r o n o i 图理论 一? 图2 6 优顶点、直线、圆弧族表达式示意图 在计算v o r o n o i 图的实际应用中，由于我们都假设直线、圆弧段都是有方向 性的( 外轮廓为逆时针方向，内轮廓为顺时针方向) ，而且限定v o r o n o i 区都在 定义元素走向左侧的影响域内，构造的曲线族都是原始定义曲线向左的偏黄线 族，因此，方程中的k 值可以统一取正号：优顶点的曲线族统一采用半径增大 的方向( 从0 开始) 。图2 7 中( a ) 、( b ) 、( c ) 、( d ) 为相交有向定义元素间四 种可能的曲线族生成区域；( e ) 、( f ) 为不相邻有向定义元素间的曲线族生成区 域。图中黑实线为定义元素：点画线为生成曲线族的交点集合；灰箭头代表了 逆时针方向上两个定义元素的先后顺序。 1 6 省一一 一 錾塑 第2 章v o r o n o i 图理论 ( n )( e )( d ) ( o )( f ) 图2 7 相交和非相交定义元素问曲线族的方向 由图知：定义了定义元素的逆时针方向和走向左侧为影响域后，曲线族的 生成区域将由两个定义元素的先后顺序来唯一确定。 2 2 2 平分线表达式 v o r o n o i 图是到至少两个以上元素等距点的轨迹。这两个元素称为定义边。 根据定义边的类型可以确定平分线( v o r o n o i 边) 的类型：直线与直线的平分线 是直线；直线与圆弧的平分线是抛物线或是直线：圆弧与圆弧的平分线可能是 双曲线、抛物线、椭圆、直线、圆的任何一种。 两直线元素的平分线 设两直线段的偏置线方程族分别为： a + x + b + y + d + k 宰t = - 0 a + x + b + y + d + k + t = 0 则平分线方程的参数表达式为： x ( t 户( b + d - b + d ) r 1 + t 4 ( b + k - b + k ) n “t ) = ( a + d a + d ) n + t + ( a + k a + k ) n n = a + b - b + a 直线和圆弧的平分线 设直线和圆弧的方程族为： ( x x c ) 2 + ( y - y c ) 2 = ( 什k + t ) 2 1 7 第2 章v o r o n o i 图理论 a x + b y + d + k + t - - 0 则平分线方程的参数表达式为： x ( t ) = x c - a * l 1 k * a * t b | 、( r t 2 l 2 2 ) y ( t ) = y c b l 1 一k + b + t 千a 、( r t 2 一l 2 2 、 r t = r + k * t l i = a + x c + b + y c + d l 2 = l 1 + k + t 图2 8 举例说明了直线和圆弧段的平分线符合抛物线定义：d 1 ：r t ，d 2 - - r t ，d l = - d 2 。图中粗实线为定义元素；点画线为两个定义元素的平分线：t 为到 两个定义元素的距离：r 为圆弧的半径。 图2 8 直线和圆弧的平分线是抛物线情况 圆弧和圆弧的平分线 设两圆弧方程族为： ( x x c ) 2 + ( y - y c ) 2 = ( 什k t ) 2 ( x x c ) 2 + ( y - y c ) 2 = ( r + k + t ) 2 则平分线方程的参数表达式为： x ( t ) = x c - - a l 1 - a * g * t + b 4 ( r t 2 - l t 2 ) y ( t ) = y c b l 1 b * g * t z ：a 、( r t 2 l t 2 ) r t = r + k * t 1 8 第2 章v o r o n o i 图理论 r t ：r + k t s 2 = ( x c - x c ) 2 + ( y c y e ) z a = ( x c x