（应用数学专业论文）基于点集voronoi图的分类器设计.pdf

学位论文原创性声明 本人所提交的学位论文基于点集v o r o n o i 图的分类器设计， 是在导师的指导下，独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均 已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：孚涛 抛7 年5 月弓。日。 学位论文原创性确认书 学生严涛所提交的学位论文基于点集v o r o n o i 图的分类器 设计，是在本人的指导下，由其独立进行研究工作所取得的原创性 成果。除文中已经注明引用的内容外，该论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。 指导教师( 签名) ： 脊 2 一o7 年，月3 d 日 。 河北帅范大学硕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 i s u a lc + + 语 言实现模式分类的主要源程序。 关键词：点集v o r o n o i 图计算几何分类器设计模式识别 第1 页 河北师范人学顾十研究生学位论文 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 fc o m p u t a t i o n a lg e o m e t r ya n di t s i m p o r t a n ti nc o m p u t a t i o n a lt h e o r ya n da p p l i c a t i o n w i t ht h ev o r o n o id i a g r a mc o n c e p t i n f i l t r a t e di n t ov a r i o u sa r e a so fa p p l i c a t i o n , p e o p l eg r a d u a l l ys t a r t e dt or e s e a r c ha l l a s p l 忸o f t h ev o r o n o id i a g r a me x p a n s i o n an o v e lv o r o n o id i a g r a m ，s e tv o r o n o id i a g r a mi sp r o p o s e d d i r e c tc o n s t r u c t i o n o f2 ds e tv o r o n o id i a g r a mb y g r o w i n gc i r c l e si sg i v e ms e tv o r o n o id i a g r a mi st h e e x p a n d e dr e s u l to ft r a d i t i o nv o r o n o id i a g r a m s e tv o r o n o id i a g r a mc a l lb eu s e dt o s o l v es o m eb a s i cp r o b l e mi np a t t e r nr e c o g n i t i o n ，s u c ha so p t i m a le l a s s i f e rd e s i g n w h i c hc 粗b eu s e dt os o l v ec l a s s i f i c a t i o np r o b l e m s c o m p a r e dw i t ho t h e rm e t h o d s i n c l u d i n gt r a d i t i o n a lc l a s s i f i e rd e s i g n , t h i sn l c t h o di se a s ya n df a s t e rt oi m p l e m e n ti n c o m p u t e ra n dh a sb e t t e rp e r f o r m a n c e i nt h i sp a p e r , w eg i v et h em a i n r e s o u r c e p r o g r a m so f c l a s s i f i e rd e s i g nw h i c h a r er e a l i z e dw i t hv i s u a lc * l a n g u a g e k e yw o r d s ：s e tv o r o n o id i a g r a m c l a s s i f i e rd e s i g n p a t t e r nr e c o g n i t i o n 第2 页 河北师抱大学颂i 研究生学位论史 第一章绪论 1 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 图的结构对太阳系进行分割【i 】。第一个有关v o r o n o i 图的概念是在p e t e rg u s t a v l e j e u n e ( 1 8 0 5 - 1 8 5 9 ) 与g 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 喇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 图的概念，d i r i c h l e t 论述了二维和三维的情况，而v o r o n o i 论述了m 维 的情况1 2 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 图【4 】；将2 维欧氏平面内的v o r o n o i 图扩展到k 维空间，定义了k 阶v o r o n o i 图；加权v o r o n o i 图是将欧氏度量扩展到其它度量，限定图形在任意指定区域，给生成元点赋予 不同的权值【5 1 ；障碍v o r o n o i 图是在生成元之间加上各种障碍 6 1 等。 1 2v o r o n o i 图的应用 计算几何在计算机图形学，c a d ，c a m ，机器人，地理信息处理等许多领 域都有重要应用。v o r o n o i 图是计算几何的一个主要分支，在求解点集或其它几 何对象与距离有关的问题时起着重要的作用，因此许多学者对其性质进行了深 入的研究，提出了不少构造v o r o n o i 图的理论方法，使v o r o n o i 图得到了较为广 泛的应用。如用于最近邻近查询，最大化最小角三角剖分，最大空圆，最小生 成树，货郎担问题求解，中轴计掣_ 7 】；用v o r o n o i 图设计模糊分类器用于图像分 析【8 1 ，非监督学习的后验条件类概率估计【9 1 等。 1 3 论文的研究内容 在模式识别中，最优模式分类器设计是一个基本问题。在分类器设计中， 基于贝叶斯决策理论的分类器，需要知道有关样本总体分布信息，一般只能用 在统计知识较为完备的场合。基于几何分类器的常用方法，如感知器算法，增 量校正算法，分段线性函数法和势函数法等，在具体操作过程中，大多需要反 第5 页 河北师范人学颀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 i s u a lc h 语言实现的主要源程序。 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 图应用于模式分类， 取得了较好的效果。 第五章是结束语，对本文的主要工作及贡献进行了总结，并对下一步工作 进行了展望。最后是参考文献、致谢和附录。 第6 页 l l 【北帅范大学 魂卜研究生学位论文 第二章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 图。而本文所述的点集 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 1 1v o r o n o i 图的定义 这里所述的v o r o n o i 图，是生成元为点的v o r o n o i 图，下面先介绍它的定义。 定义1 给定平面上万个点的集合s = a ，p ：，p 。) ，由 矿( 只) = p r 2j d ( p ，p j ) d ( p ，p ，) ，j = 1 ，2 ，f 一1 ，f + 1 ，一) 定义的区域r ( p ，) ，称为a 的v o r o n o i 区域，i = l ，2 ，n 。d ( p ，n ) 表示p 和b 问 的e u c l i d 距离。由v ( p 1 ) ，v ( p 2 ) ，v ( p 。) 及其边 界给出的平面的分割，称作以s 中的点为生成元 的v o r o n o i 图，简称v o r o n o i 图。s 中的点 曰o = 1 , 2 ，咒) 称为生成元( 如图1 ，图中的点为 生成元，各生成元所在的多边形区域为其v o r o n o i 区域) 。 2 1 2v o r o n o i 图的基本性质f l i i 性质1 r ( p ，a ) n r o ，p ，) = o o ，) 图l v o r o n o i 图 性质2 栉个生成元的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 边。 性质3 每个v o r o n o i 顶点恰好是三条v o r o n o i 边的交点。 以上性质具体证明详见文献【1 1 1 。 2 1 3v o r o n o i 图的主要生成法 到1 9 世纪6 0 年代，v o r o n o i 图的概念在自然科学和社会科学中已经相当普 第7 页 i l 北卿范人学 硖f 研究生学位论文 遍。但因为当时只能依赖用圆规和直尺进行构造，因此应用仍然十分有限。缺 少简单有效的构造方法促使研究者们寻求来自快速发展的计算机科学领域的解 决方案，到了1 9 世纪7 0 年代早期，发展了许多二维和三维v o r o n o i 图的算法。 构造平面点集s 的v o r o n o i 图的算法在最近几十年中得到了快速的发展，主 要有半平面的交、随机增量算法、分治法、平面扫描算法和离散构造算法 1 2 , 1 3 , 1 4 , 1 5 , 1 6 等。以下简要介绍几种常用算法的基本思路。 ( 1 ) 半平面的交算法 半平面的交是生成v o r o n o i 图的最直接的方法。它直接利用v o r o n o i 图的定 义，即对点集尸中的每一个生成元点n ，确定该点与其它所有生成元点之间的 等分线( 该等分线将平面分为两个半平面，包含点a 的半平面记作日( p ，p ，) ， 利用等式矿( p ，) = n h ( p 。，p ) 够造n 1 个半平面的交，然后统一所有这样建立 l ， 起来的半平面便得到点集p 的v o r o n o i 图。 该算法的时间复杂度为o ( n 2 ) 。 ( 2 ) 随机增量算法 与第一个算法相比，随机增量算法去掉了很多冗余的东西，因而显得快速 有效。算法的基本思想是增量生成的“追加引进”的概念。假设点集 p ： a ，p 2 ，以) ，并且现已构造出k ( k n ) 个点的v o r o n o i 图 f o r ( a ，觑，p k ) ，增加点n “之后，要求构造v o r o n o i 图 v o r ( p l ，p 2 ，p k ，p k + 1 ) 。具体做法是：先在_ f o r ( p l ，p 2 ，p t ) 中查找，使得点 p 州v 。( p 1 ) 的v o r o n o i 多边形v ( v j ) ，然后求p 与p i 间的垂直平分线f ，设 ，与v ( v ，) 的边界相交于鼋1 ，g ：两点，设g ：为其中一有限点，再找以9 2 所在边为 邻边的与联a ) 相邻的区域，如此进行下去，直到找到的点与吼重合为 止，最后将新增线所围区域中的场r ( p ，p ：，p ) 的边裁剪掉即可。 该算法时间复杂度为：最好情况是o ( ，1 ) ，最坏情况是o ( n 2 ) ，平均情况是 o ( n l o g n ) 。 第8 页 河北帅范人学r 袅i 研究生学位论文 ( 3 ) 分治法 另一个比较有效的著名方法是分治法。分治法构造v o r o n o i 图的基本思想 是：将生成元集合p 中的点按x 坐标由小到大排序，然后从中分割点集p 为p 和 f p ：两部分，使得l p 。1 = 1 p ：i = = 1i p i 。如果集合p 、p 2 中含点数目大于4 ，则继 二 续分割点集，直至子点集规模小于或等于4 ；对每个子点集利用煎述的方法求 v o r o n o i 图，然后不断合并相邻子点集的v o m n o i 图，直至最终得到v o r ( p ) 。 分治法时间复杂度为o ( n l o g n ) 。 ( 4 ) 平面扫描算法 该算法是f o r t u n e 在1 9 8 7 年提出的，平面扫描算法通过平面上的一条扫描 线由左至右进行扫描。在平面上已扫过的部分能够构造出v o r o n o i 图，而未扫 描部分则没有形成。 该算法时问复杂度为o ( n l o g n ) 。 ( 5 ) 离散构造算法 给每个生成元分别指定不同的颜色并以其为圆心，匀速的向外扩张画圆至 整个平面，不同颜色的区域相遇产生的交线图即为v o r o n o i 图。 2 2 点集v o r o n o i 图 下面将上述的v o r o n o i 图的定义推广到点集v o r o n o i 图。为此，先定义点到 点集的e u c l i d 距离，然后在此基础上仿照定义1 给出点集v o r o n o i 图的定义。 2 2 1 点到点集的e u c l i d 距离 定义2 在平面中，点，到点集墨= ，t ：，) 的距离规定如下： d ( p , s ，) = n f i n d ( p ，而) ，而五) ，其中d ( p ，而) 为两点p 和嘞之日j 的e u c l i d 距离。 2 2 2 点集v o r o n o i 图的定义 定义3 墨是平面上由屯个点所组成点集， 即 墨= “。玉：，) ，i = l ，2 ，厅，且墨n t = a ，f j ；设s = 墨，是，量) 为h 个点集的 集合。由以墨) = 扫r 2 id ( 弘置) d ( p ，置) f 刀，i j ) 定义的区域y ( 墨) 称为 点集s 。的v o r o n o i 区域，由v ( s 1 ) ，r ( s 2 ) ，v ( s 。) 及其边界给出的平面的分割称 第9 页 i 北帅托大学硕p 研究生学位论文 作以s 中的点集为生成元的v o r o n o i 图，简称点集v o r o n o i 图。s 中点集 s , o = l ，2 ，帕称为生成元，墨中的x j j = 1 ，2 ，生，i = 1 ，2 ，刀) 为数据点。如 果矿( 置) n 矿( s ，) o ，则称矿( 墨) n 矿( s ，) 为s 、 s ，间的点集v o r o n o i 边。其中v ( s ) 是v ( p ) 的闭 包。( 图2 为5 个生成元的点集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 2 3 点集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 ( s ，x f = 1 , 2 ，疗) 是对平面的分割即v ( s 。) ( f = 1 , 2 ，h ) 将平面分割成互 不相交的以部分。 证明：首先证明当f j 时， v ( s ) n v ( s j ) = 中 若存在p v ( s ；) n v ( s ，) ，由p v ( s 。) 和定义3 ，对任意 k i , l 七s n ，d ( p ，s ) ，所以，烈只墨) d ( p , s j ) ； 同理，由p e v ( s j ) n - l , 得d ( p ，墨) d ( p ，墨) 矛盾v c s ，) r i g ( s ) = m 设p 为平面上任一点，不失一般性，假定d ( p ，s ，) d ( p ，s 2 ) s d ( p ，s 。) 如 果d ( p ，蜀) = d ( p ，s 2 ) ，由上面的假定 ， d ( p ，墨) 2 ) 维空间的特征向量投影到二维空b j ，已超出了本文所讨论的范围，尚待研究。 3 从本质上看，基于点集v o r o n o i 图的分类设计方法，仍然属于近邻法。 在近邻法中，对未知样本x 分类，需要比较x 与n 个已知类别的样本( 训练样 本) 之间的欧式距离，并决策x 与离它最近的样本同类。使用本文的方法，一 旦利用已知类别的样本构造出点集v o r o n o i 图，只需计算未知样本x 在由点集 v o r o n o i 图染色的特征空间中的颜色值，便可直接得到x 所属的类别，而无须复 杂的计算。尤其适合训练样本给定后，需要对大量未知样本进行判别的情况。 4 还可以构造出其它距离( 如棋盘距离、城区距离等) 的点集v o r o n o i 图。 以适用于不同度量的特征空间中的分类问题。 第2 l 页 河北帅范大学颂1 研究生学位论文 第五章总结与展望 5 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 图。它不仅生成方法简单，生成过程直观，而且可直接应用于 模式分类设计。最后，我们对本文所涉及到的算法，给出了用、，i 姐a lc h 语言 实现的主要源程序。 5 2 进一步研究工作 点集v o r o n o i 图的理论是在二维空间的计算几何的基础上发展起来的，当 样品的特征空间扩展到高维时，点集v o r o n o i 图的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 图的构造方法。但是目前对高维v o r o n o i 构造方法的研究还 处于初步阶段3 蚴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 图进一步推广应用的基础。 第2 2 页 河北帅范大学硕l ：研究生学位论文 参考文献 【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 fv o r o n o id i a g r a m s a t s u y u k i o k a b e ，b a r r yb o o t s ，k o k i c h is u g i h a r a , s u n gn o kc h i u 【2 】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 n 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 p r e m i e rm 6 m o i r e ：s o rq u e i 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 i t s ，j r e i n e a n g c w ，m a t h ，1 3 3 ，9 7 1 7 8 ，1 9 0 7 【3 】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 n 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 6 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 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 , 6 7 - 1 8 1 ，1 9 0 9 【4 】赵晔，张有会等关于一般图形v o r o n o i 图的离散构造法的研究计算机应用与 软件，v o l 2 1 n o 6 2 0 0 4 年6 月 5 a u r e n h a m m e r , e ，a n de d e l s b m n n e r , h ，a i lo p t i o n a la l g o r i t h mf o rc o n s t r u c t i n g t h ew e i g h t e dv o r o n o id i a g r a mi nt h ep l a n e p a t t e r nr e c o g n i t i o n , 1 7 ，1 9 8 4 ，2 5 1 2 5 7 【6 】a l i n g a s v o r o n o id i a g r a m 、) v i t hb a r r i e r sa n dt h e i ra p p l i c a t i o n s ，m a n u s c r i p t ，1 9 8 6 【7 1 卢开澄计算几何算法一分析与设计【m 】北京：广西科学技术出版社，2 0 0 0 8 】p a v l o p o u l o ss ，k y r i a c o ue ，k o u t s o u r i sd e a 1 f u z z yn e u r a ln e t w o r kb a s e d t e x t u r ea n a l y s i so fu l t r a s o n i c i m a g e s j i e e ee n g i n e e r i n gi n m e d i c i n ea n d b i o l o g ym a g a z i n e ，2 0 0 0 ( 1 ) ：3 9 - 4 7 【9 】r o g e r sgw , s o l k aj , m a l y c v a cds ，e ta 1 as e l f - o r g a n i z i n gn e t w o r kf o r c o m p u t i n g ap o s t e r i o r i c o n d i t i o n a l c l a s s p r o b a b i l i t y j i e e e t r a n s o n s y s t e m s , m a na n dc y b e r n e t i c s ，1 9 9 3 ( 6 ) ：1 6 7 2 1 6 8 2 【1 0 】e d e l s b r u m e rh s m o o t hm l l f a c c s f o rm u l t i - s c a l e s h a p er e p r e s e n t a t i o n a i n ：p r o c e e d i n g so ft h e1 5t hc o n f e r e n c eo nf o u n d a t i o no fs o f t w a r et e c h n o l o g ya n d t h e o r e t i c a lc o m p u t e rs c i e n c e ，b a n g a l i n e , 1 9 9 5 3 9 1 - 4 1 2 【11 】f r a n c op p r e p a t a t a , m i c h a e li a ns h a m o s 著，庄心谷译计算几何导论北京： 科学出版社，1 9 9 0 【1 2 】a b e l l a n a s ，e h u r t a d o ，c j c k i n g r k l e i n ，e ，l a n g e t e p e , l m a , b p a l o p ，v s a c t i s t a i i ， p r o x i m i t yp r o b l e m sf o rt i m em e t r i c si n d u c e db yt h el im e t r i ca n di s o t h e t i cn e t w o r k , i n ：i xe n c u c n t r o s 龃g c o m c t r iac o m p u t a e i o n a l ，n c o i le ta 1 ( e d s ) ，u n i v e r s i t a td e 第2 3 页 河北帅范人学碗1 研究生学位论文 g i r o n a , 2 0 0 1 ，p p , 1 7 5 1 8 1 【1 3 】周培德，卢开澄计算几何一一算法分析与设计【m 】清华大学出版 社2 0 0 3 8 8 1 3 0 f 1 4 】陈军v 娜o n m 动态空间数据模型，北京：测绘出版社，p p3 0 - 3 2 ，2 0 0 2 年 【1 5 赵志辉，张有会等线段障碍v o r o n o i 图的离散生成计算机应用与软 件, p p 6 1 - 6 3 ，v 0 1 2 1 ，2 0 0 1 年 【1 6 】赵晔，张有会等p o w e r 图的离散生成计算机辅助设计与图形学学 报，p p l l 8 1 1 1 8 4 , v 0 1 9 ，2 0 0 3 年 【1 7 】e p r c p a r a t a , m i s h a m o s ，c o m p u t a t i o n a lg e o m e t r y ：a ni n t r o d u c t i o n n e wy o r k ： s p r i n g c r - v e r l a g , 1 9 8 5 f 1 8 】d o n a l dh e a m , m p a u l i n eb a k e r , c o n , o u t e rg r a p h i c sc v e r s i o ns e c o n de d i t i o n , p r e n t i c h a l ll n c 1 9 9 7 【1 9 】渡边贵史，村岛定行2 次元雒散水口f 因窑0 ( 1 ) o 射算踌两描 s e t p i x e l ( p - x ，p 7 p - i 。1 0 0 ) ； p f f i p - n e x t ； ) v o i dl i s t ：d e l l i s t ( ) 释放链表 ( i t e m * p = l i s t ，飞 w h i l e ( p ! = n u l l ) q 。- - p - n e x t ； d e l e t ep ； p = q ； ) v o i dl i s t ：l i s t c o p y ( l i s t + l i s t 2 1 i t e m * p l ，懈； p l = l i s t ； w h i t e t ! = n u l l ) p 2 f n e wi t m o ； p 2 - a 2 = p l - a 2 ； 1 , 2 - c o l o r = p 1 - c o l o r ；, p 2 - d 2 = p l - d 2 ； p 2 - i - - p 1 - i ； p 2 - x = p l - x ； p 2 啪l 。、y ； i f ( 1 i s t 2 - l i s t - - 一o ) l i s t 2 - i i s t = p 2 ； e l s e ( 1 i s t 2 - e n d o ) - n e x t = p 2 ； p l = p l o n e x t ； 第2 9 页 河北师范大学颂1 ：研究生学位论文 p 2 - n e x t = n u l l ； v o i dl i s t ：v o r o n o i ( c d c * p d c ，i n td 口【3 1 ) t a td x - 4 ，d y = 0 ，i = l j - l ； i t e m * p = l i s t ； w h i l e ( j y d y ； i f ( p d c - g e t p i x e l ( x ，) 7 产旬o ) p d c - s e t p i x e l ( x ，y ，p - c o l o r ) ； p - d 2 = d i 2 1 ； ) e l s ep a 2 = d 【q 【2 】； | 仡 x 2 p - x + d x ； y ；p _ y 电 i f (