（信号与信息处理专业论文）基于delaunay网格生成有限元法的三维poisson方程解算器.pdf

摘要 摘要 有限元法是计算电磁学中求解给定边界条件下p o i s s o n 方程的一种有非常有 效的数值计算方法。影响有限元法应用质量的因素有很多，但其预处理步骤 求解域的网格生成是最为关键的因素，它直接影响到有限元法应用的质量。如何 生成剖分单元质量较高、能很好适应剖分域几何及物理特征的网格是有限元法预 处理步骤所要解决的核心问题。针对这一问题，本文设计了一种对多面体剖分域 进行有限元网格生成的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 空外接圆性质，减轻了 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 网格生成方法作为有限元法的预处 理，对半导体太赫兹天线电位分布进行了求解，并将电位分布进行了结果验证及 计算机可视化处理。所开发的三维p o i s s o n 方程求解软件包能很方便地应用到太 赫兹天线的计算机模拟中。 关键词：网格生成；d e l a u n a y 三角剖分；有限元法；d e l a u n a y 空外接圆准则 广东工业大学工学硕士学位论文 a b s tr a c t f i n i t ee l e m e n tm e t h o d ( f e m ) i sav e r ye f f e c t i v en u m e r i c a lc o m p u t a t i o nm e t h o d , w h i c hi su s e dt os o l v ee l e c t r o m a g n e t i cp o i s s o ne q u a t i o ni ng i v e nb o u n d a r yc o n d i t i o n t h e r ea t em a n yf a c t o r st h a tc a ni n f l u e n c et h ea p p l i c a t i o nq u a l i t yo ff e m ，a m o n gt h e m t h em o s ts i g n i f i c a n tf a c t o ri si t sp r e t r e a t m e n ts t e p t h em e s hg e n e r a t i o no fs o l u t i o n d o m a i n ，w h i c hc a nd i r e c t l yi n f l u e n c et h ea p p l i c a t i o nq u a l i t yo ff e m t h u s ，h o wt o g e n e r a t em e s ho fh i g h e r - q u a l i t yd i s s e c t i o nu n i ta sw e l la sb e i n ga b l et oa d a p tt h e g e o m e t r i c a la n dp h y s i c a lf e a t u r e so ft h et o - b e d i s s e c t e dd o m a i nh a sb e c o m et h ek e y p r o b l e mo ft h ep r e t r e a t r n e n ts t e po ft h ef e m i nt h el i g h to ft h i sp r o b l e m ，t h i sp a p e r i n v e n t sad e l a u n a ym e s hg e n e r a t i o nm e t h o dt og e n e r a t ef i n i t ee l e m e n tm e s hf o r p o l y h e d r o n sd i s s e c t i o nd o m a i n i nt h i sp a p e ran e ws u r f a c ed e l a u n a ym e s hg e n e r a t i o nm e t h o di sp r o p o s e da n d i m p l e m e n t e d w h e nt h ep o i n t ss e to nac o n s t r a i n e df a c ea r eo nt h es a m ep l a n e ，i tc a l l n o tb eu s e dt oc o n s t r u c t3 dt e t r a h e d r o nt r i a n g u l a t i o n t h i sm e t h o dp r e v e n t st h i s d e g e n e r a t i o ns i t u a t i o nb ya d d i n ga u x i l i a r yp o i n t si n t oe a c hc o n s t r a i n e df a c e t a n dt h e n , b a s i n go nt h ee m p t yc i r c u m s p h e r er u l eo fd e l a u n a yt r i a n g u l a t i o n , i tp r o j e c t s3 d d e l a u n a yt r i a n g u l a t i o nt ot h ec o n s t r a i n e df a c e tt oo b t a i nt h em e s hg e n e r a t i o no f c o n s t r a i n e df a c e ti n d i r e c t l y f i n a l l y , a l lc o n s t r a i n e df a c e t sa t ea s s e m b l e dt oo b t a i nt h e m e s hg e n e r a t i o no fp o l y h e d r o n so u t e rs u r f a c e m o s to ft h et r i a n g l ep a t c h e so ft h e p o l y h e d r o n so u t e rs u r f a c em e s hg e n e r a t e di nt h i sm e t h o ds a t i s f yt h ed e l a u n a ye m p t y c i r c u m - c i r c l er u l ea n dt h u si tr e d u c e st h ew o r k l o a do fc o n s t r a i n t sr e c o v e r yo p e r a t i o ni n d e l a u n a ym e s hg e n e r a t i o n 晰t ht h er e q u i r e m e n to fc o n s t r a i n t sr e c o v e r yo fd e l a u n a ym e s hg e n e r a t i o n , a n d b a s i n go nd e l a u n a ye m p t yc i r c u m c i r c l er u l e ，t h i sp a p e rf i r s t l yv e r i f yt h a tt h ee x i s t e n c e c o n d i t i o no fc o n s t r a i n t si n3 dc o n f o r m i n gd e l a u n a yt r i a n g u l a t i o ni st h a t , i t se m p t y c i r c u m - c i r c l em u s te x i s t a n do nt h i sb a s i s ，t h e nr e c o v e rt h ec o n s t r a i n t so fp o l y h e d r o n b yu s i n gt h ej u d g m e n tc r i t e r i o nt h a tt h em i n i m u nv o l u m ec i r c u m s t a n c eo ft h e c o n s t r a i n t sm u s tb ee m p t y a n dt h e n , i no r d e rt op r e v e n tt h ee x i s t e n c ec o n d i t i o no f i l a b s t r a c t c o n s t r a i n t sf r o mb e i n g d e s t r o y e dw h e na d d i n ga u x i l i a r yp o i n t si nt h eo p t i m i z a t i o ns t e p o ft e t r a h e d r o n , t h i sp a p e ri n v e n t san e wm e t h o dt oa d da u x i l i a r yp o i n t st ot e t r a h e d r o n a n di tr e s o l v e st h ec o n f l i c t sb e t w e e nt h ec o n s t r a i n t sr e c o v e r yi np o l y h e d r o nd e l a u n a y m e s hg e n e r a t i o na n dt h eo p t i m i z a t i o no ft e t r a h e d r o ni ni t i nt h ef i n a lp a r to ft h i sp a p e r , t h ep o l y h e d r o nd e l a u n a ym e s hg e n e r a t i o nm e t h o di s a p p l i e dt ot h em e s hg e n e r a t i o no ft h za n t e n n at os o l v et h ep o i s s o ne q u a t i o nd e s c r i b i n g t h ep o t e n t i a ld i s t r i b u t i o no ft h za n t e n n ab yu s i n gf e m ，a n do b t a i nt h ea p p r o x i m a t e p o t e n t i a ld i s t r i b u t i o n a f t e rt h a t ，t h ea p p r o x i m a t ep o t e n t i a ld i s t r i b u t i o ni sv e r i f i e da n d v i s u a l i z e d s of a r , t h ea n a l o gc a l c u l a t i o no f3 dt h za n t e n n ah a v eb e e ni n i t i a l l y c o m p l e t e d k e y w o r d s ：m e s hg e n e r a t i o n ；d e l a u n a yt r i a n g u l a t i o n ；f i n i t ee l e m e n tm e t h o d ； d e l a u n a ye m p t yc i r c u r n c i r c l er u l e i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 6 7 做作者签字：钟 指导教师签字 i ，1 年月专专专专专专 翅专专 、 厂、 、小、 ( b ) 输出 图1 1 四叉树网格生成 f i g 1 1q u a d t r e em e s hg e n e r a t i o n 四叉树1 ) t 叉树法发展至今也取得了一些进展。s c h r o e d e r 等通过四叉树1 ) t 叉 树法与d e l a u n a y 剖分法相结合，解决了内部网格与边界网格的相容性问题，提高 了剖分网格的质量；m c m o r r i s v 3 ) 等在解决计算流体动力学的网格生成问题时，将 四叉树八叉树法与前沿推进法结合，使其能较好地适应曲表面及内部网格生成的 要求。 四叉树八叉树法应用的瓶颈在于，如果相邻正方形正方体的细分层次不同， 那么将给相邻网格的融合带来不小的困难。另外，用正方形正方体来逼近剖分域 的边界时，会存在较大的误差，从而影响计算结果的准确性。由于四叉树八叉 树法本身较难克服的缺点，目前在网格生成方面已较少使用。 1 2 3d eia u n a y 法 经典d e l a u n a y 三角剖分法的处理对象为空间散乱点集，而用于网格生成的 d e l a u n a y 法，其处理对象一般为约束域，加入了边及面的约束条件，要求在最终 的网格中不丢失约束边和面。具体而言，在二维剖分域中为平面直线图( p l a n a r s t r a i g h tl i n eg r a p h , p s l g ) ；在三维剖分域中为多面体区域。d e l a u n a y 三角剖分法 与其他空间剖分技术相比较，一个突出的特点就是具有最大最小角特性，这使得 由d e l a u n a y 三角剖分所得的剖分单元形状可以尽量地饱满，较好地符合有限元网 格生成对剖分单元的质量要求。另外，运用d e l a u n a y 方法生成的网格也具有对剖 分域的自适应性，单元的剖分密度能大致反映出剖分域的几何特征。如在尖锐处 密度较大，平缓处密度较小，这一点也符合有限元网格对剖分单元密度的要求。 4 第一章绪论 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 4 , 1 5 , 1 6 , 1 ，1 8 】；三维剖分域的d e l a u n a y 网格生成还有待进一步的完善，需解决的 问题包括约束条件的恢复、剖分单元中薄元的消除以及约束条件间的小角度处理 世 c ro 1 3 本文的主要研究内容 本文对基于约束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 网格生成程序并将其应用于太赫兹天线模拟计算中的三维p o i s s o n 方程 求解。本文工作内容主要分布在以下几个方面： 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 三角剖分中的存在条件，并依据其存在 条件在最终网格中将其恢复。 3 设计并实现了网格生成中的加点算法，兼顾网格单元的质量优化和约束 条件的恢复。 本文各章节的安排如下： 第一章绪论部分简要介绍了本文的研究背景和有限元网格生成的发展现状； 对几种典型的网格生成方法进行了分析总结，并提出本文的主要研究内容。 第二章介绍了计算几何算法库c g a l 的组成及其精确计算的优点。 第三章阐述了与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 网 格生成方法和实现过程，包括约束条件恢复、添加辅助点等内容，并进行实验结 5 广东t 业大学工学硕士学位论文 果的分析。 第六章实现了有限元法在太赫兹天线模拟计算中的三维p o i s s o n 的求解。 1 4 本章小结 本章总结了有限元网格生成在计算电磁学中的应用背景及当前各种流行的网 格生成方法，并进一步提出了本文的研究内容。 6 第二章计算几何算法库( c g a l ) 第二章计算几何算法库( o g a l ) c g a l ( 英语发音类似s e a g u l1 ) n 明是一个开源的计算几何算法库，由欧洲及以 色列的研究机构、大学、公司等七个团体于1 9 9 6 年开始研发而成。参与c g a l 项 目的各个团体在计算几何方面都有着丰富的开发经验。如乌德勒支大学的p l a g e o 和s p a g e o 项目、m a x p l a n c k 研究院的l e d a 项目和i n r i as o p h i a a n t i p o l i s 开 发的c + + g a l 项目等等。通过协作融合，各团体为c g a l 的开发带来了宝贵的知识 积累。 c g a l 的目标定位是将计算几何中的各种高效算法以c + + 库的形式加以实现， 并将其应用于工业及研究领域方面。 2 1c g a l 的组成 c g a l 主要由三部分组成：内核( k e r n e l ) 、数据结构及算法和其他非几何因 素的支持工具。 2 1 1 内核 内核是c g a l 的重要组成部分，扮演着基石的角色。内核定义中规定了特定的 类型及产生对应类型对象的接口函数。类型以函数对象的形式提供给c g a l 基本库 中的数据结构及算法使用。内核主要提供了类型、构造对象及泛化判断。 c g a l 有多种内核，分别对应于2 d 及3 d 、任意维空间对象、2 d 弯曲对象。在 内核中包含了各种恒定大小的几何基元对象，如：点、线段、直线、射线、向量、 三角形、四面体等。并提供了一些基元的接口函数，如获取几何基元的坐标值、 平面的法向量、四面体体积等；另外还包含一些与基元相关的操作函数，如：求 各基元的交点、相对位置关系等。 广东工业大学工学硕士学位论文 ( a ) 点与有向线段 c o ) 点面相对位置 ( c ) 线段相交 图2 1 基元相对位置判断 f i g 2 1p o s i t i o nd e t e r m i n a t i o no f p r i m i t i v eo b j e c t s c g a l 提供了四类实体模型来对内核概念进行实例化，分别是： ( a ) c g a l ：c a r t e s i a n ( b ) c g a l ：h o m o g e n e o u s ( c ) c g a l ：s i m p l e _ c a r t e s i a n ( d ) c g a l ：s i m p l e _ h o m o g e n e o u s 其中( a ) 、( c ) 两类基于点的笛卡尔坐标系，( b ) 、( d ) 两类基于点的归一化坐标 系。在c g a l 中几何基元可采用笛卡尔坐标和归一化坐标两种方式表示。如：d 维空间中的点在笛卡尔坐标系中可表达为( c oq ，c ) ，在笛卡尔坐标系下坐标 的表达是唯一的。在归一化坐标系下，点的表达形式为( h o ，h d _ l ) ，它与笛 卡尔坐标的转换为c ，= 红忆。一个点在笛卡尔坐标系下，对应不同的h d 值，可 以有多种表示形式。c g a l 采用归一化坐标，而多出来的坐标分量h d 可以用于保 存分母，从而避免进行除法运算。c g a l 以模板的方式对内核概念进行不同类型 的实例化，这使得它具有了泛型的特点。 c g a l 中几乎所有的基元对象及其相应的操作函数都是以模板的形式定义的。 通过各种实例化参数，可以选择不同数据类型内核中的基元对象。而对各种参数 都要求必须符合一定的语法及语义要求。 几何基元在内核中既可以以独立类的形式存在，也可以以内核类的成员形式 存在。当以独立类的形式出现时，需要用适当的数字类型参数对其参数化，以使 其能完成计算操作，常用的参数如d o u b l e 、f l o a t 等；而以内核类的成员形式出 现时，默认使用实例化内核时所使用的参数。如： 8 第二章计算几何算法库( c g a l ) c g a l ：p o i n t 一2 p ； 上式二维空间的点以独立类的形式出现，使用参数c a r t e s i a n 对其 进行参数化。下例的点定义以内核成员函数的形式出现： t y p e d e fc a r t e s i a n k e m e l ； k e m e l ：p o i n t 一2 q ； 上面式子中，先以参数c a r t e s i a n 对内核进行参数化，p o i n t2 作为 内核的成员，使用的是与内核相同的参数，即c a r t e s i a n 。 对应不同的应用，c g a l 预定义了3 种不同类型中的内核，分别是： ( 1 ) e x a c t _ p r e d i c a t e s _ e x a c t c o n s t r u c t i o n s _ _ k e m e l 可以实现精确的几何基元构造及判断。 ( 2 ) e x a c tp r e d i c a t e s e x a c tc o n s t r u c t i o n sk e m e lw i t hs q r t 除了具有精确构造及判断外，还提供精确求取平方根的功能。 ( 3 ) e x a c t _ p r e d i c a t e s _ i n e x a c t _ c o n s t r u c t i o n s _ k e m e l 可实现精确的判断，但对基元不能实现精确构造。 以上3 种预定义内核均为笛卡尔内核，可输入d o u b l e 类型数据作为坐标分量 进行点的构造，且都可实现精确判断。数据的精确性是c g a l 的一个重要的优点， 将在第二节中介绍这一点。 2 1 2 数据结构及算法 c g a l 中的数据结构及算法包括多边形、半边结构( h a l f - e d g ed a t as t r u c t u r e ) 、 多面体、三角剖分、表面网格生成、表面的划分及参数化、v o r o n o i 图、多边形 及多面体的布尔操作、点集凸壳、a l p h a 形等等，内容丰富，几乎涵盖了计算几何 的所有内容。c g a l 中的数据结构及算法采用模板的方式定义，在使用时要求提 供具体的几何特征类( g e o m e t r i ct r a i tc l a s s ) 对其实例化。 数据结构及算法是作用于几何基元之上的操作，几何特征类则起到了桥梁的 作用，它定义了一系列数据结构及算法和几何基元之间的接口函数。内核通常也 可以作为几何特征类来对数据结构及算法作实例化，以d e l a u n a y 三角剖分为例： ( 1 ) t y p e d e fc g a l ：e x a c t _ _ p r e d i c a r e s _ i n e x a c t _ c o n s t r u c t i o n s _ k e m e l k ； ( 2 ) t y p e d e fc g a l ：d e l a u n a y _ t r i a n g u l a t i o n _ 3 d e l a u n a y ； ( 1 ) 行代码先定义了使用的内核k ；( 2 ) 行代码用k 对数据结构及算法一d e l a u n a y 9 广东工业大学工学硕士学位论文 三角剖分进行实例化。 c g a l 中的数据结构及算法种类繁多，内容相异，限于篇幅，本小节主要针 对t r i a n g u l a t i o n _ 3 类部分进行介绍。 c g a l 的三维三角剖分t r i a n g u l a t i o n3 类在编码上继承于 t r i a n g u l a t i o n _ u t i l s 3 类。t r i a n g u l a t i o n _ u t i l s 3 类主要定义了对四面体顶点索引及 邻接四面体索引等一系列操作。t r i a n g u l a t i o n 3 类下面派生了三维d e l a u n a y 三角 剖分- - d e l a u n a y _ t r i a n g u l a t i o n 3 类及规则三维三角剖分r e g u l a r _ t r i a n g u l a t i o n _ 3 类。 t r i a n g u l a t i o n u t i l s _ 3 t t r i a n g u l a t i o n3 d e l a u n a y _ t r i a n g u l a t i o n _r e g u l a r _ t r i a n g u l a t i o n _ i t r i a n g u a t i 。n e 帔 图2 1c g a l 的三角剖分类 f i g 2 1t r i a n g u l a t i o nc l a s s e si nc g a l t r i a n g u l a t i o n3 类中定义了三维三角剖分数据结构t r i a n g u l a t i o n d a t a s t r u c t3 类以及点、线段、三角形、四面体等，它实现的是种简单的点与点的连接关系， 最后构成点集凸壳的三角剖分。 c g a l 在t r i a n g u l a t i o n3 类中引入了一个无限点作为为辅助点，该无限点与 凸壳的每一个外三角形表面都相连，形成无限四面体。这样一来，三角剖分中的 每一个面均被两个四面体所共有，对凸壳外表三角形面也就无需特殊处理。无限 点没有具体的坐标值，因此不能对其进行具体的几何判断。 1 0 第= 章计算n 何算法库( c g a l 7 i n f i n i t ev e r t e = ? j 图2 - 2 无限点 f i g 2 2i n f i n i t e _ v e r t e x t f i a n g u l a t i o n _ 3 类中存储了顶点( v 嗽：o - 缸) 及胞( o e n ：3 - f a c e s ) ，但没有独 立地存储边( e d g c ：l - 和三角形面( 缸啦f a c e s ) ，因此对边及面的访问需要通过 顶点或胞与顶点索引号的结合来实现。 2 圈2 - 3 四面体单元 f i z2 3c e l l t r i a a g l f l a f i o n3 类存储了顶点、胞的相互连接关系，通过这种连接关系，可 以实现对三角剖分中所有四面体的遍历。t r i a n g n f l a t i o n 3 还提供t * t t 多构造三角 剖分所需的函数，如点定位函数、查询函数等。 本文主要使用t f i a a g u l a t l o a3 的派生类d c l a u n a y _ l f i a n g u l a f i o n _ 3 。 d c l a l l n a ym 日n l 叫砒i o n - 3 类在t r i a n g u l a t i o n3 类的基础上加入了空外接圆性质， 用于点集的d e l a t m a y 三角剖分。d d 卸n 8 y 伍眦g l d 撕o n - 3 类的使用非常方便，给 广东工业大学工学硕士学位论文 定需要进行剖分的点集后，用户只需一条语句便完成了剖分的编码工作。 另外，d e l a u n a y _ t r i a n g u l a t i o n 3 类也为完成剖分所需的各步骤定义了相应的 成员函数，用户可以控制节奏，逐步地完成剖分工作，甚至可以借助各成员函数 完成自定义的算法。 2 1 3 非几何因素支持工具 c g a l 的非几何因素支持工具类似于工具箱，包括有数据类型支持、s t l 扩 展、句柄、循环器、访问内部结构的受保护接口、几何对象生成器、定时器、i o 流操作符和颜色、窗口、可视化工具g e o m v i e w 等其他流支持。 支持工具主要是为c g a l 完成各种操作提供支撑。如：c g a l 通过数据类 型支持，可以实现数值的精确计算及各种几何判断；c g a l 使用并扩展了c + + 的 s t l ，如增加了双向链表等。 2 2 精确性 c g a l 一个突出的特点就是能够实现精确计算。许多计算几何算法都是在理 论上假设对数据能够实现精确的计算，有时甚至算法的健壮性也依赖于这一假设。 而实际上，计算机中的浮点数运算是有精度限制的，存在截点误差( r o u n d o f f ) 。有 限精度的计算在很多应用中也是能够满足要求的，不过在计算几何中，往往哪怕 是一些很简单的算法，如判断一个点跟一个有向线段的相对位置关系，在点非常 接近线段的情况下，就有可能因为计算精度问题而导致误判，因此，实现精确的 计算对几何基元的构造及各种几何判断就显得非常重要。 c g a l 实现算法的处理策略是，先精选一些基本问题( 如点与线的相对位置 关系等) 和基本对象( 如经过三个点的圆等) ，然后使用这些基本问题和基本对 象来构造高层算法。这样就将精确计算的任务分配给基本问题及基本对象来处理， 只要基本问题及基本对象能够给出正确的结果，高层算法就无需关心数值的精确 性。完成基本问题和基本对象的精确计算显然不只是涉及到简单的浮点运算，它 还运用了很多复杂的内容。实质上它是通过使用在原则上可以达到任意精度的数 字来提高计算的精度。 在c g a l 中，可以通过不同的数据类型来选择近似计算或是精确计算。如使 1 2 第二章计算几何算法库( c g a l ) 用c g a l 预定义的内核e x a c tp r e d i c a t e se x a c tc o n s t r u c t i o n sk e m e l 可实现算法的 精确判断及几何基元的精确构造，而使用e x a c t 可以实现精确判断和近似构造。不同的应用p，r对ed计ica算tes的i精ne度xac要t求co也nst不ructi样onskernel ， 这需要在效率和精确性之间作综合的考虑。采用精确计算时，算法的时间和空间 效率将会比采用近似计算时的差，但是结果更可靠，算法的更具健壮性。 除了算法实现的健壮性外，c g a l 也由于在设计上采用了与c + + 的s t l 很相 似的泛型编程，具有很强的灵活性。正是由于c g a l 的一系列优点，使得它在企 业生产、研究等领域获得越来越广泛的应用。随着越来越多的研究人员对它的改 进，它的版本也在逐步地提升，截止至本文完成时，c g a l 的最高版本为c g a l 3 4 ，支持w i n d o w s 及l i n u x 等操作平台。 2 3 本章小结 本章主要介绍了计算几何算法库( c g a l ) 的组成及其精确计算的优点。并特别 针对本文所涉及到的三角剖分类作了详细介绍。 广东工业大学工学硕士学位论文 第三章d e ia u n a y 三角剖分理论基础 3 1v o r o n o i 图 v o r o n o i1 9 0 8 年研究了聆维空间中点集的邻域问题【2 0 】。假设p 和l ，p 2 ，p 。) 为，? 维空间中的点集，d ( p ，p ，) 表示点p ；与点p ，的欧氏距离。以点集中的每个点 为基点，可将空间剖分成多个子区域，每一个基点p ，对应一个区域v ( p ，) 。 v ( p ，) = x ：id ( p 。，x ) 材( p ，x ) i 协夯) ( 3 - 1 ) 显然，对于v ( p 。) 中的任意点x ，它与p ，的欧氏距离最近；反之，所有与p 。的 欧氏距离最近的点集合便形成了与p i 对应一个区域v ( p ，) 。基于这种最近点原则 对空间进行剖分，其剖分结果称为v o r o n o i 图。 图3 1v o r o n o i 图 f i g 3 1v o r o n o id i a g r a m 在二维点集v o r o n o i 图的几何形状中，相邻的子区域矿( p ，) 、v ( p ，) 由p ，、p j 两点的中垂线间隔开来，每一个子区域都由其对应基点与邻点的中垂线围成。 三维点集的v o r o n o i 图中，相邻的子区域矿p 。) 、v ( p ) 由p ，、p ，两点连线 的垂直平分面间隔开来，每一个子区域都由其对应基点与邻点的垂直平分面围成。 v o r o n o i 图具有许多优良的性质。例如二维v o r o n o i 图的每一条边e 是相邻基 1 4 第三章d e l a u n a y 三角剖分理论基础 点对的垂直平分线的一个线段，恰好为两个多边形所共有，所以v o r o n o i 图的每 一个顶点恰好是图的三条边的公共交点； 当且仅当p ，是点集凸壳边界中的一点时， 所对应的子区域v ( p ) 均是闭合的。 每一个v o r o n o i 子区域v ( p ，) 都是凸的， v ( p ，) 是无边界的，除此以外，其他点 v o r o n o i 图的另外一个很重要的性质就是与d e l a u n a y 三角剖分之间的对偶关 系。d e l a u n a y 于1 9 3 4 年提出，在点集的v o r o n o i 图中，以线段连接相邻子区域y ( p ) 所对应的基点，可得到v o r o n o i 图的对偶图，该对偶图完成了点集的三角剖分。 现在这种三角剖分被称为点集的d e l a u n a y 三角剖分。 图3 - 2v o r o n o i 图与对偶图d e l a u n a y 三角剖分 f i g 3 - 2v o r o n o id i a g r a ma n dd e l a u n a yt r i a n g u l a t i o n ( a ) v o r o n o i 图 ( b ) 连接相邻基点( c ) d e l a u n a y 图 图3 - 3 由v o r o n o i 图到d e l a u n a y 图 f i g 3 3f r o mv o r o n o id i a g r a mt od e l a u n a yd i a g r a m 广东工业大学工学硕士学位论文 若点集中出现多于三点共圆( 二维) 或是多于四点共球( 三维) 的退化情况 时，以上对d e l a u n a y 三角剖分的定义会失效。实际上在这种退化情况下的 d e l a u n a y 三角剖分，其结果不是唯一的，但任一种形式的结果都认为是正确的。 3 2 三角剖分 三角剖分是计算几何中的一个重要研究内容，处理对象通常是r ”中的点集。 它根据某种规则连接点集中的各点，生成由三角形面所组成的网格。通常都要求 网格中的各三角形紧密相连，互不重叠。严格定义如下： 定义：对r ”空间点集p 0 l ，p 2 ，p 。) 的三角剖分丁是指，将尸0 l ，p 2 ，p 脚) 的凸壳划分成一系列刀维单纯形，其中： 1 ) 丁的顶点集合为p 0 l ，p 2 ，p 。) 。 2 ) 丁中的三角形面、线段、点为各门维单纯形所共享，各单纯形互不重叠。 3 ) 一系列胛维单纯形的并集为p p 。，p ：，p ，) 的凸壳。 ( b )( c )( d ) 图3 4 剖分方法 f i g 3 - 4t r i a n g u l a t i o n 对同一点集可有不同的剖分方法，以二维点集三角剖分为例，如图3 4 所示， 其中( a ) 为合法；( b ) 、( c ) 、( d ) 为不合法。图( a ) 中的三角剖分中，如果各个三角 形均具有内部不包含其他点的外接圆，则为d e l a u n a y 三角剖分。 3 3d e l a u n a y 三角剖分 d e l a u n a y 三角剖分是一种优化的三角剖分技术。它通过连接点的方式，将点 集的凸壳剖分成一系列三角形( 二维) 或四面体( - - 维) 单纯形。凸壳内的各单 1 6 第三章d e l a u n a y 三角剖分理论基础 纯形间相交于点、线、面或空集。各单纯形紧密相连，互不重叠；所有单纯形的 并集构成了点集的凸壳。 相比较于其他三角剖分技术，d e l a u n a y 三角剖分的最大特点在于它的每一个 三角形均具有空外接圆性质。对于任意的三角剖分，如果其中的某条边三( p ，p ，) ， 存在一个过它两个端点且内部不包含其他点的圆，则称边三( p ，p ，) 是d e l a u n a y 的；如果其中的某个面f ( p ，p ，p 。) ，存在一个过它三个顶点且内部不包含其他 点的圆，则称面，( p j ，p ，p ) 是d e l a u n a y 的。 定义：对于点集的任意三角剖分丁，如果它的每一个三角形都是d e l a u n a y 的， 则r 为点集的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 三角剖分的算法来讲， 如b o w y e r w a t s o n 2 1 2 2 算法，如何处理共圆的退化情况是一个需要考虑的问题。 定理：对于尺”( 玎 - - 3 ) 空间中的点集p ( p 1 ，p 2 ，p 。) ，构造其d e l a u n a y 三角 剖分d t ( p ) ，v p f ，p ，p i ，p ，尸p 1 ，p 2 ，p 。) ： 1 ) 设p ，、p ，是线段l ( p ，p ，) 的端点，当且仅当存在一个过p 。、p j 的圆 ( r l - - 2 ) 球( 刀= 3 ) ，其内部不包含p ( p 。，p 2 ，p 。) 的任何点时，l ( p ，p j ) 存在于 d t ( p ) 中。 2 ) 设p ，、p ，、p t 是三角形面f ( p ，p ，p i ) 的顶点，当且仅当f ( p ，p j ，p t ) 的 外接圆 = 2 ) 脉( 玎= 3 ) 内部不包含p ( p 。，p ：，p 。) 的任何点时，f ( p ，p j , p i ) 存 在于d t ( p ) 中。 3 ) 设p ，、p ，、p 女、p ，是四面体t ( p ，p ，p i ，p ，) 的顶点，当且仅当 t ( p