（计算机软件与理论专业论文）三角剖分的应用研究.pdf

辽宁师范大学硕士学位论文 三角剖1 分的应用研究 摘要 三角剖分是计算机辅助几何设计研究的重要内容之一。它广泛地应用在有限元分析 和信息可视化等领域。对于仅包含离散点的数据集，可以采用离散点无约束d e l a u n a y - - - 角剖分算法得到强健的三角网格；而对于数据模型中包含数据点以及数据点之间的约束 条件的情况下，就要通过约束条件的指导对数据集进行三角剖分构造三角网格，并称这 种构网方式为约束三角剖分。本文针对用户交互式输入的轮廓线进行了改进的三角剖分 方法，并基于此三角剖分模型进行了骨架的提取。本文研究的内容如下： 1 首先介绍了离散点的d e l a u n a y - - 角剖分和v o r 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 三角剖分 与v o r o n o i 图的对偶关系，对v o r o n o i 图的算法进行分析与归纳。 2 主要研究平面点集相关的三角剖分算法其中包括平面无约束的三角剖分和约束 三角剖分的算法，约束的三角剖分的算法中，由于约束条件加入的时机不同，将约束三 角剖分算法进行分类，一类算法是离散数据点和约束条件同时进行三角剖分，一类是对 于离散点先进行三角剖分，然后再加入约束条件，现在很多算法是针对后一种三角剖分 进行了研究。 3 本文重点在第四章，此章对平面三角剖分进行了应用研究，由于平面数据点集 进行三角剖分的过程中，会破坏数据的拓扑相容性，针对用户输入的轮廓线，进行的骨 架提取，采用约束三角剖分的算法对其进行区域划分，并提取了相应的骨架。有效的避 免了对轮廓线区域的外部剖分，并对将此提取骨架的方法应用于对汉字的提取中。而运 用此骨架线进行修改后，对骨架点进行提升，连接相关的边界点，形成曲线后，再选择 相应的点进行三角剖分，最后形成三角网格曲面。 关键词：v o r o n o i 图；约束三角剖分；骨架；曲面 lj 三角剖分的应用研究 a p p iie dr e s e a r c ho nt ria n g uia t io n a b s t r a c t t r i a n g u l a t i o ni sa ni m p o r t a n tp a r to f ac o m p u t e ra i d e dg e o m e t r i cd e s i g n i ti sw i d e l yu s e d i nt h ef i e l d so ff i n i t ee l e m e n ta n a l y s i s ，i n f o r m a t i o nv i s u a l i z a t i o na n ds oo n t h ed a t as e tt h a t c o n t a i n sd i s c r e t ep o i n t sc a nb eu n c o n s t r a i n e dd i s c r e t ep o i n td e l a u n a yt r i a n g u l a t i o na r es t r o n g t r i a n g u l a rm e s h ；w h e nt h e d a t am o d e li n c l u d i n gd a t ap o i n t sa n dr e s t r a i n e dr u l e s ，i ti s n e c e s s a r yt ot r i a n g u l a t i o nd a t as e t sf o rc o n s t r u c t i n gt r i a n g u l a rm e s hb yc o n s t r a i n t sg u i d e ，a n d d e f i n e dt h i sm e t h o da sc o n s t r a i n e dt r i a n g u l a t i o n i nt h i s p a p e r ，i th a sp r o d u c e dn e w t r i a n g u l a t i o na n dt h es k e l e t o ne x t r a c t i o n ，b a s i n go ni n t e r a c t i v eu s e ri n p u t r e s e a r c hc o n t e n t s o ft h i sp a p e rr e a d sa sf o l l o w s ： f i r s t ，i th a si n t r o d u c e df u n d a m e n t a lt h e o r i e so ft h ed i s c r e t ep o i n t sd e l a u n a yt r i a n g u l a t i o n a n dv o r o n o im a p ，i n c l u d i n gt h eo p t i m i z a t i o nc r i t e r i af o rd e l a u n a yt r i a n g u l a t i o n ，r e l a t e d d e f i n i t i o n sa s d e l a u n a yt r i a n g u l a rm e s h ，a st h ed u a lr e l a t i o n s h i p b e t w e e nd e l a u n a y t r i a n g u l a t i o na n dv o r o n o id i a g r a m ，i th a sa n a l y z e dt h ev o r o n o id i a g r a ma l g o r i t h m s s e c o n d l y i th a sr e s e a r c h e dm a i n l yas c a t t e r e dp o i n ts e ti nt h ep l a n ew i t hc o n s t r a i n ta n d u n c o n s t r a i n tt r i a n g u l a t i o na l g o r i t h m ，b yt i m i n gc o n s t r a i n tt r i a n g u l a t i o na l g o r i t h mc l a s s i f i e d t w ot y p ea l g o r i t h m s ，t h eo n ei st h ed i s c r e t ed a t ap o i n t sa n dt r i a n g u l a t i o nc o n s t r a i n t sa tt h e s a m et i m e ，t h eo t h e ro n e ，f i r s td i s c r e t ep o i n tt r i a n g u l a t i o n ，a n dt h e na d d i n gc o n s t r a i n t s ，m a n y a l g o r i t h m sh a sr e s e a r c h e dt h el a t t e rm e t h o d t h em a i np a r to ft h i sa r t i c l ei st h ef o u r t hc h a p t e r ，t h et r i a n g u l a t i o nw a sa p p l i e d ，t h ep l a n e t r i a n g u l a t i o no fd a t ap o i n t sd e s t r o y e dt h et o p o l o g i c a lc o m p a t i b i l i t yo fd a t a ，f o rt h ec o n t o u r l i n e s ，c a r r i e do u ts k e l e t o ne x t r a c t i o na l g o r i t h mu s i n gc o n s t r a i n e dt r i a n g u l a t i o no fi t sr e g i o n a l d i v i s i o n ，a n de x t r a c t i n gt h ec o r r e s p o n d i n gs k e l e t o n e f f e c t i v e l ya v o i d i n gt h ec o n t o u ra r e ao f t h ee x t e r n a ls u b d i v i s i o n ，a n dt h es k e l e t o no ft h i se x t r a c t i o nm e t h o di sa p p l i e dt ot h ee x t r a c t i o n o fc h i n e s ec h a r a c t e r s a f t e rm o d i f i n gt h i ss k e l e t o n ，u p g r a d e dt h es k e l e t o np o i n t s ，c o n n e c t e d t h eb o u n d a r yp o i n t sr e l a t e dt of o r mac u r v e ，t h e ns e l e c tt h ea p p r o p r i a t ep o i n tf o rt r i a n g u l a t i o n ， a n df i n a l l yf o r m e dt h et r i a n g l em e s hs u r f a c e k e yw o r d s ：v o r o n o id i a g r a m ；c o n s t r a i n e dt r i a n g u l a t i o n ；s k e l e t o n ；s u r f a c e 辽宁师范大学硕士学位论文 目录 摘要i a b s t r a c t i i 绪论l 2d e l a u n a y 三角剖分4 2 1d e l a u n a y 三角剖分相关定义4 2 1 1 三角剖分定义5 2 1 2d d a u n a y 三角剖分的定义5 2 1 3d e l a u n a y 三角剖分的局部最优化处理6 2 2v o r o n o i 图的相关概念7 2 2 1v o r o n o i 图概念及定理8 2 2 2 算法简介1 1 2 3 本章小结1 4 3 三角剖分算法研究15 3 1 离散点无约束三角剖分算法1 5 3 1 1 逐点插入法1 5 3 1 2 分治算法1 5 3 1 3 三角网生长算法1 6 3 2 平面约束三角剖分算法16 3 2 1 约束三角网相关定义1 6 3 2 2 约束三角网算法1 7 3 3 本章小结2 0 4 三角剖分的应用研究之一2 1 4 1 交互式轮廓线曲线模型与点的获得2 3 4 2 本文采用的三角剖分方法2 4 4 3 骨架提取2 8 5 三角剖分的应用研究之二3 2 5 1 骨架的修改一3 3 5 2 三维网格曲面的生成算法研究3 4 结论3 7 参考文献3 8 硕士学位期间发表学术论文情况4 1 三角剖分的应用研究 致 黪 谓| 4 2 一i v 辽宁师范大学硕士学位论文 绪论 1 1 论文的研究背景及意义 三角剖分是计算几何研究的重要内容之一，它在有限元分析、科学计算信息可视化 等应用领域有着重要应用。由于在工程分析中存在大量的复杂数据信息，应用三角剖分 就可以处理这种复杂的情况。d e l a u n a y 三角剖分对数据点集的处理，可以得到强壮三角 网络，网格满足空圆特性和最小角最大的特性n 1 ，两个性质保证了对数据点集进行剖分 时构建的三角网格唯一性，最优性，区域性。而在实际工程应用与分析中，单一的 数据描述已经不能解决实际问题，数据的存在形式往往比较复杂，数据点集中有特殊形 状的数据来描述模拟场景的复杂性，比如地学领域中的山脊线、山谷线等在地学分析时， 通常需要作为将其这些特殊的条件作为一种约束条件进行三角剖分，这种存在大量的复 杂的数据信息，应用d e l a u n a y 三角剖分就会出现错误的剖分结果，而为了避免这种情 况的发生，就要求通过数据中的约束条件的指导来进行三角剖分，这个问题则是约束三 角剖分来解决的心3 。对于约束条件的加入破坏局部最优化，很多学者进行了相关的研究 后，提出来可以通过附加条件的加入，调整剖分后的三角网格，以达到三角网格的全局 最优化。离散点的三角剖分在没有边界数据限定的条件下，保持了区域的凸多边形外 壳，它有点与点的连接规则，而对于有曲线轮廓边界要求的数据点的三角剖分， 很情况下将其转换成多边形的三角剖分，而对于直接对轮廓边界的处理上的研究 很不完善，本文针对性这个方面做出了一定的工作。基于三角剖分的骨架广泛的应用于 地理信息系统中，河流的骨架提取中，它们将目标对象转化成多边形然后进行d e l a u n a y 三角剖分，后进行骨架的提取。由于骨架是用低维描述高维物体的形状信息，很好地保 留物体的几何和拓扑信息。在对轮廓线不进行转化为多边形上，进行了三角剖分与骨架 提取的算法的研究。 1 2 三角剖分的研究现状： 1 9 3 4 俄国数学家d e l a u n a y ，针对离散点构网提出的相关准则，保证了离散点区域形 成的三角形的唯一性，这个准则的构网方式的结果得到d e l a u n a y 三角网格。随后，学者 们提出了不同的剖分算法，t s a i 口1 对d e l a u n a y - - 角网的算法三角网的实现过程进行了分 类研究将相关的算法分为分治算法、逐点插入法、三角网成长法等3 类h m 朝1 。对于数 据集中包括约束条件，这对传统的三角剖分算法提出了挑战，对于剖分后的三角网格中， 要包括这些约束条件的存在，比如初始数据集中两点之间的连线要出现在三角网中，约 束条件的存在使得三角网格不再满足d e l a u n a y - 一- - 角剖分的两个特性，一些学者在对约束 三角剖分的三角网中，对三角形的有关性质进行证明，它包括局部特性，点对边的可见 三角剖分的应用研究 性以及数据的拓扑不相容性。相关的约束三角剖分的算法，主要是针对约束条件的嵌入 进行的，对于约束条件的嵌入时机分为两大类算法，一类是不考虑约束条件，直接对数 据集合进行三角剖分。代表算法有s h e l l 盯3 ，一类是对于数据的三角剖分为两步阻】【们“引， 首先对离散点进行三角剖分，而后再对约束条件进行在已有的三角网中插入。， 1 3 骨架的研究 骨架能够充分体现图形图象轮廓的特性，对于获得目标对象的骨架线很多学者进行 大量的研究，也取得了很大的进展。骨架的表示在工程图的形状分析与识别骨架，地理 信息区域骨架确定有广泛的应用。 1 9 6 7 年，b l u m 引入了骨架的定义，不过当时称为中轴( m e d i ma x i s ) 1 。骨架的 经典定义有两种：一种是草火模型定义。另外一种是最大圆盘定义。到目前为止，对于 骨架的提取算法已经有了大量的研究成果。可以将这些算法按骨架的原始定义为两种类 型。第一类算法是根据b l u m 的“模拟森林着火 的骨架定义而产生的。由骨架特性限 制，通过由图象从外到里不断地去除冗余的图象点来求得最终图像的骨架。第二类算法 2 1 由“最大圆盘 的骨架定义出发，此定义是更直观的定义，它把骨架看作图像内最大 圆盘的圆心集合，其思想是根据某些中心属性来直接定义骨架的象素。在应用研究领域， 将河流等目标对象的轮廓转化为多边形，然后依据多边形的三角剖分化分的区域再对其 进行提取骨架，本文针对交互式输入的轮廓线上的离散点不采用这种转化成多条形的方 式，对由线状图的骨架线提出了新的思路，采用直接进行三角剖分的方法，对剖分的点 进行判定，保证了对轮廓剖分的正确性，其剖分结果不违背数据的拓扑相容性。 1 4 本文的主要工作： 本文在研究的过程中，一方面积极吸取前人的优秀理论成果，其中包括对三角剖分 的基本性质与算法，另一方面在实际应用中，针对用户交互式输入的轮廓线进行三角剖 分算法实现，并对其轮廓区域提取骨架。论文首先对d e l a u n a y 三角剖分与其对偶 v o r o n o i 图n 3 1 进行相关性质与算法的介绍，并对v o r o n o i 图的经典生成算法进行的时间 复杂度的总结；对于现有的三角剖分算法，从数据集合有无约束条件，将三角剖分方法 分为无约束三角剖分与约束三角剖分，从数据集合的所在的空间区域，对平面三角剖分 和空间三角分别进行了相关的阐述。由于三角剖分在实际中的广泛应用，特别是应用在 多边形骨架线上，本文在阐述了相关的骨架的概念与算法。并对在实际应用中，离散点 的三三角剖分有拓扑不相容性，所以很多学者为了提取对目标对象的骨架线，把目标对象 的轮廓转化为多边形，多边形中轴线，本文对其进行了创新的改进，并将此方法运用到 对于用户交互式输入的轮廓线中，首先对轮廓线进行离散点的提取后，将相邻的离散点， 记为边界边，不对其进行三角形的扩展，然后基于此剖分区域，对三角剖分后分块区域 2 辽宁师范大学硕士学位论文 的骨架线进行提取。基于二维轮廓线骨架的三维曲面重建是模型创建系统中的重要方法 之一，在这一曲面造型方法中，最有里程碑意义的方法是基于骨架修改生成三维网格曲 面的方法，本文对此核心算法展开了深入的研究分析。 三角剖分的应用研究 2d eia u n a y 三角剖分 三角剖分的研究在计算机何中一直处于非常重要的地位，它广泛的应用在地理系 统，科学可视化，计算机几何造等领域。三角剖分在各个领域的应用中，又可以分为两 种不同的情况：二维数据和三维数据，对离散点三角剖分无论是在二维平面还三维空间 区域，都已经取得了很多研究成果【l4 1 ，特别是在二维平面的离散点的三角剖分的研究工 作上有很成熟的理论和算法，如d e l a u n a y ”】，v o r o n o i ，l a w s o n ，b o w y e r 等，对于平面 的三角剖分理论与方法的研究有助于对三维的问题的解决。无论是二维的三角剖分还是 j 维的三角剖分，其实质是用三角网格来反映离散数据点间的拓扑结构关系，进而揭示 离散数据点的内在本质联系。在三维离散点的三角剖分问题上，可以分为对三维数据 投影域的剖分【怕l 和空间中直接剖分【1 7 】两种类型。但是，由于三维离散数据在空间中位置 关系非常复杂，对其进行三角剖分的已有算法中，从应用领域上讲，还要有侍提高。 2 1d eia u n a y 三角剖分相关定义 三角剖分是拓扑学中最基本的研究方法，由于三角剖分在数值分析以及计算机图形 学的广泛应用而成为研究的热点。对于离散点的三角剖分的研究来自不同领域的学者， 提出了不同的算法，这些算法不但保证了剖分三角形不会互相重叠，而且不会产生额外 顶点，完全表达了符合原始数据点集的拓扑关系。 数据点三角剖分解决的问题是：如何把一个离散数据点集( 无论是二维平面，还 是三维空间) 连接成不均匀的三角形网格，进而完成数据点集的面化或体化，如图2 1 ， 2 2 所示。 图2 1二维离散点集 f i g 2 1 t w o d i m e n s i o n a ld i s c r e t ep o i n t 4 图2 2 f i g 2 2 辽宁师范大学硕士学位论文 2 1 1 三角剖分定义 定义1 ：二维平面的有限点集肛 vi v ) ) ，由点集y 中的点作为端点构成的封闭线段 边e ，e 为e 的集合。那么该点集v 的一个三角剖分t - - ( v , e ) 是一个平面图g ，而且该平 面图满足条件： 1 除了端点，平面图g 中的边不包含点集中的任何点。 2 没有相交边存在。 3 平面图g 中所有的面都是三角面，且所有三角面的合集是散点集v 的凸包。 由此定义，我们知道，对于一个已知的点集y 来说，它的三角剖分是不确定的，它 也有可能的n 种连接的方式。如何判断这些连接三角形网的算法的优劣? 生成后的三 角形的质量问题，而且有几种判定的规则，以保证可证明某种方式得到的三角形一定条 件下是最优的? 1 9 3 4 年，d e l a u n a y 提出的三角剖分方法，解答了以上的问题，d e l a u n a y 三角剖分，有很好的性质【1 引，它在离散点的三角剖分研究历程中，有划时代意义，至今 很多学者从事相关的研究工作。 2 1 2d e i 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 d e l a u n a y 提出它的定义后，很多学者在不同的应用领域进行研究的过程中，逐渐对 此定义进行了不同方向的发展，为它成为经典的计算几何中作了不同的诠释，下面首先 给出d e l a u n a y 边的定义。 d e l a u n a y 边：假设边集 e r 2 ( v i ，v j ) 中的一条边e ( 两个端点为，f ，) ，设e 存在的条件是，圆c 以v i ，v j 两点为直径的圆，圆内( 注意是圆内，圆上最多三点共圆) 不 含点集v 中任何其他的点。则称e 为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 三角剖分：对于平面上的点集v 来说，它的一个三角剖分丁，当满足丁是 d e l a u n a y 边e 的集合时，那么该三角剖分t 称为点集v 的d e l a u n a y 三角剖分。 d e l a u n a y 三角剖分满足以下两个特性： 1 空圆特性：由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 ，三角形d a e 的外接圆内括离散点b ，不是点集中的最优三 + 角形，而三角形c b d ，a b d 的外接圆中不包含其它点，所以是最优三角形。 三角剖分的应用研究 图2 4 空圆特性 f i g2 4e m p t yc i r c l e 2 最小角最大特性：对于离散点集v 形成的所有三角剖分t ( y ) 集中，d ( i o 中三 角形的最小角是所有t ( 矿) 集中的最小角中最大的。这样可以分析，d e l a u n a y 三角网是“最接近于规则化”的三角网。具体的说是指在两个相邻的三角形构 成凸四边形的对角线，在相互交换后，凸四边形中最小角将不再增大。( 如图2 5 中，对凸四边形m q n p 来说，设最小角是l m p q ，图2 6 中，最小角为z m n q ， 由对角线p g 变换为m n 后，l m n q l m p q ，最小角不再发生变化) 这一性质保证 了“狭长”三角形不会出现在点集v 的最后的d ( 功三角剖分网格中。 p m n q 图2 5 有最小角产生 f i g2 5 am i n i m u ma n g l e p m n q 图2 6 最大最小角生成 f i g2 6 m i n ia n dm a xa n g l e 平面点集中，所有的点在平面中的此性质是平面点集所特有的，高维的离散点集的 三角网，存在着面角之间的位置关系，所以高维的三角剖分并不具有此性质。1 9 7 7 年， s i l b s o n 1 9 】证明，对于平面点集而言，空圆特性和最小角最大特性是等价的。 2 1 3d e l a u n a y 三角剖分的局部最优化处理 在理论上为了构造d e l a u n a y 三角网，删j d 刀【2 0 l 提出了局部优化过程l o p ( l o c a l o p t i m i z a t i o np r o c e d u r e ) ，在点集生成三角网的过程中，不断对其生成的三角网进行l o p 6 辽宁师范大学硕士学位论文 处理，耳pn - i 确保三角网成为d e l a u n a y 三角网，基本做法是：首先将两个具有共同边的 三角形看成一个多边形，然后对其中一个三角形运用空圆准则作，判断第四个顶点与三 角形的外接圆的位置关系，如果第四个顶点在圆的内部则修改对角线，则即完成局部优 化过程的处理。 图2 7 局部优化过程 f i g2 7 l o c a lo p t i m i z a t i o np r o c e d u r e 无论在地学分析，还是建筑等领域，d e l a u n a y 三角剖分都以它独特的性质， 为大多数学者研究的对象。那么从应用研究的角度，我们发现，d e a u n a y 三角剖 分所具有的优异特性，对于离散点的d e a u n a y 网中，每一个三角形，总是以最近 临的三点构成，任意两个相邻三角形形成的凸四边形，以它们的一条对角线，形 成的六个内角，如果可以互换的话，那么两个三角形六个内角中最小的角度不会 变大，这是d e l a u n a y 网的一个最优性。如果在三角网中任意新增、删除、移动某 一个顶点时只会影响临近的三角形。不论从区域何处开始构建，经过优化处理， 最终都将得到一致的结果。此三角网最外层的边界形成一个凸多边形的外壳。 可以发现，对于一个点集来说，它的三角剖分中存在的每个三角必须符合空圆的特 性，那么可以说这个三角剖分是此点集的d e l a u n a y 三角剖分心。 2 2 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 图的定义可以上溯到更 早的时期，1 8 5 0 年和1 9 0 8 年数学家g l d i r i c h l e t ，m g v o r o n o i 分别在他们的论文中 7 三角剖分的应用研究 讨论到v o r o n o i 图的概念。在不同领域中，v o r o n o i 图得到了广泛传播，同样也形成了 不同的名称，例如生物学定义v o r o n o i 图为中轴变换( m e d i a l a x i st r a n s f o r m ) 。物理学，化 学则称其为w i g n e r - s e i t zz o n e s ，气象学和地理学中称之为t h i e s s e n 多边形。v o r o n o i 图 可以有效化分数据点集在空间中最近距离区域和最远距离区域，这种对区域化分的合理 性，使得v o r o n o i 图在各种领域中，有非常重要的应用。比如，在空域规划设计中，提 出以v o r o n o i 图，划分空域，以保证飞机在空中飞行的安全；荷兰气候学家彳啊t h i e s s e 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 图是非常有用的查询工具，可以解决有关距离的问题。 2 2 1 v o r o n o i 图概念及定理 f o r o n o i 图对空间区域化分提供了一个有效的工具，它解决了空间中的特定对象与 其邻近的空间区域关系问题，例如在实际运用中，常提到的“地盘分割。假设将平面 看作一片胡萝卜地，选定几个特定的离散点，在每一个离散点处，放一只兔子。那么如 何合理化分每只兔子的领地，每一块领地又是什么样子的呢? 计算每只兔子的领地是什 么样的呢? 由d i r i c h l e t 的结论可知，胡萝卜地上的胡萝卜距离哪只兔子最近，就属于哪 兔子。如图2 8 所示，每一个凸多边形单元就是每一个离散点的领域。所有的多边形组 成v o r o n o i 图。1 9 0 8 年v o r o n o i 研究了相同的问题并将其扩展到了高维空间。 v o r o n o i 图的定义： 定义l ：平面点集p = p l ，p 2 ，p n ) ，( 2 n i n d e x p ：一 i n d e x ) - - - 1 ， 或者a b s ( ，p 一 i n d e x p 一 i n d e x ) = p o i n t n u m b e r - 1 ， 2 5 当以上条件成立时，则角，屁是相邻的顶点，表明勉是边界基线，不进行扩 展。 s t e p6 ：对于链表中所有的三角形都已经扩展完毕后，算法结束。 边扩展算法是整个算法的核心，对于每一条符合条件的边来说，都要进行边扩展。 那么对于待扩展边来说，形成新的三角形，需要找到符合条件的“第三点 。它应该满 足一定的条件，以a n 协助为例，当n ，乜是扩展的边。寻找的p 点要满足： 1 ) 点p 不为边p l p 2 中两点之中的一个点； 2 ) 点p 位于以p lp 2 为边的三角形的顶点肋的不同侧。 3 ) 点p 的边表中，a 乜点的使用次数均不为2 次。 4 ) 点p 为点链表中与p lp 2 形成的角度最大的点。 当p 点符合以上条件时，它即是要找的“第三点”，形成新的三角形为a 脚。将此 新形成的三角形加入到三角形链表中。 数据结构： v i s u a l c + + 是m i c r o s o f t 公司开发的重要产品之一，它用来在w i n d o w s 环境下开发 应用程序，是一种功能强大，行之有效的可视化编程工具。v i s u a l c + + 提供了m f c 类库， 它的c o b l i s t 类支持c 0 b j e c t 指针序列，或通过指针值访问有序列表。它可以方便 的构成单向或双向链表。对链表的插入，搜索，删除，循环，只需要调用封装在c o b l i s t 类的成员函数就可以了，这样我们使用m f c 类就可以高效地满足完成用户所需 要的开发的应用程序。 在对离散点进行三角剖分的过程中，主要的图形元素包括点，边，三角面片，它也 是每一个应用程序中不可缺少的，因此本文列出这些重要的数据结构，它主要包括点链 表，边链表，三角形链表，它可以保证相应的函数能够很好的完成相应的操作。 边表类： c l a s ss _ e d g e n o d e ：p u b li cc 0 b j e c t p u b l i c ： i n ts i n d e x ：1 点索引号 s h o r tp c o u n t ： 边的使用次数 s _ e d g e n o d e0 p c o u n t = 0 ：s i n d e x = 0 ：) ： 初始化 s _ e d g e n o d e ( in td e x ，in tc o u n t ) 重载构造函数 si n d e x = d e x ：p c o u n t = c o u n t ：) ： 2 6 ， 嚣 ： 点类： c l a s ss p o i n t ：p u b l i cc o b j e c t p u b l i c ： i n tp i n d e x ： d o u b l es x ： d o u b l es y ： b o o lv e r t e x ： b o o ls f i n ： c o b l is t * s e d l ： p u b l i c ： v o i di n i e d g e l is t ( c o b l is t * s t e m p ) s _ e d l = s t e m p ：) i n tg e t s l n d e x0 r e t u r ni n d e x ：) d o u b l eg e t s x0 r e t u r ns x ： d o u b l eg e t s y0 r e t u r ns y ：) c o b l is t * g e t s e d g e l is t0 r e t u r ns e d l ； s p o i n t0 i n d e x = 0 ：y = 0 ：x = 0 ：s e d l = 0 ：) s _ p o i n t ( i n ti ，i n tj ，i n tk ) ) ： 三角面片类： c l a s ss j r i a n g l e ：p u b li cc o b j e c t p u b l i c ： b o o lf l a g ： i n ti n d e x 3 ： p u b l i c ： s _ t r i a n g l e0 ) ： s _ t r i a n g l e ( i n ti ，i n tj ，i n tk ) ) 2 7 顶点的序号 点的坐标 点的坐标 与该点相关的边使用次数 点是否在三角形中 边表指针 初始化边表 初始化 重载构造函数 该三角形是否已经扩展 顶点的索引号数组 重载构造函数 帑“_ ；氮 三角剖分的应用研究 ： 三角剖分算法的实行 由程序的流程可知，三角剖分的主要是创建初始三角形算法和对三角形进行循环扩 展算法，以及找新点扩展边形成新的三角形算法构成，三者的功能由创建初始三角形函 数i n i t t r i0 ，循环扩展三角形函数e n l a r g e t r i0 ，对于边的扩展函数e n l a r g e e d g e0 三个函数实现。本文对于边界边的判断为：对三角形的三个顶点来说，判断其两点是否 为边界基线。如果为边界基线的话就不进行此边的扩展了。 i f ( ( a b s ( ( p 2 一 i n d e x ) 一( p 3 一 i n d e x ) ) ! = 1 ) ( a