（应用数学专业论文）三角剖分算法研究.pdf

哈尔滨理工大学理学硕士学位论文 三角剖分算法研究 摘要 三角剖分是计算机辅助几何设计、几何造型及计算机图形学中研究的重 要内容之一。对于设计一个三角剖分算法来说，最重要的就是其复杂度低和 高质量网格的形成。三角剖分算法在计算几何、曲面重构及有限元网格生成 中有着重大的应用价值。本文研究内容如下： 1 首先介绍了离散点和多边形三角剖分的些基本理论，以及v o r o n o i 图和d e l a u n a y 三角剖分的定义，包括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 本文重点在第四章，首先介绍了平面点集三角剖分的定义，接着对 主要的平面点集三角剖分算法进行了介绍，并且采用了对比方式进行分析描 述。在d e l a u n a y 三角剖分优化准则的基础下，提出了一种新的平面点集三 角剖分算法。该算法的基本思想就是生成一个满足的条件的三角形，以每条 边为基础向周围寻找可以满足条件的点，生成新的三角形，再以新的三角形 为基础向周围生长，直至覆盖平面中的所有点。该算法的时间复杂度为 o ( n l o g n ) ，很好地避免了病态三角形的出现，提高了网格质量，特别适用 于有限元网格生成。 4 在二维三角剖分的基础上，推广到三维空间。首先介绍了凸壳的一 些基本概念和平面点集凸壳的一些重要算法。接着给出了两个三维空间点集 剖分算法。一种算法是：先求得点集的凸壳，然后在凸壳区域内根据点的坐 标，利用四阶行列式的值来选择一个符合条件的点进行点集剖分。从而提高 了算法的效率。该算法的时间复杂度为o ( n l o g h ) 。另外一种是空间点集三 角剖分算法，算法的思想是：首先生成一个凸壳，接着在剩下的点再形成一 哈尔滨理工大学理学硕士学位论文 个凸壳，依次类推。所有的点都划成凸壳，接着关键就是凸壳之间的连接。 这样可以保证生成更好的三角形，从而保证剖分质量。 关键词平面点集：d e l a u n a y 三角剖分；凸多边形；凸划分；有限元网格 ：筌鎏垩三奎兰垩耋罂圭兰竺丝兰 r e s e a r c ho nt r i a n g u l a t i o na l g o r i t h m a b s t r a c t t r i a n g u l a t i o ni so n eo ft h ei m p o r t a n tr e s e a r c hc o n t e n t si nc o m p u t e ra i d e d g e o m e t r yd e s i g n ，g e o m e t r ym o d e l l i n ga n dc o m p u t e rg r a p h i c s f o rt h e t r i a n g u l a t i o na l g o r i t h md e s i g n ，t h em o s ti m p o r t a n ti st om a k et h ea l g o r i t h mh a v e l o wt i m ec o m p l e x i t ya n dt oc r e a t en e tl a t t i c ew i t hh i g l lq u a l i t y t r i a n g u l a t i o n a l g o r i t h mh a ss i g n i f i c a n ta p p l i c a t i o n si nc o m p u t a t i o n a lg e o m e t r y , c u r v e ds u r f a c e c o n s t r u c t i o na n df i n i t ee l e m e n t 鲥dg e n e r a t i o n r e s e a r c hc o n t e n t so ft h i sp a p e ri s a sf o l l o w s ： f i r s t ，s o m ef u n d a m e n t a lt h e o r i e so fd i s c r e t ep o i n ta n dp o l y g o nt r i a n g u l a t i o n a r ei n t r o d u c e d ，a n dr e l a t e dd e f i n i t i o n ss u c ha sv o r o n o ig r a p ha n dd e l a u n a y t r i a n g u l a t i o na r ed e s c r i b e d ，i n c l u d i n gt h eo p t i m i z a t i o nr u l e s e c o n d l y , t h ep o l y g o nt r i a n g u l a t i o nh a sb e e ns t u d i e d i th a si n t r o d u c e dt h e d e f i n i t i o n sr e l a t e dt oc o n v e xp o l y g o na n dt h ec o n v e xp a r t i t i o na l g o r i t h mf i r s t i n c o n v e xp a r t i t i o n ，t h ep e c u l i a rc a s ei st h a tt h eg e n e r a t e dc o n v e xp o l y g o ni sa t r i a n g l e t h em a i ni d e ao ft h ea l g o r i t h mi s t od e l e t e t h eb r a n c hp o i n tf i r s t ( m e a n w h i l ei ti sac o n v e xp o i n t ) b yc u t t i n gt h ee a r st om a k et h et w oc h a i nu s e d t ot h ep a r t i t i o nb em o n o t o n o u s ，t h e nt op a r t i t i o nt h et w ee h a i n s u n f o r t u n a t e l y t h e r ew i l lb et h el o n ga n dn a r r o wt r i a n g l e sc r e a t e di nt h ep a r t i t i o nw i mt h i s a l g o r i t h m s o w h e nat r i a n g l ei s p r o d u c e d ，t h ed e l a u n a yt r i a n g u l a t i o n o p t i m i z a t i o nc r i t e r i o ni su s e di no r d e rt og e n e r a t et r i a n g l e sw i t hm u c hb e t t e r q u a l i t y t h em a i nb o d yo ft h i sp a p e ri sd e s c r i b e di nt h ef o u r t hc h a p t e r s o m e t r i a n g u l a t i o na l g o r i t h m sf o ras c a t t e r e dp o i n ts e ti nt h ep l a n ea r ei n t r o d u c e da n d a n a l y s e db ye o m p a r i s i o na f t e rt h ed e f i n i t i o no ft r i a n g u l a t i o nf o ra s c a t t e r e dp o i n t s e ti nt h ep l a n e t h e n ，an e wt r i a n g u l a t i o na l g o r i t h mf o ras c a t t e r e dp o i n ts e ti n t h ep l a n ei sp r o p o s e du n d e rd e l a u n a yt r i a n g u l a t i o no p t i m i z a t i o nc r i t e r i o n t h e m a i ni d e ao ft h ea l g o r i t h mi st h a tat r i a n g l es a r i s f 甄n gt h ec o n d i t i o n so ft h e t r i a n g u l a t i o ni sg e n e r a t e df i r s t ，t h e nt h ep o i n t ss a t i s f y i n gt h ec o n d i t i o n so ft h e - 1 1 1 堕堑堡兰三查兰堡兰堡圭兰丝篁兰 t r i a n g u l a t i o na r et ob es e a r c h e dt ot h eo u t s i d eo ft h et r i a n g l et oc r e a t eu e w t r i a n g l e s ，t h i sp r o c e s si sr e p e a t e du n t i la l lg i v e np o i n t sa r ed e a l tw i t h t h et i m e c o m p l e x i t yo ft h i sa l g o r i t h mi so ( nl o gn ) t h ei l lt r i a n g l e sa r ea v o i d e db e i n g c r e a t e da n d t h eq u a l i t y o f n e t p a r t i t i o ni s i m p r o v e d g r e a t l y a n d t h e p a r t i t i o n i s s u i t a b l et ot h eg r i dg e n e r a t i o nf o rf i n i t ee l e m e n ta n a l y s i s l a s t ，t h e t r i a n g u l a t i o na l g o r i t h m s i n t h e p l a n ea r ege n e r a l i z e d t o t h et h r e e d i m e n s i o n a ls p a c e t h er e l a t e dc o n c e p t sa n ds o m ei m p o r t a n ta l g o r i t h m sf o r c o n v e xh u l lo fp o i n ts e ti nt h ep l a n ea r ei n t r o d u c e df i r s t t h e nt w op a r t i t i o n a l g o r i t h m sf o rp o i n ts e ti nt h et r e ed i m e n s i o na r eg i v e n ，t h ei d e ao fo n e o f t h e m i st h a tt h ec o n v e xh u l li sc o m p u t e df i r s t ，t h e nt h ep o i n t ss a r i s f y i n gt h ec o n d i t i o n o fp a r t i t i o nf f i es e l e c t e db vt h ev a l l i eo fad e t e r m i n a n to ff o u ro r d e rt op a r t i t i o n t h ep o i n ts e t t h et i m ec o m p l e x i t yo ft h i sa l g o r i t h mi so ( nl o gn ) a n dt h ei d e a o ft h eo t h e ra l g o r i t h mi st h a tt h ec o n v e xh u l li sc o m p u t e df o rt h eg i v e np o i n ts e t ， t h e l lt h ec o n v e xh u l lf o rt h er e s tp o i n t s r e p e a tt h i su n t i lt h e r ea r el e s st h a nt h r e e p o i n t sl e f t t h ek e ys t e pi st h el i n kb e t w e e na n ya d j a c e n tt w oc o n v e xh u l l s t h e p a r t i t i o nw i t hh i 班q u a l i t yc a n b eg e n e r a t e dw i t ht h i sa l g o r i t h m k e y w o r d sp o i n ts e t i nt h ep l a n e ；d e l a u n a yt r i a n g u l a t i o n ；c o n v e xp o l y g o n ； c o n v e xp a r t i t i o n ；f i n i t ee l e m e n tg r i d i v 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文三角剖分算法研究，是本 人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究工作所取 得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的 研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方式注 明。本声明的法律结果将完全由本人承担。 作者签名： l 写擎矽 日期：z 7 年月，g 日 哈尔滨理工大学硕士学位论文使用授权书 三角剖分算法研究系本人在哈尔滨理工大学攻读硕士学位期间在导师 指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所有，本论 文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大学关于 保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子版 本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或 其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 ，不保密d 。 ( 请在以上相应方框内打) 作者签名：日期：7 - , 0 7 年弓月fp 日 导师签名：扒老咳日期：。乙呷年3 月f 矿日 哈尔滨理1 = 大学理学硕士学位论文 1 1 研究目的及意义 第1 章绪论 计算几何的内容属于欧几里得的几何构造范畴，即由算法和算法的复杂性 分析组成。欧几里得的几何构造满足算法的所有要求：无二义性、有穷性、确 定性、能行性、输入、输出、正确性等。它与计算机图形学的区别就是计算机 图形学是研究用计算机进行图形处理和图形运算的学科，而不是算法分析。与 几何定理机器证明的区别在于几何定理机器证明主要研究定理证明的探索方法 及证明过程的推断，而不是几何本身。计算几何是方法论，而不是严密的公理 化的科学体系。因为经典的几何对象的表征常常不适合于有效算法的设计，所 以计算几何的目的在于寻找能用计算机高效的解决几何构造问题的算法。所以 要建立一些几何实体。此学科是从实践中来，回实践中去，属应用范畴。三角 剖分是计算几何中的一个非常重要的分支，是计算几何领域中的重要课题之 一，它具有广泛的应用价值。三角形是平面域的单纯形，与其他类型的多边形 相比，它具有许多特性和优点。例如它可以更好的贴近拟合复杂边界；有限元 自动生成，计算机图形处理及模式识别需要三角剖分来解决；三维实体几何造 型系统中的曲面描述及隐藏面消除等许多领域中也都存在三角剖分问题算法。 在各种不规则的网格剖分算法中，d e l a u n a y _ = 角剖分是比较常用的方法。因为 它具有“三角剖分最小内角最大”的性质，尽可能避免病态三角形的出现，从 而保证了网格整体质量最优以及有限元迭代算法的稳定可靠。可以况三角剖分 算法是计算机图形学的一个非常重要的理论基础。 1 2 国内外现状分析 到目前为止，许多文献已经对三角剖分做过研究，并已提出许多有效的算 法。t s a i t l 】根据实现过程，把生成d e l a u n a y 三角网的各种算法分为分治算法、 逐点插入法、三角网成长法等3 类。r o b i n s o n l 2 1 等人运用的是逐点插入法，就 是当添加一个新点时，找出包含此点的三角形，如果落在三角形内，将此点与 三角形的三个顶点连接，并将三角形的三条边送入优化列队，按照d e l a u n a y 三角网的性质进行优化；如果落在三角形的边上，删除此边，重新建立两条新 边，并将其余两边或四边送入优化队列优化。周杰p 】等人以平面离散点集逐点 哈尔滨理1 = 大学理学硕士学位论文 插入的d e l a u n a y 三角化的方法为基础，在三角化过程中采用一定策略，将其 改进成为一种简单易行而高效的方法，能够适应包括多岛、多连通域等复杂情 况的各种边界能够生成贴体的三角网，网格能够保证符合d e l a u n a y 法则。周 培德 4 】利用平面扫描的思想，即利用从右到左移动的y 轴扫描点线集。当扫描 线达到某个给定点或给定线段端点时，将该点或端点与其上下相邻线段端点连 接。新连接线与已三角剖分的边只能在其端点处相交。另外，他还提出了平面 点集三角剖分的一种新的算法【5 】，该算法首先逐层求凸包，然后分割环域成三 角形，最后调整相邻环域的三角剖分便能获得最小权三角剖分。无论d e l a u n a y 三角剖分、贪心法三角剖分以及依据环形试探法设计的三角剖分算法，还是 e p p s t e i n t 6 】提出的三角剖分算法均不能产生最小权三角剖分。但是周培德的这 种方法就可以得到最小权三角剖分。方锡武【”等人介绍了一种有限元网格自动 生成算法，算法对点的位置没有任何限制，增加新点时，可在原有网格基础上 生成新的符合d e l a u n a y 性质的三角形有限元网格。 三角剖分已经在地理信息系统、地学、计算机图形学和虚拟现实等领域有 着相当广泛的应用。更多研究都在现实工程研究中取得了很好的成果。为了进 行长江口水动力过程的有限元数值模拟，李世森【8 】等人研究了任意平面区域的 d e l a u n a y 三角剖分和基于背景网格等值线点集的新的自动生成方法，就是在局 部三角形内得到等值线、进行自动加点；改进了d e l a u n a y 三角剖分法，从区 域边界向域内逐步三角化。另外孟倩【9 】等人对地质模型不规则网格剖分的算法 进行了优化，提出了更好的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 3 课题来源 本课题来源于导师参加的国家自然科学基金项目。 1 4 本文主要研究内容 在本文的研究中，一方面，注重吸收前人已有的研究成果，特别是关于三 角剖分的一些基本思想和算法；另一方面，针对在实际中需要保证网格的最 优，有针对性的开展了平面点集三角剖分算法的研究。 1 在单调多边形三角剖分算法中，算法生成的三角形的形状多为狭长的 三角形，在此算法的基础上，将d e l a u n a y 三角剖分的优化准则更好的融入到 算法中，保证了更高质量的三角形的产生。 2 对各种平面点集三角剖分算法研究和比较。 3 提出了一种新的平面点集三角剖分算法，算法关键是每一个新的三角 形生成，而三角形的生成的关键又在于对每一条边的扩展，这就是要在点集中 寻找一个符合条件的点，为此点构成一个新的符合d e l a u n a y 三角剖分的优化 准则的三角形该算法的时间复杂度为o ( n l o g h ) 。该算法有效的降低了三角 剖分算法的时间复杂度，提高了剖分后的网格质量。 4 基于二维平面点集三角剖分，提出两种三维空间点集剖分的算法。一 种算法的思想就是先求得点集的凸壳，然后在凸壳区域内根据点的坐标，利用 四阶行列式的值来选择一个符合条件的点进行点集剖分。从而提高了算法的效 率。该算法的时间复杂度为o ( n l o g n ) 。另外一种是空间点集三角剖分算法， 算法的思想是：首先生成个凸壳，接着在剩下的点再形成一个凸壳，依次类 推。所有的点都划成凸壳，接着关键就是凸壳之间的连接。这样可以保证生成 更好的三角形，从而保证剖分的质量。 1 5 本章小结 本章首先论述了本文研究的目的和意义，阐述了三角割分算法研究在国内 外研究的现状，说明了三角剖分算法的重要学术意义与应用价值。同时简述了 本文的研究内容。 哈尔滨理工大学理学硕七学位论文 第2 章三角剖分相关概念 2 1 离散点的三角剖分 离散点的三角剖分是科学计算与分析中的一种重要方法，在计算几何、数 据插值曲面构造甚至三维数据场可视化中得到了广泛的应用。对离散点三角剖 分方法的研究不论是在二维平面还是三维空间区域上都已经有了很多成果，尤 其是对二维平面离散点三角剖分的研究，其理论和算法已经成熟，但是对于三 维离散数据的三角剖分，特别是曲面形状比较复杂。散乱点的数量很大的时 候，当前的算法在适应性、应用效果等方面还需要进一步提高。 给定一组散乱数据点 k ) ( f _ 1 ，2 ，) ，如何将各点之间以三角形相互连 接，形成一张三角网格，并使网格质量较优? 该问题的解是散乱点集( 以 的一个三角剖分，其实质是以三角网格反映各 个数据点与其邻近之间的拓扑连接关系，从而揭示数据点之间的内在本质联 系。 三角剖分所涉及的问题在实际应用中根据数据点位置的不同有两种情况： 二维和三维。所谓二维是指所有的数据点都位于同一个平面上，若此条件不成 立，则是三维情况。 根据这种情况，三维散乱数据的三角剖分可分为对三维散乱数据投影域的 剖分和在空间中直接剖分两种类型。散乱数据的投影域包括平面域和球面域直 接三角剖分方法研究如何直接将散乱数据点在空间中连接成一个优化的三角网 络。 许多学者都对二维平面域内散乱数据点三角剖分的理论与方法的做了卓有 成效的研究工作，如v o r o n o i ，d e l a u n a y , l a w s o n ，b o w y e r 及周培德等等。对平 面域内散乱数据点三角剖分理论与方法的研究有助于对三维空间问题的理解与 解决。 2 2v o r o n o i 图 平面三角剖分的实质是以三角形反映数据点与其邻近点之间的拓扑连接关 系，若能首先找出平面上一点的所有邻近点，则上述问题在平面上的情况就好 哈尔滨理工大学理学硕士学位论文 办多了。为此需要解一个问题：给定平面中挖个点的集合s = p l ，p ：，见 ， 对于s 中的每个点n ，平面中比s 的其它点更接近于只的点( x ，”轨迹是什么? 直观地说，上述问题的解是把平面划分为一些区域( 每个区域是点( x ，y ) 的 轨迹点( x y ) 比s 的其它点更接近于s 的一个点。 设p 。，p z 是平面上两点，上是线段昆见，垂直平分线，上将平面分成两部分 和工。位于l l 内的点p t 具有特性： d ( 易，n ) 1 ) 维欧氏空间中给定的点集s ，d ( s ) 表示s 的d e l a u n a y 三角剖分，d ( s ) 中的任一n 维单纯形的n 维外接圆内没有s 中的 点，对于平面点集，这一准则称为空外接圆准则，对于三维点集，则称为空外 接球准则。 图2 4 中给出了外接圆的大致思想：三角形a b d 和三角形b c d 均为 d e l a u n a y 三角剖分的最优三角形，其外接圆内不再包含其他点；三角形c d e 则不是d e l a u n a y 三角剖分的最优三角形，它的外接圆内包含其他点，其中也 包括最优点b 。 2 最小角最大准则：这是平面点集d e l a u n a y 三角剖分区别于高维点集所 特有的性质。1 9 7 7 年，s i l b s o n 证明，对于平面点集而言，空外接球准则和最 小角最大准则是等价的，并且符合准则的三角剖分只有一个，即d e l a u n a y 三 哈尔滨理工大学理学硕士学位论文 角剖分。具体地说，对于给定的平面点集s ，任何一个三角剖分t ( s ) 总有一个 c 图2 4 外接圆优化准则 f i g u r e2 - 4c i r c u m c i r c l eo p t i m i z a t i o nc r i t e r i o n s 三角形的内角是最小的，而d ( s ) 中的这个最小角在所有r ( s ) 的最小角当中是 最大的。正是这一特性，d e l a u n a y 三角剖分总是尽可能避免病态三角形的出 现，自动向等边三角形靠近。需要指出的是，d e l a u n a y 三角剖分的这一特性仅 仅适用于平面点集。三维及更高的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 多面体的公共边， 并且每个顶点是四个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 四面体。 如果一个二维，三维点集中有四点共圆五点共球的情况，这时这些点对应 的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 顶点对应的d e l a u n a y 三角形四面体。这时称为退化的情况。 定义2 3 任意点集中所有v o r o n o i 顶点所对应的d e l a u n a y 三角形，四面体 的并集是对点集的一个三角四面体剖分，称其为d e l a u n a y 三角剖分四面体剖 哈尔滨理 = 大学理学硕士学位论文 分。 定义2 4 在三角四面体剖分中外接圆# b 接球内部不包含任何网格顶点的 三角形四面体称为符合d e l a u n a y 准则的三角形四面体。 定理2 1d e l a u n a y 三角四面体剖分中每个三角形四面体都符合d e l a u n a y 准则。 定理2 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 三角剖分基本理论对网格进行操作。这时为了使网格退化的局部形状网格单元 尽量饱满，可以用最小角最大等其他原则对这个局部网格进行连接。但即使这 个局部网格不是最优的连法，在对网格进行质量控制时也可以通过在外心加点 的方法立刻消除局部退化的情况。基于这些分析，在本文中将不再讨论退化的 情况。 2 4d e l a u n a y 三角网 2 4 1d e l a u n a y 三角网的介绍 三角网被视为最基本的一种网格，它可以适应规则和不规则的分布数据， 它在地形表现方面有很独特的优势。d e l a u n a y 三角网是相互邻接并且互不重叠 的三角形的集合，每个三角形的外接圆内都不包含其他顶点。d e l a u n a y 三角形 是由三个相邻点连接而成，与这三个相邻点相对应的v o r o n o i 多边形有一个公 共的顶点。 在用三角网来拟合地形表面的时候，对三角网有三点基本要求： 1 三角网必须是唯一的； 2 尽量使三角形有最佳的几何状态，尽量使每个三角形都接近等边三角 形( 也就是不要产生畸形三角形) ： 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 三角网在三维空间方面都有很广泛的应用。 2 4 2d e l a u n a y 三角网形成的方法 d e l a u n a y 三角网的构建过程和标准三角网的构造过程相似，只是在构造准 三角网的过程中，加入了局部三角形形状最优化过程，l a w s o n ( 1 9 7 7 ) 提出了根 据最大最小角度法则来建立局部几何形状最优的三角网：在出两相邻三角肜构 成的凸四边形中，交换此四边形的两对角线，不会增加这两个三角形六个内角 总和的最小值。l a w s o n 据此提出了局部优化方法( l o p l o c a lo p t i m i z a t i o n p r o c e d u r e ) ：交换凸四边形的对角线，可获得等角性最好的三角网。如图2 5 所 示，左图为优化前三角网，右图为优化后三角网，其中圆为三角形的外接劂 图2 - 5 l o p 优化示意图 f i g u r e2 - 5s c h e m a t i cg r a p ho fl o p 下面介绍几种建立d e l a u n a y 三角网的算法： 1 逐点插入法 l a w s o n 提出了用逐点插入法建立d e l a u n a y 三角网的算法思想。l e e 和 s c h a c h t e r ，b o w y e r ，w a g o n ，s l o a n ，m a c e d o n i o 和p a r e s c h i ，f l o r i a n i ， p u p p o ，t s a i 先后进行了发展和完善。 逐点插入算法的基本步骤如下： 步骤1 定义一个包含所有数据点的初始多边形( 往往为其最小外接矩 形) ： 哈尔滨理工大学理学硕士学位论文 步骤2 在初始多边形中建立初始三角网； 步骤3 插入一个数据点p ，在三角网中找出包含p 的三角形f ，把尸与，所 三个顶点相连，生成三个新的三角形； 步骤4 用l o p 算法优化三角网； 步骤5 重复步骤2 至步骤4 直到所有的点都处理完毕： 步骤6 删除所有包含初始多边形顶点( 非原始数据点) 的三角形。 从上述步骤可以看出，逐点插入算法的思路非常简单，先在包含所有数据 点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用l o p 算法 确保其成为d e l a u n a y 三角网。各种实现方法的差别在于其初始多边形的不同 以及建立初始三角网的方法不同。 2 三角网生长法 g r e e n 和s i b s o n 首次实现了一个生成d i r i c h l e t 多边形图的生长算法。 b r a s s e l 和r e i f 稍后也发表了类似的算法。m c c u l l a g h 和r o s s 通过把点集分块 和排序改进了点搜索方法，减少了搜索时间。m a u s 也给出了一个非常相似的 算法。 三角网生长算法的基本步骤如下： 步骤l 以任一点为起始点，找出与起始点最近的数据点相互连接形成 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 三角形 的第三点： 步骤3 基线的两个端点与第三点相连，成为新的基线； 步骤4 重复步骤2 至步骤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 三角形的另一端点，依次处理所有新生成的边，直至最终 完成。各种不同的实现方法多在搜寻“第三点”上做文章。 3 分治法 s h a m o s 和h o e y 提出了分治算法思想，并给出了一个生成v o r o n o i 图的分 治算法。l e w i s 和r o b i n s o n 将分治算法思想应用于生成d e l a u n a y 三角网，他 哈尔滨理工大学理学硕士学位论文 们给出了一个“问题简化”的算法，递归的分割点集，直至子集中只包含三个 点而形成三角形，然后自下而上的逐级合并生成最终的三角网。以后l e e 和 s c h a c h t e r 又改进和完善了l e w i s 和r o b i n s o n 的算法。 分治算法的基本步骤如下： 步骤1 把点集以横坐标为主，纵坐标为辅按升序排序； 步骤2 把点集分为近似相等的两个子集； 步骤3 在两个子集中生成三角网； 步骤4 用l a w s o n 提出的局部优化算法l o p 优化所生成的三角网，使之成 为d e l a u n a y 三角网； 步骤5 找出连接两个子集中两个凸壳的底线和顶线； 步骤6 由底线至顶线合并两个子集的三角网； 步骤7 递归执行步骤2 至步骤6 直到点集中的所有点都参加了d e l a u n a y 三角网的构造。 以上步骤显示，分治算法的基本思想是问题简化，把点集划分到足够小， 使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用l o p 算法保证其成为d e l a u n a y 三角网，不同的实现方法可有不同的点集划分法、 子三角网生成方法及合并方法。 2 5 本章小结 本章主要介绍了三角剖分的基本理论，首先是离散点的三角剖分的简介， 接着对v o r o n o i 图给出了描述性的定义和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 三角网和它的形成方法。 第3 章多边形的三角剖分 多边形分为凸多边形和任意多边形。其中凸多边形是种特殊的多边形， 它具有很多特性，比如凸多边形的所有项点都在任一条边的同一侧等等，在实 际中很多问题常常将多边形分割称凸多边形，特别是凸多边形的特殊情况 剖分成三角形。这里首先介绍凸多边形的相关定义和凸划分的算法，最后介绍 简单多边形的三角剖分。 3 1 凸多边形的相关定义 定义3 1 由平面上若干条线段p l p 2 ，p ：见，p 。p ，围成的封闭有界域称为多 边形。其中线段两= 一1 , n ，p 。= 昆) 称为多边形的边，相邻的两条边仅在端 点相交，其交点n 称为多边形的顶点。 定义3 2 与同顶点p i 关联的两条p i 一，p i ，p i p 。，形成的位于多边形内部 的角匈。p ，p i + ，称为多边形的内角。 定义3 3 若多边形p 的顶点序列p 。，p ，岛按逆时针方向排列，并且点 p 。在p i - l p i 的左( 右) 侧，则称点n 为凸( 凹) 点。以凸( 凹) 点为顶点的 内角，r ( 丌) 。 定义3 4 所有内角都小于i t 的多边形称为凸多边形。凸多边形的所有顶点 均为凸点。 先求出凸多边形各顶点y 坐标最小值所对应的顶点，设为p ，。然后，如果 p l + ，在i i 的左( 右) 侧( f = 丽) ，那么凸多边形顶点序列是按逆( 顺) 时 针方向排列。对于任意简单多边形，可以先求出多边形顶点的凸壳，然后用上 述方法确定多边形顶点序列是逆时针排列还是顺时针排列。 3 2 多边形凸划分算法 划分多边形成凸多边形有两个目标： 1 划分多边形成尽可能少的凸多边形； 2 尽可能快地完成划分工作，即设计时问复杂性低的算法。 h e r t e l 和m e h l h o m 于1 9 8 3 年提出了一种划分多边形成凸多边形的算法， 其基本思想是从p 的三角剖分开始，重复删去非基本对角线。该算法显然在线 哈尔滨理工大学理学硕士学位论文 性时间内可以完成。可以证明这个算法产生凸多边形的数目小于4 m 。寻找最 优凸多边形数目的凸剖分比寻找次最优要花更多的时间。1 9 8 3 年，g r e e n e 设 计出最优凸剖分的一种算法，时间复杂性为0 0 4 ) 。1 9 8 5 年，k e i l 改进到 o ( n 3 l o g n ) 。如果用线段而非对角线进行剖分，那么问题就困难了。1 9 8 0 年 c h a z e l l e 设计出复杂性为o ( n 3 ) 的算法解决了这个问题。 3 2 1 相关定义 定义3 5 在由对角线划分多边形成凸多边形的划分中，如果在顶点p i 处删 去对角线d 之后产生非凸多边形，则称对角线d 关于顶点p i 是基本的。对顶点 p 。不是基本的对角线称为非基本的。 定义3 6 如果b 是多边形p 的凹点，b 一，p i ，p , p 是与p f 关联的两条 边，只一；p ；( p 。；p j ) 的延长线与p i p 。，( 见p “) 所夹的角域称为p ；的a ( c ) 域； 只一，p i 的延长线与乃+ ，乃的延长线所夹的角域称为只的口域。图3 - 1 中已示出 凹点p ：的a ，b ，c 域，顶点办，风分别落入a ，c 域，顶点岛，p 。，p ，落入占 域。利用三阶行列式的值可以判断点落入哪个域。值得注意的是，可能存在p 的某些顶点不落入某点p ，的a ，b ，c 域。 c 图3 - 1 凹点p ：的a ，b ，c 域 f i g u r e3 - 1 t h ea ，b ，cd o m a i n s f o r t h ec o n c a v e p o i n t 最 引理3 1 设吼，q j 是多边形p 的两个凹点( 如图3 - 2 所示) ，y f r q ，q 哈尔滨理工大学理学硕士学位论文 分别落入q ，q ，的b 域，瓦不与p 边相交，则瓦分割p 成两个多边形鼻与 最，并且在只，最中，g f ，吼不再是凹点。 p ，+ 2 图3 - 2 墨与足中，q ，q j 不再是凹点 f i g u r e3 - 2q ，a n d q j a r en o tc o n c a v ep o i n tb e t w e e n 丑a n d 最 引理3 2 设多边形有一个凹点q 。，其他顶点均为凸点并且分别位于g ，的 c ，a 域内，边刀的两个端点分别位于c ，a 域内( 如图3 - 3 所示) ，那么连线 7 i 与百7 分割多边形成一个三角形和两个凸多边形。 图3 - 3 多边形被分成三块 f i g u r e3 - 3t h ep o l y g o ni sd i v i d e di n t ot h r e ep a r t s 哈尔滨理工大学理学硕士学位论文 3 2 2 凸划分算法 周培德f 4 3 1 于1 9 9 7 年提出的种剖分多边形成凸多边形的算法，这个算法 的大致思想与步骤如下： 步骤l 确定多边形尸的凹、凸顶点，然后逐个处理凹点，将凹点都变为凸 点，从而达到了分割多边形为凸点的目的。 步骤2 处理凹点g i 的时候。利用定义3 6 ，划分q ，