（应用数学专业论文）散乱数据点集的三角bézier曲面重构算法研究.pdf

哈尔滨理工大学理学硕士学位论文 散乱数据点集的三角b 6 z i e r 曲面重构算法研究 摘要 曲面重构技术在曲面测量造型与可视化等领域有着广泛的应用背景 本文 从散乱点集曲面重构问题出发 对三角b 6 z i e r 曲面相关性质和理论进行系统研 究 基于国内外经典算法研究成果 实现了任意拓扑网格分段g 连续几何重 建 论文首先对曲面重构国内外研究现状进行分析 得出利用三角b 6 z i e r 曲面 拟合的重要应用前景 确立论文的研究内容 通过散乱点集的邻域结构及其经典算法研究 提出并论证了计算散乱点集 d e l a u n a y 三角剖分的方法 即平面点集d e l a t m a y 三角剖分的局部构造算法 然后对三角b 6 z i e r 曲面相关性质全面介绍 着重论述三角 b 6 z i e r 曲面的基 本原理及其拼接中的参数连续性和几何连续性问题 当曲面形状比较复杂时 使用单张曲面片常难以满足要求 而需要采用多种曲面片进行连接 这就要求 在曲面片的接合处达到一定的连续性要求 参数连续性逐渐被几何连续性所代 替 得到了沿边界g 1 连续的曲面需要至少四次的三角b 6 z i e r 曲面 论文最后针对任意拓扑曲面的几何重建问题 提出了两种新的c t 分割算 法 一种采用了三角域上的b b 曲面 另一种采用了矩形域上的b 6 z i e r 曲 面 第一种算法的特点是重建结果不依赖于顶点的处理顺序 不需要进行控制 顶点的初估及修正 可使各控制顶点的计算一次完成 第二种算法的创新之 处在于它首次在该问题上采用了矩形域上的b 6 z i e r 曲面 因而可被大多数 c a d c a m 软件所直接采用 由于两种算法都是完全局部的 且对多余的自由 度进行了合理的分配 因此具有较高的效率 并可构造相对光顺的插值曲面 关键词三角b 6 z i e r 曲面 曲面拟合 d e l a u n a y 三角剖分 曲面重构 堕玺堡型三奎兰堡兰堡圭耋堡篁兰 a l g o r i t h m r e s e a c ho nr e c o n s t r u c t i o no f t r i a n g l e b e z i e rs u r f a c eo fs c a t t e r e dd a t ap o i n t s a b s t r a c t t h et e c h n i q u eo fs u r f a c er e c o n s t r u c t i o nh a se x t e n s i v ea p p l i c a t i o n si ns u r f a c e m e a s u r i n gm o d e l i n ga n dv i s u a l i z a t i o na n ds u c hf i e l d s t h i sp a p e rs t a r t sw i t ht h e p r o b l e m sa b o u ts u r f a c er e c o n s t r u c t i o n o f s c a t t e r e d p o i n t s a n d m a k e sas y s t e m a t i c r e s e a r c ho nt h ep r o p e r t i e sa n dt h e o r yo ft r i a n g l eb r z i e rs u r f a c e a n db a s e do n d o m e s t i ca n di n t e m a t i o n a lc l a s s i c a la l g o r i t h md e v e l o p m e n t a r b i t a r yt o p o l o g i c a lg r i d p i c e w i s e g 1c o n t i n u o u sg e o m e t r i cr e c o n s t r u c t i o ni sc a r r i e do u t a tf i r s t t h i sp a p e ra n a l y s e st h es t a t u so fi n t e r n a t i o n a la n dd o m e s t i cr e s e a r c hi n r e l a t i v ef i e l d d e r i v e st h ep r a c t i c a lp r o s p e c ta n da d v a n t a g e so fu s i n gt r i a n g l eb r z i e r s u r f a c ef i t t i n gt e c h n i q u e w h i c hm a k e sf o u n d a t i o nf o rt h er e s e a r c hc o n t e n to ft h i s p a p e r t h el o c a ls t r u c t u r eo fas c a t t e r e dp o i n ts e ta n di t sc l a s s i c a la l g o r i t h m sa r e i n v e s t i g a t e d a na l g o r i t h mf o rd e l a u n a yt r i a n g u l a t i o nf o r s c a r e r e dp o i n t si s s u g g e s t e d w h i c hi sf r o mp o i n t si np l a n e t h e nt h i sp a p e ri n t r o d u c e st h er e l a v e n tc h a r i c t r e r i s t i co ft r i a n g l eb 6 z i e rs u r f a c e s t r e s s e st h eb a s i cp r i n c i p l eo fb r z i e rs u r f a c ea n dt h ep a r a m e t r i cc o n t i n u i t y g e o m e t r i c c o n t i n u i t y s i n g l es u r f a c ei sh a r dt om e e tt h er e q u i r e m e n tw h e nt h es h a p eo fs u r f a c e i sc o m p l i c a t e d c o n n e c t e dm u l t i p l es u r f a c e sa r ea d o p t e d w h i c hr e q u i r e st h a tt h e r eb e s o m el i m i t a t i o ni nt h ec o n t i n u i t ya tt h ej o i n t p a r a m e t r i cc o n t i n u i t yi sr e p l a c e db y g e o m e t r i cc o n t i n u i t y t h es u r f a c et h a ti sg 1c o n t i n u o u sa l o n gt h eb o u n d a r yn e e d sa t l e a s tq u a dp o w e rt r i a n g l eb r z i e rs u r f a c e i nt h ee n d t w on e wc ta l g o r i t h m sa r ep r o p o s e df o rg e o m e t r i cr e c o n s t r u c t i o n o fa r b i t r a r yt o p o l o g i c a ts u r f a c e s o n eo ft h e ma d o p t sb bp a t c h e so nt r i a n g l e sa n d t h eo t h e rb r z i e rp a t c h e so nr e c t a n g l e s t h ef i r s ta l g o r i t h m g i v e su n i q u er e s u l t u n a f f e c t e db yt h eh a n d l i n go r d e ro f p o i n t sc o n c e r n e d a n dt h ec o n t r o lv e r t e x e sc a nb e c a l c u l a t e da to n c e w i t h o u t i n i t i a les t i m a t i o na n dc o r r e c t i o n t h e i n n o v a t i o no f t h e s e c o n da l g o r i t h mi st h a tb r z i e rp a t c h e so nr e c t a n g l e sa r ea d o p t e df o rt h ef i r s tt i m e i i 堕尘堡些三查兰堡兰堡圭耋竺丝三 f o r t h i sp r o b l e m h e n c ei tc a nb ed i r e c t l ya d o p t e db ym o s tc a d c a ms o f t w a r e b e c a u s et h et w oa l g o r i t h m sa r e c o m p l e t e l yl o c a l a n d r e d u n d a n tf r e e d o m sa r e a s s i g e dr e a s o n a b l y t h e y a r eh i g h l ye f f i c i e n ta n dc o m p a r a t i v e l ys m o o t hi n t e r p o l a t i n g s u r f a c e sc a nb ec o n s t r u c t e d k e y w o r d st r i a n g l eb 6 z i e rs u r f a c e s u r f a c ef i t t i n g d e l a u n a yt r i a n g u l a t i o n s u r f a c e r e c o n s t u c t i o n 1 i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明 此处所提交的硕士学位论文 散乱数据点集的三角b 6 z i e r 曲面 重构算法研究 是本人在导师指导下 在哈尔滨理工大学攻读硕士学位期侧独 立进行研究工作所取得的成果 据本人所知 论文中除已注明部分外不包含他 人己发表或撰写过的研究成果 对本文研究工作做出贡献的个人和集体 均己 在文中以明确方式注明 本声明的法律结果将完全由本人承担 作者签名 撇 闩期 p q 年 月f g 日 哈尔滨理工大学硕士学位论文使用授权书 散乱数据点集的三角b 6 z i e r 曲面重构算法研究 系本人在哈尔滨理工大 学攻读硕士学位期问在导师指导完下成的硕士学位论文 本论文的研究成果归 哈尔滨理工大学所有 本论文的研究内容不得以其它单位的名义发表 本人完 全了解哈尔滨理工大学关于保存 使用学位论文的规定 同意学校保留并向有 关部门提交论文和电子版本 允许论文被查阅和借阅 本人授权哈尔滨理工大 学可以采用影印 缩印或其他复制手段保存论文 可以公布论文的全部或部分 内容 本学位论文属于 保密口 在年解密后适用授权书 不保密团 请在以上相应方框内打1 j 作者签名 寺祝幻 只期 沙司年弓月悖日 导师签名 吣司 钐唔同期 d 矗乎 f 三月f 日 堕查童垩三查兰矍耋璧圭兰堡鎏兰 1 1 研究目的及意义 第1 章绪论 随着信息时代的到来 全球统一市场的逐渐形成 加剧了世界市场的竞 争 使得市场对产品的价格和性能更为敏感 产品的生命周期变得越来越短 产品的更新换代频繁 生产批量减小 如何低成本高效率地开发新产品 已成 为赢得市场竞争的首要因素 传统的产品开发方式已难以满足新的市场竞争的 需求 而曲面重构技术则以其在快速产品开发中的独特优势 得到了广泛重视 和迅速发展 曲面重构技术就是将已有产品模型或实物模型转化为工程设计模型或概念 模型 曲面重构的设计过程与传统的设计过程是完全不同的 传统的正向设计 过程是在市场调研的基础上 根据功能和用途来设计产品 得到图纸或c a d 模型 经检验满意后制造出产品来 而曲面重构技术是从己存在的零件或产品 实物原型入手 首先通过测量扫描系统等先进的数字化处理手段获得产品的实 物信息 即用一个庞大的三维数据点集来表示整个零件 然后利用c a d 模型 重构技术快速准确地建立产品数学几何模型 再在工程分析的基础上 数控加 工出产品或加工出产品模具后制成产品 实物原型重构是通过大量的测量数据来重构实物模型 由于只有通过测量 数据点来进行反向建模 造型的过程是被动的 自由度很小 因此使得反向建 模比正向设计的技术高度要大很多 目前 实物原型重构尚未形成成熟的技术 集成c a d c a e c a b i 系统中去 在当前国内外通用的c a d c a e c a m 软件系 统中 如美国e d s 公司的u g i i 法国m a h a 公司的e u c l i d 及s h i m 美国 s d r c 公司的i d e a s 美国ipi c 公司的p m e n g i n e e r 和日本h z s 公司的 g r a d e c u b e n c 等 只有l t g i i p r o e 和s t r i m1 0 0 软件具有专门的反求模 块 但都只能进行简单曲面的拟合 对复杂自由曲面的测量数据点集 直接拟 合得到的曲面光顺性较差甚至失真 u g i i 提供的由测量数据点集直接拟合自 由曲面的功能限制在矩形区域的数据点集 对于区域边界不呈矩形或是曲面形 态复杂的数据点集 拟合得到的曲面失真很大 u g n 还提供一种由点一线一 曲面的曲面重构方法 但测量点顺序 测量精度以及测量点拟合曲线的光顺性 等都会直接影响重构曲面的质量 往往造成重构曲面的光顺性较差 并且不适 堕查堡矍三查兰矍兰堡 兰堡兰三 合空间散乱数据点集的曲面重构 美国i m a g ew a r e 公司开发的曲面重构专用软 件s u r f a c e r 反向造型的方法与u g i i 类似 也具有同样的问题 对空间散乱数 掘的处理也比较困难 由测量数据点反求实物曲面模型 可以通过两个途径来实现 1 由测量数据点拟合得到曲线进行曲面建模 由于大部分测量数据是散 乱点集 用这种方法很难得到光顺曲线 同时难以保证由多条曲线拟合得到光 顺的曲面 曲面重构精度低 2 通过测量数据点直接进行曲面拟合 首先根据数据点集建立拓扑网 格 然后根据网格拟合 导到测量曲面的三维数字模型 与前一种方法相比 这 种方法更为智能 自动 用户交互少 重构的曲面精度高 因此实物原型重构 路线通常采用第二种途径 实物测量数据的曲面重构 最早是采用四边参数域拟合技术 因此早期数 据点集的网格划分研究都集中在四边形网格划分 由于对散乱数据四边域曲面 拟合的效果不佳 相比而言 三角形网格比四边形网格更为稳定 更能灵活反 映实际曲面复杂的形貌 对复杂边界也能很好地表达 适用于任意分布的散乱 数据点集 因此人们在四边域曲面拟合中 四边形无法很好表达的部分引入了 三角形单元格 并开始探讨三角b 6 z i e r 曲面拟合 研究三角网格的划分 在曲 面重构中取得了较好的应用 目前三角b 6 z i e r 曲面是比较流行的三角域建模方 法 1 2 国内外研究现状分析 c a g d 中由己知数学方程生成的曲线曲面称为规则曲线曲面 例如柱 锥 球面等 常用隐函数或二次方程的显函数来表示 但是在汽车 轮船 飞 机 模具 艺术品等产品设计中 存在大量的曲线曲面是不能用二次方程来描 述的 这类没有数学表达式的曲线曲面称为自由曲线 f r e ef o r m c u r v e 和自由 曲面 f r e ef o r ms u r f a c e s 这些是计算机辅助几何设计所研究的主要几何形 状 三角剖分与拓扑重建是一对密切相关的概念 一方面 拓扑重建技术往往 要用到三角剖分技术 另一方面 当采用三角形网格时 拓扑重建的结果表现 为曲面三角剖分 目前最广泛流行的三角划分算法是d e l a u n a y 三角划分方法 1 9 3 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 三角剖分使得所形成的每个三角形尽可能接近等边三角 形 三角剖分是因其在有限元分析中的应用而成为热点的 但其早期的研究却 并不完全源于有限元分析的需要 七十年代初 美国加利福尼亚工学院喷气推 进实验l a w s o n 为了绘制二维流场等值线 对平面点集的三角剖分进行了研 究 英国b a t h 大学数学分校的g r e e n 和s i l b s o n 等从纯数学的角度对这一问 题进行了研究1 2 3 1 0 八十年代初 英国b a t h 大学数学分校b o w y e r l 4 1 和澳大利 亚悉尼大学地科系w a t s o n t5 1 对三角剖分算法进行了影响深远的研究 分别构造 了b o w y e r 算法与w a t s o n 算法 从这些文献可以看出 早期的研究者并不都是 研究有限元问题的学者 他们来自不同的领域 所提出的算法也各不相同 但 所得的剖分结果却都是以v o r o n o i 图为理论基础的d e l a u n a y 三角剖分 d e l a u n a y 三角剖分因为具有若干优良的性质 至今仍有学者从事相关的研究 参数曲面造型方法是当今c a d c a m 软件的核心技术之一 从参数域的形 状来看 矩形域和三角域上的参数曲面是两种最为常用参数曲面 矩形域上的参数曲面 自六十年代以来 人们研究和发展了多种雕塑曲面 的造型技术 各种商品化c a d c a m 软件在工业界中的应用有力地推动了雕塑 曲面只益广泛的应用 1 9 6 4 年 f e r g u s o n 6 l 首次应用了参数域上的矢量函数来 表达曲面 并提出了f e r g u s o n 双三次曲面的数学模型 他所采用的曲面参数形 式从此成为曲面数学描述的标准形式 1 9 6 4 年到1 9 7 4 年间 c o o n s 7 l 提出了一 个更具一般性的曲面造型方法 即插值四条给定边界的c o o n s 曲面模型 1 9 7 4 年 b 6 z i e r 首先提出以数学逼近为基础的参数曲面造型方法 并以此为基础开 发了u n i s u r f 自由曲线曲面设计系统 8 1 之后f o r r e s t g o r d o n 等人相继发现 了b 6 z i e r 基函数和b e m s t e i n 基函数的内在联系 从而侵b e z i e r 的造型方法有 了峰实的理论基础 随着c a d 技术和c a g d 研究的进展 在d e b o o r c o x 等 人研究和完善了b 样条基函数的理论之后 g o r d o n 和r i e s e n f i e d 于七十年代中 期将b 样条理论引入了曲面设计系统 从此 b 包i e r 曲面被视为b 样条曲面的 一种特例 b e z i e r 曲面与b 样条曲面的共同特点在于它们都是用多边形网格控 制或逼近曲面 其逼近的程度与基函数的次数有关 b e z i e r 曲面具有装配灵 活 适应性强等优点 而b 样条曲面则具有连续性强 整体配置控制顶点的优 点 同时 由于b e z i e r 曲面的角点通过控制顶点 所以也广泛应用于离散数据 的曲面插值 而b 样条曲面用于离散数据的曲面插值则需反求控制顶点 因而 最常用的是双三次b 样条曲面 因为此时反求控制顶点的方程组可转换成三对 角线方程组 1 9 7 5 年 在r i e s e n f e l d 工作的基础上 v e r s p r i l l e 在他的博士论文 中首次提出了有理b 样条 即n u r b s 模型 此后 由于p i g e l 和t i l l e r 等人的 贡献 n u r b s 成为c a g d 中最为流行的技术 b 6 z i e r 有理b 6 z i e r b 样条 均匀有理b 样条等都被统一到n u r b s 中来 n u r b s 不仅可表示自由曲面 而且还能表示球面等规则曲面 为c a g d 提供了统一的数学描述方法 1 9 9 1 后 国际标准化组织 1 s o 颁布的工业产品数据交换标准s t e p 中 把n u r b s 作为定义工业产品几何形状的唯一方法 从而成为产品外形描述的工业标准 三角域上的参数曲面 参数域为三角形的曲面称为三角曲面 其造型方法 最早在五十年代由d e c a s t e l j a u 开始研究 并导出了三角域上b 6 z i e r 曲面的表 达形式 但这一成果直到1 9 7 5 年 才由b o e h m 在c i t r o e n 公司的一份报告中 发现 另一学者s a b i n 于1 9 7 7 年开始独立地研究了这一问题 得到了与d e c a s t e l j a u 相同的结果 后来的十余年里 f a r i n 系统地研究了三角曲面的性 质 递推算法 偏导数计算以及曲面间的连续拼接问题 9 a o 后来的学者也曾 研究过三角域上的样条曲面 但由于这种曲面对控制顶点的分布要求太过严 格 所以应用远不广泛 而三角域上的b 6 z i e r 曲面则由于其装配的灵活性 在 插值曲面的几何重建问题上受到普遍重视 1 9 8 3 年 f a r m t 9 i 通过三角形的 c l o t i g h t o c h e r 分割算法 简称c t 算法 构造了整体g 1 连续曲面 1 9 8 6 年 w h e l a n i 研究了三角形的c 2 连续插值问题 1 9 9 2 年 柯映林 1 在他的博士论 文中提出了一种准c 1 连续三角b 6 z i e r 曲面插值模型 克服了c t 算法的一些 固有缺陷 并以此为基础提出了构造g 1 连续三角b 6 z i e r 曲面的方法 人们注 意到 三角域b 6 z i e r 曲面在插值离散数据时具有矩形域曲面无可比拟的优越 性 因为这种方法允许完全散乱的数据 而不必是张量积形式的数据 正因如 此 尽管三角域上的b 6 z i e r 曲面在连续拼接时存在一定的困难 但在插值曲面 的几何重建问题上 这一方法还是倍受亲睐 四边曲面与三角曲面的综合应用 1 9 9 4 年 l o o p 1 3 采用了b 6 z i e r 曲面间 的连续拼接技术将三角面片或四边面片拼接在一起实现了曲面的几何重建 1 9 9 7 年 f l o a t e r t l 研究了从四边拓扑曲面三角剖分出发构造b 样条逼近曲面 的方法 其算法可以给出令人满意的光顺曲面 同一年 赵东福 2 2 在他的博士 论文中研究了三角 四边b 6 z i e r 曲面混合造型的方法 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 三角剖分的局部构造算法 并将它推广到曲面点集中去 在曲面重构中从退化条件入手研究新的c t 算法 适合任意拓扑网格几何 重建算法中 f a r i n 的c t 算法是一种很常用的算法 但这种算法在计算控制 顶点时依赖于相关顶点的处理顺序 并需进行控制顶点的初估及修正而不能一 次计算完成 因此 我们设想是否有一种新的c t 算法能够克服f a r m 算法的 缺点 无论是改进f a r i n 的c t 算法还是研究采用n u r b s 曲面数学模型的c t 算法 都会遇到退化问题 对退化条件下相邻曲面问的连续拼接条件的研究将 是解决问题的关键所在 针对散乱数据点集曲面重构算法分析 应用三角b 6 z i e r 曲面进行曲面重构 重点对以下问题进行研究 1 对给定散乱的数据进行三角剖分 并作必要的修改 主要对d e l a u n a y 三角剖分进行研究 解决平面点集d e l a u n a y 三角剖分的局部构造算法 2 在曲面拟合中 将重点研究用三角b 6 z i e r 曲面的基本原理及其拼接中 的参数连接性和几何连续性问题 3 三角b 6 z i e r 曲面的拼接条件 在前人研究结果的基础上达到分段g 连 续 并对算法进行改进 4 四边b 6 z i e r 曲面与三角b 6 z i e r 曲面的拼接条件 由于对四边b 6 z i e r 曲 面已经有很多研究且应用广泛 因此研究三角b 6 z i e r 曲面与四边b 6 z i e r 曲面连 接问题 5 从算法结构入手 研究算法所需要数据结构 针对各个算法实际需要 优化数据结构 给出主要算法的数据结构 堕查堡竺三查兰矍兰堡 兰 篁兰 第2 章平面点集d e l a u n a y 三角剖分的局部构造 2 1d e l a u n a y n 9 与v o r o n o i 图的关系 我们从样点集的构造这个角度 把曲面集 曲面点集与曲面三角剖分联系 起来进行考虑 研究如何在曲面上构造一个所谓 足够好 的曲面点集的问题 定义局部分离样本和全局分离样本 然而 当我们进行曲面拓扑重建时 曲面 集及其拓扑与几何性质都是未知的 我们所面对的仅仅是三维空问中的一个散 乱点集 这就是我们可以用来进行曲面拓扑重建的全部资讯 一般认为 除了 点与点之间的距离之外 欧氏空间中的一个散乱点集似乎不可能隐含着什么明 确的结构 但实际上 在考虑了邻近样点的距离和分布两个因素之后 就可以 得到一个明确的领域结构 关于这个问题 有文献记载的研究可以追朔到一个 半世纪以前 早在1 8 5 0 年 d i r i c h l e t 就研究了平面离散点集的邻域问题 他 将平面想像成一片草地 并在每个离散点处放一只绵羊 那么每只棉羊的领地 f 即邻域 应该是什么样子呢 d i r i c h l e t 的结论是 草地上的草离哪只绵羊最近就应属于哪知绵羊的领 地 如图2 1 所示 每个离散点 填黑的点 的邻域应该是一个凸多边形 凸多 边形的每条边都代表着某两个相邻样点的中垂线 图2 1 被称为v o r o n o i 图 是因为1 9 0 8 年v o r o n o i 研究了相同的问题并将其扩展到了高维空间 l5 j v o r o n o i 的研究结果可描述为 对于n n 1 维欧氏空间中的一个p x l x 2 x m c r 样点x i 或称剖分点 的v o r o n o i 邻域由这一空间中邻近x i 的点组成 邻域中的 点到x i 的距离小于到其它样点的距离 若用数学公式表示 点x i 的v o r o n o i 邻 形 x r l d x x 1 维欧氏空间中的一个点集p 称由p 构造的一个单纯形集合 r 尸1 为关于点集p 的三角剖分 如果t p 是p 的凸包的 个划分且r p 的顶 点集为p 如果r p 中任意 条边的两个端点在y p 中是相邻的 则称t p 是点集p 的一个d e l a u n a y 三角剖分 记为d 尸 这个与v o r o n o i 图相对应的 d e l a u n a y 三角剖分的概念是1 9 3 4 年由俄国数学家d e l a u n a y 提出的 它也被称 作是v p 的对偶图 容易证明 只要点集p 中没有多于n 1 个点共h 维空间中 的n 维球面 则v o r o n o i 图中的每个顶点恰距n 1 个样点等远 并且d p 是唯 一的 否则 d p 将不是唯 的 在这种情况下 可任取一种图2 2d e l 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 图用以显示两者的对偶关系 2 2 1d e l a u n a y 三角剖分的性质 d e l a u n a y 三角剖分具有一些非常重要的性质 其中最为重要的有 1 空外接球准则 对于n n 1 维欧氏空间中给定的点集p d p 中的任一1 1 维单纯形的n 维外接球内没有剖分点 对于平面点集 这一准则称为空外接圆准则 对于三 维点集 则称为空外接球准则 2 局部性 具体表现为 在己有的d 尸 中加入 去除或移动一个顶点后 仅需进行 局部修改即可重新获得d e l a u n a y 三角剖分 图2 3 以平面点集为例 表示了加 入或删除一点所需进行的修改 所有需要进行修改的三角形的并集称为影响 域 可以证明 影响域的各顶点对于加入或删除的点来说都是可见的i 从而 证明影响域是局部的 3 低维单纯形的存在条件 d e l a u n a y 三角剖分的这一性质可以描述为 n m n m 1 1 维单纯形在 d e l a u n a y 三角剖分中出现的充分条件是这个单纯形具有月一m 维 真 空外接 球 这一重要性质是由浙江大学工程图学所徐永安在其博士论文中给出的 l 所谓 真 空外接球 是指不仅其内没有剖分点 其上也仅有此低维单纯形的顶 点 而无其它剖分点 需要指出的是 在徐永安的论文里并没有这个 真 字 但为与一般空外接球的含义有所区别 本文加上了这个字 对二维与三维空 堕查堡些三当兰矍兰堡 兰竺篁三 间 这 性质表现为 对于平面点集p 而言 只要两点连线具有真空外接圆 则此两点的连线必将出现在d p 中 对于三维点集p 而言 只要两点连线具有真空外接球 则此两点的连线必 将出现在d 尸 中 同时 只要三点所连三角形具有真空外接球 则此三角形 必将出现在d d 中 图2 3 平面点集d e l a u n a y 剖分中加入或删除一点 f i g u r e2 3a d d o rd e l e t eap o i n ti nd e l a u n a yt r i n g u l a t i o no f p o i n t si np l a n e 4 最小角最大准则 这是平面点集d e l a u n a y 三角剖分区别于高维点集所特有的性质 1 9 7 7 年 s i l b s o n l 3 证明 对于平面点集而言 v o r o n o i 邻域准则 空外接圆准则和最 小角最大准这三者是等价的 并且符合这三个准则的三角剖分只有一个 即 d e l a u n a y 三角剖分 具体地说 对于给定的平面点集p 任何一个三角剖分 t p 总有一个三角形的内角是最小的 而d p 中的这个最小角在所有t p 的 最小角当中是最大的 正是由于这一特性 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 2 2 d e l a u n a y 三角剖分的经典算法 由于d e l a u n a y 三角剖分提出至今己有近7 0 年的历史 其间出现了多种多 样的计算方法 其中较有影响的算法有 i b o w y e r 算法 4 1 哈尔滨理t 大学理学硕 一学位论文 该算法由英国b a t h 大学数学分校的b o w y e r 于1 9 8 1 年提出 b o w e r 算法 首先构造所给点集的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 图的构造是从一个由n 1 个 剖分点构成的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 图 该算法 在n 维空间中的效率为o n 厶 是一个效率较低的算法 2 w a s t o n 算法 5 1 该算法是澳大利亚悉尼大学地科系w a s t o n 于1 9 8 1 年提出的 它是应用计 算机构造晶体模型的研究成果 w a s t o n 算法采用空外接圆准则 直接从三角剖 分入手 其主要思想是 从一个单纯形出发 每次加入一个样点后 找出所有 外接球包含此点的单纯形 并予以删除 得到一个包含此点的空洞 将新点与 空洞各项点相连就构成了加入新点后的d e l a u n a y 三角剖分 当所有剖分点全 部加完时 所给点集的d e l a u n a y 三角剖分即告完成 w a s t o n 算法的特点是 思路明确 易于编程实现 其主要不足是计算复杂度较大 w a s t o n 本人虽然没 有分析其算法的时效 但j o e 9 i 的研究指出 其复杂度将高于b o w y e r 算法 令塞今令舌今 b 图2 4 平面四点的三种构型及两种变换 f i g u r e2 4t h r e es t r u c t u r e sa n dt w ot r a n s f o r m a t i o n so f f o u rp o i n t si np l a n e 3 l a w s o n 算法 1 9 7 7 年 美国加利福尼亚工学院l a w s o n 提出了基于边交换的二维 d e l a u n a y 三角剖分算法 l a w s o n 算法是以二维空间中四点的三种构型及构型 问的两种变换为基础的 如图2 4 所示 这三种构型分别是 a 构成一个三角 形 第四点在一条边上 b 构成一个凸四边形 又可分为两种三角剖分 c 构 成一个三角形 第四点在其内部 两种变换 指的就是b 1 中两种构型之间的相 互转换 l a w s o n 算法从一个非优化的三角剖分出发 对其中每一条边的两个 哈尔滨理1 大学理学硕j 学位论文 相邻三角形进行空外接圆检查 若不满足 则交换这条对角线 由于交换后一 定满足空外接圆准则 所以l a w s o n 算法最终可以构造d e l a u n a y 三角剖分 4 闵卫东算法i i o j 清华大学计算机科学与技术系c a d 中心闵卫东和唐泽圣对二维域内点集 的d e l a u n a y 三角剖分问题进行了比较深入和系统的研究 提出了d t a d 的生 成算法 该算法首先生成给定域的三角剖分 然后采用生成核插入算法逐个插 入域内的剖分点 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 三角剖分局部性的算法 具体地说 对于任意给定的一个散乱的平面点集p 关于此点集的d e l a u n a y 三角剖分d 尸 以及相应的v o r o n o i 图为矿 j p 如果只 想获知d p 中一点周围的三角形是哪些 或者说该点在矿 p 中的邻近点是哪 些 是否可从该点及其附近的样点中直接构造 而无需对d p 进行完全构造 另一个与之相关问题是 如果这样的方法存在 是否可以用来逐点地构造 d p 这就是本节所要讨论的问题 2 3 1 构造任意点处的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 三角形 为了构造平面点集p 中任意点x 处的一个d e l a u n a y 三角剖分d j 1 我们 采用了一种递推的算法 称为算法2 1 算法的基本思想是 从点x 与其最近 点所连的边开始 找出过这条边的d e l a u n a y 三角形 再从这个三角形中过点x 的新边开始找出下一个与之相邻的d e l a u n a y 三角形 如此递推 直到再次回 到第一个三角形 表示点x 为一内点 或者到达凸包的边界 也就是此边的外 堕尘堡竺三奎兰矍兰竺 兰堡篁兰 侧没有待剖分点 表示x 为凸包的边界点 这时再从反方向递推地找到另一条 凸包边界 算法描述如下 算法2 1 s t e p l 从p 中找出点x 的最近点口得边x a 令a 为a f l a g 为0 s t e p 2 从p 中找出对边x a 张角最大的点b 得三角形x a b 并令曰为b s t e p 3 检查三角形x a b 关于边如的外侧是否有p 中的点 如果有 从中找出对边曲张角最大的点c 得三角形x a c 转s t e p 4 如果没有 将f l a g 加1 转s t e p 5 s t e p 4 如果c 等于一 则转s t e p 6 否则 令a 为b b 为c 转s t e p 3 s t e p 5 如果f l a g 等于2 转s t e p 6 否则 令a 为曰 令b 为a 转s t e p 3 s t e p 6 结束 如图2 6 所示 在s t e p1 中 以x a 为直径的圆必为真空外接圆 因此x a 必出现在d x 中 下面的定理2 1 将证明在s t e p 2 中找出的三角形x a b 是一个 d e l a u n a y 三角形 而定理2 2 将证明在s t e p 3 中找到的三角形x a c 也是一个 d e l a u n a y 三角彤 就这样递推地找出点z 处所有相邻的d e l a u n a y 三角形 每次 寻找的依据都是张角最大 如果这个过程可以继续下去 则下面的定理2 3 将 证明这样递推下去一定可以封闭回去即再次找到最近点 从而完成点x 处的一 个d e l a u n a y 三角剖分 如果在递推过程中发现某三角形外侧没有任何样点 则说明点x 是点集p 凸包上的一个边晃点 而当前三角形是一个边界三角形 此时 可从三角形x a b 关于边x q 的外侧出发 递推地找到另一个边界三角形 b b c c 图2 6 算法2 i 的示意图 f i g u r e2 6d i a g r a mo f a l g o r i t h m2 1 左图为凸包内点 右图为凸包边界点 x 哈尔演理t 大学理学硕十学位论文 定理2 1 设p 是任意给定的平面点集 x 是其中任意一个样点 a 为x 的 最近样点 之一 b 是到边加的张角最大的样点 之一 则三角形x a b 是 d e l a u n a y 三角形 证明如图2 7 所示 用反证法 设三角形x a b 不是d e l a u n a y 三角形 则 三角形x a b 的外接圆内至少存在另外一个样点y 由于a 为x 的最近样点 之 一1 因此点y 不会在以a x 为直径的圆之内 这样 点y 只能在图中月牙形的 阴影区域内 从而与点b 位于弦埘的同侧 因此 点y 对边x a 的张角比点b 大 这与b 是对边x a 的张角最大的样点f 之一 相矛盾 证毕 定理2 2 设p 是任意给定的平面点集 三角形x a b 是d e l a u n a y 三角形 点 c 是位于三角形x a b 关于边曲的外侧且对边曲的张角最大的样点 之一 则三 角形x b c 是d e l a u n a y 三角形 证明如图2 8 所示 用反证法 假定三角形x b c 不是d e l a u n a y 三角形 则三角形x b c 的外接圆内至少有一个样点y 由于三角形x a b 是d e l a u n a y 三角 形 所以其外接圆内没有样点 这样 点y 只能在图中月牙形的阴影区域内 因此与点c 位于弦x 6 的 一侧 由此可知 点y 对边曲的张角大于点b 对边柏 的张角 这与点c 是此侧对边z 6 的张角最大的样点 之一 相矛盾 证毕 b 幽2 7 定理2 1 证明用图 f i g u r e2 7d i a g r a mo f t h e o r e m 2 1 图2 8 定理2 2 证明用圈 f i g u r e2 8d i a g r a mo f t h e o r e m2 2 定理2 3 设p 是任意给定的平面点集 则算法2 1 必能找到其中任意点处 的一个d e l a u n a y 三角剖分 证明如图2 9 所示 假定点x 是点集p 凸包的一个内点 则由定理2 1 及 定理2 2 可知算法2 1 一定可以进行下去 随着所选三角形数目的增加 这些 三角形所扫过的角度 即以点x 为顶点的各个内角之和 将逐渐增大 设点a 为