（计算机应用技术专业论文）pebi网格的生成与应用研究.pdf

作者签名：啦日期： 研年月。日 学位论文授权使用声明 本人完全了解北京工商大学有关保留和使用学位论文的规定，即：研究生在校 攻读学位期间论文工作的知识产权单位属北京工商大学。学校有权保留并向国家有 关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅；学校可以 公布学位论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。( 保密的学位论文在解密后遵守此规定) j 学位论文电子版同意提交后，可于囱当年 口一年口二年后在学校图书馆 网站上发布，供校内师生浏览。 作者签名：墨限导师签名： 日期：c 2 辟朋胡 l 摘要 本文针对油藏模拟领域p e b i 网格( 一种限定v o r o n o i 图) 现有生成算法中存在 的缺点，对p e b i 网格的生成技术进行系统的研究，分析限定条件在p e b i 网格中存 在的充要条件，提出生成p e b i 网格的优化检测带细分算法，并实现p e b i 网格的尺 寸控制和质量控制。本文还研究限定v o r o n o i 图在机器人路径规划中的应用，提出解 决路径规划问题的方案。 本文主要完成的工作如下： ( 1 ) 对p e b i 网格所涉及的v o r o n o i 图、d e l a u n a y 三角剖分、p o w e r 图、r e g u l a r 三角化、经典d e l a u n a y 细化算法、计算几何等基础理论和方法进行总结、分析、对 比，研究限定点、限定线等限定条件在最终生成的p e b i 网格中存在的充要条件。 ( 2 ) 针对已有的p e b i 网格生成算法的缺点，提出生成二维p e b i 网格的算法，设 计相应的数据结构，并给出算法实例证明其正确性和有效性。 ( 3 ) 对p e b i 网格单元的质量控制和尺寸控制方法进行深入研究，提出二维p e b i 网格质量控制与尺寸控制的控制准则和相应的控制算法，并用实例进行算法验证。 ( 4 ) 通过本文算法生成限定v o r o n o i 图，构造机器人的候选路径集合，解决机器 人最短路径问题。算法的实例验证了其正确性和有效性。 本文成果可以应用于可视化、空间数据处理、地质模型构造等各个领域。 关键词：v o r o n o i 图；p e b i 网格；d e l a u n a y 三角化；质量控制；尺寸控制；路径 规划 a b s t r a c t p e b i 鲥d i st h ea p p l i c a t i o no fc o n s t r a i n e dv o r o n o id i a g r a mi nr e s e r v o i rs i m u l a t i o n c o n c e r n i n gt h ed r a w b a c k sa n dl i m i t a t i o n so fc u r r e n tp e b ig r i dg e n e r a t i o na l g o r i t h m ，t h i s t h e s i ss y s t e m a t i c a l l ys t u d i e dt h et h e o r ya n da l g o r i t h mo fp e b i g r i d f i r s t l y , t h ec o n d i t i o n s t h a tg u a r a n t e et h ee x i s t e n c eo fc o n s t r a i n e dp o i n t sa n ds e g m e n t si np e b i 鲥da r ep r e s e n t e d a f t e r w a r d s ，ar e f i n e m e n ta l g o r i t h mi sp r e s e n t e dt og e n e r a t ep e b i 酊d t h es i z ea n d q u a l i t yc o n t r o la l g o r i t h mo ft h em e s ha r ea n a l y z e dl a t e r f i n a l l y , a ni m p l e m e n t a t i o no f p e b ig r i di ss t u d i e dt or e s o l v ep a t hp l a n n i n gp r o b l e mf o rm o b i l er o b o t t h em a i nc o n t r i b u t i o n so ft h i sw o r ka r es u m m a r i z e di nd e t a i la sf o l l o w s ： ( 1 ) t op r o p o s et h ec o n d i t i o nt h a tg u a r a n t e e st h ee x i s t e n c eo fg e n e r a lc o n s t r a i n e d p o i n t sa n ds e g m e n t si np e b ig r i d ，t h er e l a t e dt h e o r ya n da l g o r i t h mo fv o r o n o id i a g r a m ， d e l a u n a yt r i a n g u l a t i o n ，p o w e rd i a g r a m ，r e g u l a rt r i a n g u l a t i o n a n d c o m p u t a t i o n a l g e o m e t r ya r es y s t e m a t i c a l l ya n a l y z e da n dc o n c l u d e d ( 2 ) t oo v e r c o m et h ed r a w b a c k so fe x i s t i n gg e n e r a t i o na l g o r i t h m ，ag e n e r a la p p r o a c h a n dc o r r e s p o n d i n gd a t as t r u c t u r et og e n e r a t ep e b ig i r da r ep u tf o r w a r db ys e t t i n gu pi n i t i a l i s o s c e l e st r a p e z o i ds t r i ps e t sa n dt h e ns u b d i v i d i n gt h es t r i ps e t s a ni m p l e m e n t a t i o ni sa l s o g i v e nt oi n d i c a t et h ev a l i d i t ya n de f f i c i e n c yo ft h ea l g o r i t h m ( 3 ) t h es i z ea n dq u a l i t yc o n t r o la l g o r i t h mo fp e b i 鲥da r ep u tf o w a r d a f t e rt h e a n a l y s i sa n di n t r o d u c t i o no fc o n t r o lr u l e s ，t h et w oc o n t r o la l g o r i t h m sa r ei n t r o d u c e d a n e x a m p l es h o w i n gs i z ea n dq u a l i t yc o n t r o lo fp e b ig i r di ss h o w nt op r o v e t h ev a l i d i t yo f t h et w oa l g o r i t h m s ( 4 ) t or e s o l v ep a t hp l a n n i n gp r o b l e mf o rm o b i l er o b o t ，a na p p r o a c hi si n t r o d u c e db y u s i n gp e b ig i r dg e n e r a t i o nm e t h o di nt h i sw o r k c o m p a r e dt oo t h e rm e t h o d s ，t h i so n ei s m o r ee f f i c i e n ta n df a s t ，w h i c hi si n d i c a t e db ya ni m p l e m e n t a t i o np r e s e n t e df i n a l l y t h er e s e a r c hr e s u l t so ft h i st h e s i sc a nb ea p p l i e dt ov i s u a l i z a t i o n ，s p a t i a ld a t a p r o c e s s i n g ，g e o l o g ym o d e l i n ga n dm a n yo t h e rf i e l d s k e yw o r d s ：v o r o n o id i a g r a m ，p e b i 鲥d ，d e l a u n a yt r i a n g u l a t i o n ，s i z ec o n t r o l ， q u a l i t yc o n t r o l ，p a t hp l a n n i n g i i 目录 第一章绪论1 1 1 引言l 1 2v o r o n o i 图及其应用研究现状1 1 3p e b i 网格4 1 4 本文的目的、意义及价值6 1 5 本文的组织7 1 6 本章小结7 第二章v o r o n o i 图及d d a u n a y 三角形8 2 1 引言8 2 2v o r o n o i 图及d e l a u n a y 三角形8 2 3d e l a u n a y 三角形的特性10 2 4v o r o n o i 图生成算法一1 3 2 5 经典的d e l a u n a y 三角化算法一1 5 2 6 限定d d a u n a y 三角剖分一1 6 2 7p o w e r 图及r e g u l a r 三角化一1 9 2 8 本章小结1 9 第三章p e b i 网格的生成算法一2 0 3 1 引言一2 0 3 2p e b i 网格生成研究现状。2 0 3 3 限定条件在p e b i 网格中存在的充要条件2 2 3 4v o r o n o i 梯形检测带细化算法2 3 3 4 1 算法思路一2 4 3 4 2 算法描述2 5 3 4 3 算法收敛性分析2 7 3 4 4 算法效率分析2 8 3 5 算法的数据结构2 8 3 5 1 规范化后的限定线端点( e p s ) 2 8 3 5 2 限定线端点与限定线端点的连线2 9 3 5 3 检测带边界及检测带2 9 3 6 算法实例3 0 3 7 本章小结3 2 第四章p e b i 网格的质量与尺寸控制3 3 4 1 引言3 3 4 2 控制算法的预处理3 4 4 3p e b i 网格的尺寸控制。3 7 4 4p e b i 网格的质量控制3 8 4 5 算法实例4 0 4 6 本章小结4 2 第五章机器人路径规划中p e b i 网格的应用4 3 5 1 引言4 3 5 2g v g 生成研究现状4 3 5 3 本文方法4 6 5 4 算法实例4 8 5 5 本章小结4 9 第六章结论与展望5 0 6 1 论文完成的工作5 0 6 2 今后工作展望5 0 参考文献。5 2 在学期间发表的学术论文及研究成果5 5 致谢。5 6 i v 王长飞：p e b i 网格的生成与应用研究 第一章绪论 【内容摘要】本章概述v o r o n o i 图的历史及研究应用现状，引出限定v o r o n o i 图 及p e b i 网格的概念，指出本文的研究目的、内容及意义。 1 1 引言 v o r o n o i 图是一个关于空间划分的基础数据结构。1 0 0 年来，它被应用在与几何 信息相关的各个领域。随着计算机技术的普及和发展，v o r o n o i 图的应用范围也在不 断扩大，本文研究的p e b i 网格就是v o r o n o i 图在油藏数值模拟领域的应用。本文来 源于北京市教委科技发展项目面上课题( 项目号：k m 2 0 0 5 1 0 0 1 1 0 0 4 ) 以及北京市自 然基金课题( 项目号：4 0 6 2 0 1 0 ) 。 本章其余内容组织如下：1 2 介绍v o r o n o i 图及其应用现状，给出v o r o n o i 图的 研究热点。1 3 简述p e b i 网格的相关概念。1 4 阐述本文的研究目的、意义及价值。 1 5 介绍论文的内容组织结构。 1 2v o r o n o i 图及其应用研究现状 1 8 5 0 年德国数学家d i r i c h l e t 研究了平面点的邻域问题i 】，1 9 0 8 年俄国数学家 v o r o n o i 将其研究结果扩展到高维空间【2 1 。d e l a u n a y 于1 9 2 9 年给出“d i r i c h l e t 区域”的 概念。1 9 3 2 年“v o r o n o i 区域”概念的提出，标志着v o r o n o i 图作为计算几何的一个分 支正式诞生。1 9 3 4 年，d e l a u n a y 将v o r o n o i 区域相邻的点连接起来得到v o r o n o i 图的 对偶图- - d e l a u n a y 三角网格。如图1 1 ，每个v o r o n o i 图顶点是d e l a u n a y 三角形的外 一) 。 图】1v o r o n o i 图和d e l a u n a y 三角网格 v o r o n o i 图的应用非常广泛。刘金义对v o r o n o i 图9 0 年代以来的应用进行了综述 王长l s ：p e b i 网格的生成与应用研究 【3 1 。此处简要列举v o r o n o i 图的一些应用实例：流行病学一1 8 5 5 年英国霍乱调查委员 会( c h o l e r ai n q u i r yc o m m i t t e e ) 发布的“1 8 5 4 年秋季w e s t m i n s t e r 的s t j a m e s 教区霍 乱爆发的报告”及j o h ns n o w 绘制的地图表示b r o a ds t r e 斌p u m p 周围霍乱死亡者的空 间分布时用到了v o r o n o i 图，被称为“最著名的1 9 世纪的疾病地图”。地质学一1 9 0 9 年俄罗斯的b o l d y r e v 、1 9 2 0 年美国的d a v i s 和h a r d i n g 应用v o r o n o i 区域研究某个区 域沉积物的储量估计方法。气象学荷兰气象学家t h i e s s 饥在1 9 1 1 年使用v o r o n o i 区域作为辅助工具计算某区域降水平均值【4 】。经济学b o g l l e ( 1 9 4 9 ) 和s n y d e r ( 1 9 6 2 ) 研究了美国大城市中心的v o r o n o i 多边形，它被看作这些中心的实际市场区域。城市 规划一g o o d c h i l d 和m a s s a m ( 1 9 6 9 ) 用v o r o n o i 多边形来进行城市里的公共服务设施 的定位设计。无线通信一1 9 6 5 年s l e p i a n 应用v o r o n o i 图研究信号的发射和接受区域， c o n w a y 和s l o a n e 在1 9 9 2 年称这种区域为“v o r o n o i 蜂窝”( v o r o n o ih o n e y c o m b ) 。物 理学w i 辨e r 和s e i t z 在1 9 3 3 年研究了金属钠的化学性质，用v o r o n o i 区域来描述分 布在三维空间中一个栅格内的点，物理学家现在称其为 w i g h t - - s e i t z 区域”( w i g n c r - - s e i t zr e g i o n s ) ；考古学- r u g 西e s 和c h u r c h ( 1 9 9 6 ) 等分别应用v o r o n o i 图研究了 南英格兰的铁器时代、古希腊克里特文明、墨西哥盆地的a z t e c 遗址等早期文明的可 能的领地结构。天文学v o r o n o i 图常被用来确定恒星和星系的分布【5 】，法国数学家 d e s c a r t e s ( 笛卡尔) 于1 6 4 4 年发表的太阳系及其周边天体的分布图就是v o r o n o i 图【6 j 。 建筑学一用来城市建模【| 7 1 ，如图1 2 所示。生物学一用来蛋白质建榭8 ，9 】。艺术学一用 来制 图1 2v o r o n o i 图在城市建模中的应用7 l 在g i s 领域，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 n f l u e n c er e g i o n ) 、测向邻 2 王长匕：p e b l 网格的生成与应用研究 近( l a t e r a la d j a c e n c y ) 、局域动态( l o c a la n dd y n a m i c ) 等重要特性，因此成为g i s 空间数据建模和分析的一种重要工则坦】。 除了上述学科领域以外，计算机科学方面的相关文件搜索( a s s o c i a t i v ef i l e s e a r c h i n g ) 、集群分析( c l u s t e r a n a l y s i s ) 、存取访问( s c h e d u l i n gr e c o r da c c e s s e s ) 、 碰撞检测( c o l l i s i o nd e t e c t 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 动态g i s 的基本结构和空间数据动态存取方 法等。 对于点状目标的普通v o r o n o i 图，早期人们主要研究其性质、生成算法。生成算 法主要分为矢量和栅格两类生成算法。其中矢量生成算法常见的有增量法、分治法、 并行算法和基于d e l a u n a y 剖分的间接算法【l 1 2 1 。随着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 图在欧几里德空间定义，点之 间的距离是欧氏距离。在实际应用中，该距离可以推广到加权距离、最短路径距离、 m i n k o w s k i 距离、凸包距离、球面距离等等。 ( 2 ) 生长元推广的v o r o n o i 图。通常地，v o r o n o i 多边形的生长元是点集。在某些 应用领域，生长元可以是线段集合和点集的混合，线段集合也可以是直线段和曲线段 的集合；更进一步，生长元可以是一个区域，比如圆，椭圆，n u r b s 曲线围成的区 域等。图1 3 是一个生长元为点和线段v o r o n o i 图的例子。 图1 3 生长元为点和线段的v o r o n o i 副1 3 l ( 3 ) 移动点的v o r o n o i 图。上述v o r o n o i 图中的生长元( 点集) 是静止的。如果生 3 王长飞：p e b i 网格的生成与应用研究 长点是运动的，生成的是动态v o r o n o i 图。这种v o r o n o i 图在移动通信领域有很好的 应用前景。 ( 4 ) p o i s s o nv o r o n o i 图。如果生长元( 点集) 的分布是有一定的统计规律符合 p o i s s o n 分布，得到的就是p o i s s o nv o r o n o i 图，它在量子学、天文学等领域被广泛应 用。 ( 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 图( c o n s t r a i n e dv o r o n o id i a g r a m ) ，障碍物 被称为限定条件或约束条件，如图1 4 所示。 1 3p e b i 网格 图1 4 限定v o r o n o i 图1 4 1 h e i n e m a n n 于19 8 9 年提出的p e b i ( p e r p e n d i c u l a rb i s e c t i o n ，即垂直平分) 网格就是 一种限定v o r o n o i 副”l ，它实质上是限定v o r o n o i 图在油藏数值模拟领域的应用。 油藏数值模拟是应用数值计算方法研究油气藏中多相流体渗流规律的技术，广泛 应用于油气藏开发领域，具有重要意义。油藏数值模拟计算大量采用的是有限差分的 计算，而现在广泛采用的笛卡尔网格在描述地质条件复杂的油藏时存在较大的局限 1 5 , 1 6 ，比如在边界处( 例如断层、油水分界面) 不能精确描述其形状；有时存在严重 的网格取向效应【l 。n ，使得计算精度很难保证。而目前在其它领域广泛使用的三角形( 四 面体) 网格单元直接应用于油藏数值模拟也存在困难。 p e b i 网格是种非结构化局部正交网格，它比结构网格更灵活，可以很好地模 拟非规则地质体的边界，便于局部加密：同时又满足了有限差分方法对网格正交性的 4 王长匕：p e b i 网格的生成与应用研究 要求，最终得到的差分方程与笛卡尔网格有限差分法相似。因此，在油藏数值模拟领 域，p e b i 网格与径向网格组成混合网格，可以避免出现网格划分过密的情况，提高 数值计算的稳定性和速度【1 8 】，也能很好地计算圆形地层中非达西渗流【1 9 1 。 p e b i 网格中的限定条件可能包括： ( 1 ) 限定点：给定点必须成为p e b i 网格节点。 ( 2 ) 限定线：网格必须沿着给定折线分布，不允许出现跨过限定线的网格。 ( 3 ) 限定域：内部限定域内不能出现网格，外部限定域之外不能出现网格。 ( 4 ) 限定面：网格块的一个小面必须在给定的平面片上，不允许出现跨过限定面 的网格。 一般情况下，在油藏数值模拟领域，断层线就是限定线条件，井点就是限定点条 件，井点的影响范围用以井点为半径的圆表示，流体沿着p e b i 网格节点之间的连线 流动。另外，由于是应用于油藏数值模拟领域，p e b i 网格的限定条件要考虑到正断 层、逆断层等各种复杂地质情况。 在数值网格生成领域更一般地是将这些限定条件看成平面线段图( p l a n a rs t r a i g h t l i n eg r a p h ，简称p s l g ) 2 0 】或者是分段线性复厶形( p i e c e w i s el i n e a rc o m p l e x ，简称 p l c ) t 2 ，如图1 5 所示。 ( a ) p s l g ( b ) p l c 图1 5p s l g ( a ) ) 3 乏p l c 示意图( b ) 【2 2 l p s l g 较简单，它是平面上限定点和限定线段的集合。对于p l c ，它必须满足三 个特性： 5 王长飞：p e b i 网格的生成与应用研究 ( 1 ) p l c 中任意边的顶点也包含在p l c 中；p l c 中任意面所包含的顶点和边也包 含在p l c 中。 ( 2 ) 在相交处是闭合的。例如：如果p l c 中的两个面相交，则交线也一定包含在 p l c 中。 ( 3 ) 若p l c 中的一条边与p l c 中的一个面相交于该边内部一点，则整条边必须是 p l c 中一部分。 除以上限定条件外，网格单元的尺寸和形状也需要做一定控制。比如：在井点影 响范围内，希望网格单元由小到大成放射状分布；在空间不同位置，希望网格具有不 同的密度；在密度相同的情况下，希望网格单元的形状尽量饱满，即接近正六边形， 生长点尽量靠近正六边形中心，如图1 6 所示。在这些限定条件下生成p e b i 网格的 过程，称为p e b i 网格生成。 图1 6p e b i 网格1 2 3 】 由于p e b i 网格自身的复杂性，目前有关p e b i 网格生成的文章较少，还远不能满 足实际情况的要求【2 4 】。p e b i 网格研究的理论也不够系统、完善。因此，对其生成技 术进行进一步的思考和钻研显的极其迫切。 1 4 本文的目的、意义及价值 鉴于油藏数值模拟等领域对p e b i 网格的迫切需求，针对现有p e b i 网格生成算法 中存在的问题。本文研究目的是：在已有p e b i 网格生成算法的基础上，研究限定条 件在p e b i 网格中存在的充要条件，研究完成满足一定实际应用需求的边界一致的健 壮的快速的p e b i 网格生成算法；使用本文算法生成限定v o r o n o i 图( p e b i 网格) ， 6 王长飞：p e b i 网格的生成与应用研究 解决机器人路径规划问题。 应用价值方面，p e b i 网格是一种非结构化局部正交网格，它比结构网格更灵活， 可以很好地模拟非规则地质体的边界，便于局部加密；同时又满足了有限差分方法对 网格正交性的要求，最终得到的差分方程与笛卡尔网格有限差分法相似，在油藏数值 模拟领域有很好应用前景。本课题的研究对石油勘探开发事业、天然气资源探测及前 文所述各个应用领域都起到巨大推动作用。 1 5 本文的组织 本文共六章，内容安排如下： 第一章，即本章，概述v o r o n o i 的历史及应用现状，指出v o r o n o i 图是许多学科 的基础，引出p e b i 网格概念，阐述本文的研究目的、内容及意义。 第二章讲述了v o r o n o i 图的基础知识，介绍其生成方法；简要介绍v o r o n o i 图的 对偶图- - d e l a u n a y 三角的相关知识，给出本文的研究思路和解决方案。 第三章介绍二维p e b i 网格生成算法研究的相关内容。在分析已有生成算法不足 的基础上，提出二维p e b i 网格的优化检测带细分算法，实现p e b i 网格的生成，并 给出算法实例，验证该算法的正确性和有效性。 第四章对二维p e b i 网格进行尺寸控制和质量控制，给出各自的控制准则，研究 加点策略，提出相应的控制算法并给出算法实例。 第五章提出方法解决路径规划问题。使用本文算法生成限定v o r o n o i 图，解决移 动机器人的最短路径问题，并给出算法实例。 第六章总结全文，并展望下一步的工作。 1 6 本章小结 本章简要介绍了v o r o n o i 图的历史及研究应用现状，介绍限定v o r o n o i 图及 p e b i 网格的概念，引出本文的研究目的、内容及意义。 7 王长飞：p e b i 网格的生成与应用研究 第二章v o r o n o i 图及d e l a u n a y 三角形 【内容摘要】本章提出本文的研究思路和解决方案，讲述v o r o n o i 图的基础知识， 简介v o r o n o i 图的生成方法，介绍v o r o n o i 图的对偶d e l a u n a y 三角化的一些方法和成 果。 2 1 引言 v o r o n o i 图及其对偶图d e l a u n a y 三角具有很多完美的数学特性，各自均有多种生 成算法。相对而言，d e l a u n a y 三角剖分的算法更成熟瞄 2 5 2 6 ，2 7 ，2 8 1 。因此可以采取 d e l a u n a y 三角剖分方法间接生成v o r o n o i 图，这个思路始终贯穿本文。也正是如此， d e l a u n a y 三角的一些性质和方法显得极其重要，本章将详细讲述这方面的知识。 本章内容组织如下：2 2 介绍v o r o n o i 图及d e l a u n a y 三角形，2 3 给出d e l a u n a y 三角形的特性，2 4 小节简述v o r o n o i 图的生成算法，2 5 给出d e l a u n a y 三角化的方 法，2 6 介绍限定d e l a u n a y 三角剖分，2 7 简介p o w e r 图及r e g u l a r 三角化。 2 2v o r o n o i 图及d e l a u n a y 三角形 d i r i c h l e t 于1 8 5 0 年研究了平面点的邻域问趔，给定二维空间中的一个点集p = 僻ii = l 一，删，点集p 中无重复的点，b 点的邻域由邻近b 的所有空间中的点组成， 邻域中的点到只的距离小于到点集中其它点的距离。如图2 1 所示，图中域 乃圪巧吩虼内的任意点到尸2 点的距离小于到点集中其它点只僻2 ) 的距离，域 乃乃乃巧巧虼称为b 的邻域，其边界称为对应于乃点的d i r i c h l e t 多边形，它是由b 与点集中相邻点连线的垂直平分线围成的，乃称为其d i r i c h l e t 多边形的生长点。如 巧圪是p 2 p s 的垂直平分线的一部分。二维d i r i c h l e t 图是平面点集所有点的邻域多边 形的并集( u n i o n ) ，d i r i c h l e t 多边形边数的数学期望值为6 t 2 9 1 。 图2 1 二维情形的d i r i c h l e t v o r o n o i 图 v o r o n o i 于1 9 0 8 年将其结果扩展到高维空间【2 1 ，因此d i r i c h l e t 图也被称为 d i r i c h l e t v o r o n o i 图( 为方便起见，简称为v o r o n o i 图或维诺图) ，v o r o n o i 图的定义如 8 王长飞：p e b i 网格的生成与应用研究 下： 定义2 1 设dc x , 肼) 表示z 到只的欧氏距离，则定义点只的邻域瑶为： k = 扛id 似彬q 伍p p ，歹i v o r o n o i 图是点集中所有点的邻域的并集( u n i o n ) 。 在三维空间中，对应于b 的邻域是由只与相邻点连线的垂直平分面围成的凸多 面体，亦称为对应于只的v o r o n o i 多面体，v o r o n o i 多面体的每个边界面是垂直平分 面的一部分。1 9 7 0 年m i l e s 经过统计研究，表明三维v o r o n o i 多面体边界面个数的数 学期望值的上限为2 7 0 7 【2 9 1 。 在二维平面中，假设点集p 中若无四点共圆，点集尸的v o r o n o i 图有如下重要特 性【捌： ( 1 ) 点集p 的v o r o n o i 图中每个顶点恰好是三个边的公共顶点，并且是三个v o r o n o i 多边形的公共顶点。这三个v o r o n o i 多边形所对应的点集中的点连成的三角形称为和 这个维诺顶点对应的d e l a u n a y 三角形。如图2 1 ，维诺顶点乃对应的d e l a u n a y 三角 形为a p t p 2 p 3 。 ( 2 ) 点集p 中，任意3 个点确定的圆c 不包含点集中其他点。 ( 3 ) 点集p 中，只的每一个最近邻近点确定v o r o n o i 多边形所的一条边。 ( 4 ) 多边形k 是无界的，当且仅当只是点集p 凸包边界上一点。 ( 5 ) v o r o n o i 图直线对偶是点集p 的一个d e l a u n a y 三角剖分。 其中，性质( 4 ) 中凸包的定义如下： 定义2 2 点集q 的凸包( c o n v e xh u l l ) 是指一个最小凸多边形( 二维) 凸多面体( - - 维) ，满足q 中的点要么在该多边形边凸多面体上，要么在该多边形逝凸多面体内。 二维情况下，平面点集q = p o , p l 一, p l 刀的凸包如图2 2 所示。 p 3 p 0 图2 2 二维凸包 同理，在三维空间中，点集中若无五点共球，则该点集的v o r o n o i 图每个面是两 个v o r o n o i 多面体的公共面，每个边恰好是三个v o r o n o i 多面体的公共边。并且每个 9 王长i s ：p e b 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 顶点对应的d e l a u n a y 四面体。 因此，在二、三维情况下，可以给出d e l a u n a y 三角化的定义如下： 定义2 3 任意点集邢中所有维诺顶点所对应的d e l a u n a y _ 三角形四面体的并集是 对点集的一个三角四面体剖分，称其为d e l a u n a y 三角剖分d t s ( p s ) i 四面体剖分 d t e s ( p s ) 。 注意，如果一个二维点集中有四点或多于四点共圆的情况，那么这些点对应的 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 3 所示： 图2 3v o r o n o i 图退化情形 如果出现多点共圆情形，无论怎样连，只要形成的三角形将这些点形成的凸包充 满就行，各种连接方式生成的三角形均可称为和这个维诺顶点对应的d e l a u n a y 三角 形。 类似地，三维空间中，若点集中五点或多于五点共球，那么这些点对应的维诺多 面体共一个维诺顶点，该公共维诺顶点对应的维诺多面体多于四个，对应点集中的点 也多于四个。点集中共球的点连成四面体的方式也不唯一。只要形成的四面体将这些 点形成的凸包充满，各种连接方式生成的四面体均可称为和这个维诺顶点对应的 d e l a u n a y 四面体。 上述情况就称为退化情况。尽管如此，由于v o r o n o i 图拥有局部优化性质，同时， d e l a u n a y 三角具有下文所述的最小角最大特性，退化情况并不妨碍我们利用d e l a u n a y 三角剖分基本理论对点集进行剖分操作从而得到v o r o n o i 图。所以，本文将不再讨论 退化情况，从而减少大量无关紧要但却冗长的论证细节。 2 3d e l a u n a y 三角形的特性 与一般的三角网格相比，d e l a u n a y 三角网格具有较大的优势，主要表现在以下两 1 0 王长飞：p e b i 网格的生成与应用研究 个方面。 ( 1 ) d e l a u n a y 三角网格是一个空间优化结构 在生成点集的三角网格时，有很多种方法将点连成三角形或四面体。但在利用三 角网格进行分析计算时，为了提高计算精度，往往希望网格单元尽量饱满。而把点连 成d e l a u n a y 三角形或四面体，就最能满足这个需求。 ( 2 ) d e l a u n a y 三角网格的可操作性较好 d e l a u n a y 三角网格具有严格的数学定义和完备的理论基础，一般情况下具有唯一 性。在对已经生成的d e l a u n a y 三角网格进行加点、减点操作时，有可靠的理论依据 和简单的方法，来确保得到的新网格仍然是d e l a u n a y 三角网格，而一般的三角网格 则没有这些优点。 d e l a u n a y 三角网格具有以下三个重要特性：最小角最大、局部优化与整体优化、 d e l a u n a y 空洞与局部重连，含义如下： ( 1 ) 最小角最大( m a x m i n a n g l e ) ( 二维) 1 9 7 8 年s i b s o n 已经证明：二维的情况下，在平面点集的所有三角剖分中，d e l a u n a y 三角化生成的三角形的最小角达到最大【3 0 】。 如前文所述，给定点集，不加限制，存在很多种方法三角化。二维空间中，每种 三角化所生成的三角形都存在一个最小角，d e l a u n a y 三角化的最小角是最大的。因为 这一特性，对给定点集进行d e l a u n a y 三角化能够尽量地避免生成“瘦长”三角形，所 生成的三角形自动向等边三角形逼近。二维情况下，d e l a u n a y 三角化的最小角最大准 则与空外接圆准则是等价的1 3 l j 。空外接圆准则是指d e l a u n a y 三角化所生成的三角形 中，任意三角形的外接圆除经过该三角形的三个顶点外，不包含点集中的其它点。如 图2 4 所示，四边形a b c d ，连接a c ，则州c d 的外接圆包含b 点。连接b d ，则倒肋 的外接圆不包含c 点，a b c d 的外接圆也不包含彳点。显然地，后一种情况生成的 三角形的最小角要大于前一种情况的最小角。 a j = 、， 、， 、一、7 图2 4 空外接圆准则与最小角最大准则的一致性 但这种等价性在3 维空间中并不存在3 2 1 ，这是因为二维空问单纯形_ 三角形的 内角和为1 8 0 0 ，而3 维空间的单纯形( 如三维空间的四面体) 的内角和并不为常值。 所以用空外接球( 圆为二维球，大于三维为超球) 准则作为d e l a u n a y 三角化的优化 王长飞：p e b i 网格的生成与应用研究 准则更具普遍性。 ( 2 ) 局部优化( l o c a l l yo p t i m a l ) 与整体优化( g l o b a l l yo p t i m a l ) 如前文所述，在二维空间中，给定点集p ，