（计算数学专业论文）nurbs曲面间的最短距离.pdf

南京航空航天大学硕士学位论文 摘要 本文从不同的分析角度，分别就凸曲面和一般曲面展开研究，给出了n u r b s 曲面间距离求解的几种算法，解决了最为复杂的两参数曲面间的最短距离求解问题。 首先，基于分析两张参数曲面间达最短距离所必须满足的几何约束条件及各种 可能出现的边界情况处理，结合n e w t o n - r a p h s o n 迭代法，提出了距离求解精化的一 种方法。 然后，针对凸曲面的几何特征，给出了n u r b s 凸曲面间距离求解的公垂线法 和切平面法。( 公垂线法是把曲面间的距离求解问题转化成曲面的离散点生成的凸壳 间的距离，再归之为两凸壳在其公垂线上投影集合间的距离，由此抽象成一个线性 规划问题，估算出近点对。切平面法是运用g j i z 和l c 构造支撑映射的原理而设计 的一个搜索近点对的迭代法，着重给出了迷向情况的处理和初始迭代点的选取方法， 并证明了只要将初始迭代点取为阳点，就不会出现迷向情况。卜，一万 最后，探讨了n u r b s 曲面的分裂技术与控制网的收敛性问题，充分利用n u r b s 曲面的凸包性和距离值上下边界分类的思想，避免大量不必要的细分，提出了一般 n u r b s 曲面间最短距离求解的分裂算法。 均验法实 算 。 上较以一比厂一和耖 n u r b s 曲面间的晟短距离 a b s t r a c t t h i st h e s i s ，f r o md i f f e r e n ta n a l y t i c a lp o i n t so f v i e w , p r o p o s e s t h r e ea l g o r i t h m sf o rt h e m i n i m u md i s t a n c e sb e t w e e nc o n v e xn u r b ss u r f a c e s a n dg e n e r a ln u r b ss u r f a c e s r e s p e c t i v e l y f i r s t l y , b a s e du p o na n a l y z i n gt h eg e o m e t r i cc o n s t r a i n tc o n d i t i o no ft h en e a r e s tp o i n t s ， am e t h o di s g i v e nt o r e f m et h e a p p r o x i m a t e dd i s t a n c eb e t w e e nt w os u r f a c e st h r o u g h n e w t o n - r a p h s o n i t e r a t i o n a tt h es a m et i m e s t h ee a s e so f b o u n d a r i e sa r ea l lc o n s i d e r e di n d e t a i l s e c o n d l y , a c c o r d i n gt oc o n v e xg e o m e t r i cc h a r a c t e r i s t i c s ，ac o m m o n p e r p e n d i c u l a r - l i n ea l g o r i t h mi s d e v e l o p e df o rt h ed i s t a n c eb e t w e e nt h ec o n v e xn u r b ss u r f a c e sb y m a k i n gs u r f a c e sd i s c r e t e ，a p p r o x i m a t i n gt h ed i s t a n c eb yo n eb e t w e e nc o n v e xh u l l so f d i s c r e t es u r f a c e sa n d s o l v i n gal i n e a rp r o g r a m m i n gp r o b l e m t og e tt h e i rv e r t i c a lp r o j e c f i v e l e n g t ho nc o n l n l o np e r p e n d i c u l a rd i r e c t i o 玛t h a ti s ，t h eo r i g i i l a id i s t a n c e t h i r d l y , f r o mt h ei d e ao f l o c a l l yl i n e a ra p p r o x i m a t e ，a n o t h e rt a n g e n t - p l a n ea l g o r i t h m i sp r e s e n t e df o rt h ed i s t a n c eb e t w e e nt h ec o n v e xn u r b s s u r f a c e s t h ec d t i c a ls t e pi st h e c o n s t r u c t i o no ft h es u p p o r tm a p p i n gb yg j ka n dl ct os e a r c hf o rn e a r e s tp o i n t s ，a n d e m p h a s e sa r el a i do nd e a l i n gw i t hi s o t r o p i cc a s e sa n dc h o o s i n gi n i t i a li t e r a t e dp o i n t s i ti s a l s op r o v e dt h a tn o i s o t r o p i s md u r i n gi t e r a t i o nw o u l d t a k ep l a c ei fi n i t i a li t e r a t e dp o i n t sa r e p o s i t i v ep o i n t s f i n a i l y as p l i ta l g o r i t h mi sp u tf o r w a r dt oc a l c u l a t et h em i n i n l u l nd i s t a n c eb e t w e e n t w o g e n e r a ln u r b ss u r f a c e s ，i nw h i c h t h et e c h n i q u eo f s p l i t t i n gt h en u r b s s u r f a c e sa n d t h ec o n v e r g e n c eo fc o n t r o lp o i n t sa r eu s e d , a n ds p a t i a lc l a s s i f i c a t i o nu s i n gt h eu p p e r & l o w e rb o u n da n dt h ec o n v e xh u l lp r o p e r t yo ft h en u r b s s u i f s p 世sa r ea p p l i e dt oa v o i d u n n e c e s s a r ys u b d i v i s i o n s t h e p r o g r a m s o ft h ea b o v e a l g o r i t h m sa r ed e v e l o p e d i t i ss h o w e dt h a tt h e a l g o f i t h r a s a r er o b u s ta n de f f i c i e n tb y c o m p u t a t i o no f m a n ye x a m p l e s , a n da n a l y s e sa n dc o m p a r i s o no f t h ee x p e r i m e n t a l r e s u l t s f i g u r e sa n d t a b l e sa r ca l s oa t e l l i n gs t o r y k e y w o r d s ：m i n i m u md i s t a n c en u r b ss u r f a c e s c o n v e x i t y l i n e a r - p r o g r a m m i n gs u p p o r t - m a p p i n g u p p e rb o u n d l o w e rb o u n d s p l i to f n u r b s s u r f a c e 南京航空航大大学硕士学位论文 第一章引言 1 1 距离求解问题的发展及现状 距离求解问题是机器人技术、计算机仿真、工业设计等方面遇到的一个关键问 题。如机器人无碰运动路径规划m i 、实时碰撞检测1 9 1 2 0 i 、实时路径修j 下、几何布局 工作的计算机辅助设计都要涉及到物体间的距离计算和判断两个物体之l e 】是否发生 碰撞。 在某些情形下，距离求解问题是容易解决的，如点到平面的距离，球面间的距 离等，但一旦将平面变成四边形，问题就变得复杂了许多。所以多边形、多面体及 参数曲面的距离求解问题一直以来是计算几何等有关领域的研究热点。经过数学和 计算机应用领域许多学者的长期共同努力，已研究发展了一些有效算法，使这一复 杂而又困难的问题取得了长足的进展。 文献 4 5 】采用优化手段探讨了凸多边形之间的距离问题。文献【7 】用四元数表示 法讨论了一个移动目标与静止障碍物的碰撞检测问题，针对不同的碰撞类型进行了 分析，提出了路径规划算法。g i l b e r t 、d o h n s o n & k e e r t h i ( g j k ) 和l i n & c a n n y ( l c ) “ ”分别于1 9 8 8 ，1 9 9 1 年提出了凸多面体之间距离的两个富有代表性的算法。q h i n l a n f 6 1 于1 9 9 5 年利用边界分类的思想研究了非凸多面体之间的距离求解问题。近年来，文 献【1 0 1 l 】给出了凸多面体之间沿给定方向的距离的算法，但实现该算法需要存储许 多预先做好的辅助信息。由此可见，距离问题的研究发展到今天，绝大多数工作仍 集中于多边形或多面体，尤其是凸多边形和凸多面体。这主要基于以下原因： ( 1 1 与一般的几何模型相比，多面体模型处理起来比较容易。而且，在很多情 形下，以多面体模型代替原有物体从精度上来说就足够了； ( 2 1 把研究的物体限制为凸体更容易得到问题的快速算法。 虽然多面体之间的距离算法在许多应用领域起着非常重要的作用，但是，在实 践中，以自由型曲面作为表面的物体是极为常见的，涡轮叶片、船的外壳、汽车外 壳和飞机的机身就是很好的例子。现在的许多造型系统都直接采用自由型曲线、曲 面模型。特别n u r b s 方法在形状定义方面的强大功能和潜力，几乎所有的自由型曲 线、曲面都可以采用n u r b s 方式来定义。1 9 9 1 年国际标准组织( z 阳) 颁布的工业 产品几何定义的s t e p 标准，就把n u r b s 作为唯一定义自由型曲线、曲面的数学方 法。近年来，许多c h d 商用软件纷纷开发或推出了n u r b s 功能。因此，探讨咄 曲线、曲面间的距离无疑是非常重要的。目前，有关自由型曲面的距离研究能见到 的文献很少，文献【l9 】给出了有理b 6 z i e r 曲面之间有向距离( 不是两个集合间的一般 距离1 的算法，并在文中指出在他之前还不曾有这方面的研究成果。此算法以b 6 z i e r n u r b s 曲面间的最短距离 曲面的分裂性质为基础，以距离最近点处的法矢量共线、反向这一几何特征为依据， 估算出曲面之间距离最近的一对点后，再用n e w t o n - r a p h s o n 迭代解方程组提高解的 精度。由于n e w t o n r a p h s o n 迭代的收敛性仅在曲面为凸的情况下才能得到保证，这 就大大限制了算法的适用性；此外，从理论上讲，n u r b s 曲面可转化为有理b 6 z i e r 曲面1 ，则此算法可推广到n u r b s 曲面距离求解上，但事实上，这是一个相对繁琐 的过程，用于求距离根本不可能实现。针对这一现状，本文提出从以下两个方面来 探讨n u r b s 曲面之间的距离问题： ( 1 ) 利用凸曲面的几何特征给出n u r b s 凸曲线、曲面间的距离算法； ( 2 ) 运用n u r b s 曲线、曲面自身的几何性质给出其距离算法。 本文根据n u r b s 曲面的形状和曲面问的相对位置，将n u r b s 曲面间的距离问 题分为两类进行讨论：第一类是本文第三章定义的相对凸情形下的v 咄曲面问的 距离求解问题，第二类是一般形状和任意位置下的| v 砌s 曲面间的距离求解问题。 对于第一类问题，本文给出了两个算法：公垂线法和切平面法。公垂线法的基 本思想是将曲面离散成一系列的点，以两个点集的凸壳之间的距离近似地代替曲面 之间的距离。而凸壳之间的距离归之为其在公垂线上投影集合间的距离。这一算法 充分地利用了曲面的凸性和凸多面体的性质，将距离求解问题转化为一个线性规划 问题。在求解的过程中，不需要用很复杂的数据结构，只需记录点的信息，也不需 要关心曲面的形状和具体的表达方式。在求解线性规划问题时，采用应用广泛的单 纯形法，这充分保证了算法可靠性和快速性。显然。用凸壳代替曲面，计算结果无 论如何是一种近似。但估算出曲面距离最近点后，可采用n e w f o n r a p h s o n 迭代解方 程组( 2 一1 ) 来精化解。切平面法以曲面的切平面和曲面自身的联系为基础运用g j k 和l c 算法的基本原理，不断改变所考察的点，使它们之间的距离逐渐减小，以至 于最后得到一对距离最近的点。切平面法利用了投影的手段和曲面的凸性，计算量 小，简单直观。如果仅是为了求解凸n u r b s 曲面之间的距离，这里的两个算法比文 献【1 9 】运算量小得多，这是因为文献【1 9 在对b 6 z i e r 曲面进行分裂时，根本就没有考 虑曲面凸性这一重要的几何性质。 对于第二类问题，本文给出的分裂算法采用了距离值边界分类的思想，充分利 用n u r b s 曲面自身的几何性质来分裂曲面，对每一子曲面片构造一个r a i n 矾戢包围 盒，包围盒之间的距离就是其内部子曲面片间距离值的下边界。同时每一次分裂 曲面片以后，都可以根据新的子曲面片的角点信息更新距离值的上边界由上边界 值和下边界值，就可以排除大量不必要继续分裂和检测的子曲面片，大大减小计算 量。利用n u r b s 曲面分裂中控制网对曲面的收敛性，当曲面分裂到一定程度时，就 可以用控制网点进行点点比较得到曲面之间距离的最近点。 本文共分七章论述：第一章是引言，介绍了距离求解问题的现状及背景知识： 第二章主要论述n e w t o n r a p h s o n 迭代求解距离的方法，特别分析处理了各种可能出 现的边界情况，指出了这一算法在距离求解问题中的作用：第三章、第四章分别从 南京航空航天大学硕十学位论文 离散投影和局部线性近似的角度给出了相对凸的n u r b s 曲面问的距离求解算法；第 _ 丘章根据n u r b s 曲面自身的几何性质，给出了一般l ，r 日s 曲面阳j 的距离求解算法： 第六章给出各种算法的算例、图形绘制，进行计算结果分析和算法比较。最后一章 是总结和展望。本文着重探讨n u r b s 曲面之间的距离计算问题，但这些算法对曲线 的隋形也适用。此外，因为n u r b s 曲线曲面将圆锥曲线、初等解析曲面和b 6 z i e r 、 有理b 6 z i e r 、占样条曲线曲面统一在它的表达式中，所以本文的算法对其它自由型 曲线曲面电适用。 1 2 背景知识 1 2 1 基本术语的约定 本文所探讨的曲面都是包含边界的，即曲面上所有的点形成空间中的闭集，从 而曲面( 或曲线) 之间的最短距离d 可表示为： d = i n 删p 一训1 p l ，孑z 2 - 其中t ，z 是闭集 由于本文探讨的仅是距离问题，因此文中出现的范数卜0 都是指欧氏范数。可咀证 明：两个不相交的闭集，：上至少存在一对点风，玩满足条件： 慨一删= 蚵怕_ 训哥1 ，虿z 2 ( + ) 事实上，任取辱：，d o ：i n f 一剖1 p 。易知舻o ，且有 p + ) c 使得 忙一硎斗d 。，于是， 声 有收敛子列。不妨令矿斗蟊，则 l 悖一芦，l i = i n f l l q p 芦， 。 显然，d = i n f 0 孑一芦| | i 牙：，芦) = i n f l l q 声。l i i 虿e z ：，p 。ez ) ， 于是有，点列 牙 c ：，使得忙一芦矿l d 。因此，啊+ ) 具有收敛子列，不妨设 香一q o ，则4 玩一芦知i l = d 。又由：是闭集知磊z ：，记风= 声而，有： i i 芦。一q o4 = i n f ( 1 卢一彳0 l j 。，彳芑：) ，芦。z 1 , q oe ： 由此，本文约定：凡满足条件( ) 的风，q o 称为，2 之间的一个近点对， p o ，磊的连线称为z 。e 2 之间的公垂线，p o q 。，q o p 。都称为。z 2 之间的公垂线方 向。 n u r b s 曲面间的最短距离 1 2 2g j k 算法和l c 算法的基本原理 g j k 算法和l c 算法是计算凸多面体之间距离的两个富有代表性的算法，这两 个算法的基本原理对凸曲面之间距离求解问题的解决具有重要的借鉴作用。现对这 两个算法的基本原理作简要介绍。 g j k 算法和l c 算法都需要检验所考察的一对点是否是物体间的近点对，这两个算 法的实施过程都是不断改变所考察的点，使 其问的距离不断下降的过程。如图l 所示， a 、b 是两个凸体厅i 是物体a 、b 上的 b 、两点，那么检测占，b 是否为a 、b 之间 c 、近点对的原理如下： ( 1 )定义一个支撑函数h ： h x ( 刁) = 唧掣j 。矛 c 卜0 0 图1 - 1g j k 算法和l c 算法的原理 这里，x 是个点集，厅是个方向，是数量积的运算符。 ( 2 ) 取= 占一面，g t , 云是物体a 、b 间的一个近点对当且仅当 h 。( ) = 五ah n ( 一) = 云( ) ( 1 - 2 ) 利用凸体的性质还可以构造如下支撑映射：给定一个方向牙后，就返回z 中的 一个点j 。( 开) 满足条件：h ，( 厅j = s ，( 开) 厅。支撑映射s 。的构造是g j k 算法和l c 算 法的关键部分。对于凸多面体来说，支撑映射s 。能按如下方式返回多面体中的一个 顶点： s t e p 给定一个方向开和一个当前顶点i 计算i 厅； s t e p 2 对i 的每一个邻近顶点t ，计算e 开 矿对某个i ，有f 牙 f 帝 t h e n 以i ，代替帚，转s t e p i e l s e 转s t e p 3 ： s t e p 3 输h 5 i 、i 就是所求的解。 本文求解凸曲面之间距离的公垂线法和切平面法就是根据这里的求解思想而建 构的。 4 南京航空航天大学硕士学位论文 1 2 3 n u r b s 曲面简介 n u r b s 曲面的表达式定义为： 0 9 。互一n + ( “) | v ( v ) p ( u ，y ) = 号# - 一( 1 - 3 ) 酚，j 。( “) 川( v ) j = o3 = 0 这里的控制顶点d 。，i = 0 ，1 ，m ；j = 0 , 1 ，”；拓扑矩阵形列，形成一个控制网 格，6 9 是与控制顶点一，相联系的权因子，规定。，0 3 椰c o 6 0 。 0 ，其余 ( 1 9 0 。n ， ( h ) f - 0 1 ，m 和，( v ) ，j = 0 ，l ，h 分别是”向k 次和v 向和f 次 的规范b 样条基，它们分别由“向和p 向的节点矢量： u = 阻o ，l ，“，“，“+ 】与v = 【v o ，”- ，”- ，v ，v “+ i 】按出一 b o o r 递推公式决定。本文还约定：【，向矢量和y 向矢量中端节点的重复度分别取为 n l 和，+ l 以便使n u r b s 曲面的端节点具有与同次有理b e z i e r 曲面相同的角点几何 性质。 对于上述n u r b s 曲面，本文用到了它的齐次坐标表示形式： f o ( u ，v ) = h p ( u v ) = 日 西。协) m ，( v ) ) ( 1 - 4 ) j ；0 ，= 0 其中，巨，= 陋，。孑。，q ，】称为控制项点z ，的带权控制顶点或齐次坐标。日f ) 表 示中心投影变换，投影中心取为齐次坐标原点。 采用齐次坐标表示以后，张量积丑样条曲面的许多算法，如本文中常用的如一 b o o r 算法、插入节点算法都可以推广到n u r b s 曲面。值得注意的是，非有理b 样 条曲面求偏导的计算不能推广到n u r b s 曲面。n u r b s 曲面求偏导的计算见文献 2 8 和张量积b 样条曲面一样，n u r b s 曲面也是分片连续的。在每一曲面片 芦0 ，v ) ，v ) | “，a t + 1 】x 【v ，v + i 】内是无限次可微的，沿向在重复度为r 的“节 点处是p 。次可微的，沿v 向在重复度为，的v 节点处是d 4 次可微的。因此求偏导 时，如整张n u r b s 曲面达不到相应的连续阶，那在边界线处就必须区分边界线的左、 右两个偏导数。 n u r b s 曲面间的最短距离 第二章最短距离求解中的迭代法 早在1 9 8 5 年，m o r t e n s o n 在他所著的g e o m e t r i cm o d e l i n g _ f ”i - - 书中就提到了用 n e w t o n r a p h s o n 迭代法解下列方程组( 2 1 ) 来搜索自由型曲面之间距离最近的点。 但方程组( 2 1 ) 只是距离最近点满足的一个必要条件，以及n e w t o n r a p h s o n 迭代法 固有缺点，远远不能解决自由型曲线、曲面间距离问题。与所有不动点迭代法一 样，应用n e w t o n r a p h s o n 迭代法求距离之前，首先要提供最近点的初始估计值， 初值选择不当有可能导致迭代不收敛。但一旦初值选择的比较合理，迭代收敛速 度快，精度高。这个初值必须由其它求距离方法得到，所以n e w t o n r a p h s o n 迭代 法不能构成一个独立的求距离方法，但可作为求距离精化的一种有效手段。方程( 2 1 ) 没有包含边界的情况，当考虑边界情况时，其间的距离计算更为复杂。本章对距 离最近点可能出现的各种情况作了分析，尤其是边界情况的处理，在此基础上结 合d e b o o r 递推算法，给出了求n u r b s 曲面间距离最近的点的n e w t o n r a p h s o n 迭 代方法及其程序设计。当用其它方法估算出近点对芦，百大致位置后，可以采用该 方法快速获得精确的近点对。 2 1参数曲面间的近点对满足的必要条件 设声( “，v ) ，辱( s ，r ) ，其中“，v ，s ，f 【0 ，1 】是两张参数曲面片，p ，辱是这两张参 数曲面片的一个近点对，则当卢，i 分别落在二曲面片内部时，它满足如下方程： ( 卢一毒) 声。= 0 ( p 一辱) 卢r ( 2 - 1 ) ( 西一百) 玩= 0 ( 多一孑) 玩= 0 即这两点的连线与这两张曲面在该点的切平面垂直。当西，厅两点中有一点( 或两 点都) 落在所属曲面的边界线或角点处，此时卢，孑就不会再满足方程( 2 1 ) ，如芦 点落在曲面片p ( “，v ) 的边界线p ( o ，v ) 内部( 即不会位于该曲线的二端点处) ，面落 在在曲面片面( s ，) 的内部时，芦，7 就满足方程 南京航空航天大学硕士学位论文 l ( 置一辱) 卢，( o ，v ) = o ( 芦一孑) 面，( s ，) = o ( 2 - 2 ) 1 ( p 一彳) 辱，( j ，t ) = 0 象这样p ，i 中至少有一点不落在所属曲面片内部的情况，本文称( 曲面片之间近 点对的) 边界情况。可将他们分为如下五类：( 1 ) 边面，即声，孑中有一点所属曲 面在边界线上，另一点在所属曲面的内部；( 2 ) 点面即卢，百中有一点是一个曲 面片的角点，而另一点在一个曲面片内部：( 3 ) 边边：( 4 ) 点边；( 5 ) 点点。编 制程序进行迭代求解时，必须对这五类情况作出不同的处理。进一步地，上述五 类情况又可以分为若干种如第( 1 ) 类曲面片p ( “，v ) ，牙( j ，t ) 各有四条边界线， 因此，这一类情况共有8 种。这样所有的边界情况共有8 0 种，它和西，香都落在各 自曲面片内部的情况加在一起，就可知近点对声，百的位置情况共有8 1 种，它们是 近点对的搜索程序所必须考察的。曲线之间近点对的搜索与曲面类似，不再讨论。 2 2n e w t o n - r a p h s o n 迭代搜索n u r b s 曲面问的近点对 由于n e w t o n - r a p h s o n 迭代法求解非线性方程组的理论和基本算法都已相当完 善，因此，对这些内容本文不再赘述，下面仅给出结合d e - b o o r 算法搜索曲面片之 间近点对的n e w t o n e a p h s o n 迭代法及程序。 2 2 1 迭代求解的具体方法 设曲面片声( “，v ) ，百( s ，r ) ( 其中“，v ，s ，f 0 ，1 ) 之间所估算出的近点对风，磊 所对应的参数分别是( “。，v o ) ，( s o ，t 。) 这两组参数组成的向量( f 0 ) x 咒x ；o ) x j ) 就 是迭代过程中的初始迭代值。占是一个很小的正数，表示精度h 是搜索步长。为 了叙述的方便，将上一节的非线性方程组( 2 1 ) 简记为： j z ( x l ，x 2 ，岛，) = 0 f五2f(xx1，,xx：2，,x3,xx。4)：=0x( 2 1 ，) 3 , 0工( x i ，x 2 ，x 4 ) = 、 【工( x l ，x 2 ，x j ，x 4 ) = 0 程序一： 输入；确定两张n u r b , 7 曲面的所有信息及初始迭代值( x “，x ：o ) ，x p ，x ( o ) 7 n u r b s 曲面间的最短距离 输出：最短距离d ，近点对扁，吼及其所对应的参数值 将数组武，磊中的值赋初值0 8 将d 的值置为0 用d e b o o r 算法推得芦( x ：“，x ? ) ，g ( 工 ”，x ：) 及相应的芦。，p ，i ，虿 计算残量p j 吣= 厂( x ”，x 罗，x ，x p ) ( 其中i = 1 ，2 ，3 ，4 ) w h i l p ( m a x e 州 s ) f 每一个x ，+ 都在 o ，1 】内 ( 其中，= 1 ，2 ，3 ，4 ) ( 1 ) 构造四个点( x f “，4 0 + h ，x ：o ) ，= 1 ，2 ，3 ，4 ( 2 ) 用d e b o 。r 算法推得于( x ；一，x 2 1 ，厅( z ，z 1 ) 及相应的 p 。，p ，q ，q ( 3 ) 计算残量8 j = ，( x 卜，x 一，x 3 。, * ：山，i = 1 ，2 ，3 ，4 _ ，= 1 ，2 ，3 ，4 ( 4 ) 解方程e 1 z ，= e p ( 5 ) 替换z j 仉：x j o = x ；们一h z ，a ，其中a = 1 一 ( 6 ) 矿每一个x j o 都在【o ，i 】内 用d e b o o r 算法推得p ( x p ，x ? ) ，辱( x p ，x ：o ) 及相应的 p 。，p ，q 。，q 计算残量p j = l ( x l ”，z ，z 5 “，工? ) ( 其中i = i ，2 ，3 ，4 ) 簧d 的值为1 退出w h i l e 循环 e n d i f 南京航空航天大学硕士学位论文 e l s e 置d 的值为1 退出w h i l e 循环 e n d i f e n d w h i l e 旷d 的值为0 置卢。= 西( x f ”，x ? ) ，亩。= 虿( x ；”，蜉) ，d = l l 多。一o o0 输出d ，氐，孔及( x 0 ) x ( o ) ，x 乳x ：o ) 从上面的程序可以看到，在迭代过程中，每一步的迭代值( 即参数值) 都必 须在【o ，l 】区域内。否则d e b o o r 算法就无法执行。此时，认为近点对不会在曲 面内部取得，程序设计输出距离赤1 ，表示转到边界情况。 2 2 2 边界情况的处理 由2 1 的分析，边界情况共有五类，作者分别就边面、点面、边边和点边问 题编出了相应的迭代程序，它们的输入、输出信息与程序一完全类似限于篇幅， 这里不再赘述。为说明问题起见，下面的程序所考察的边界情况仅从五类边界情 况中各取一种，而在实际问题中每一种边界情况( 共8 0 种) 都要考虑到。为了整 个求解过程的简洁，这里将程序一所处理的情况，即近点对都落在所属曲面内的 情况纳入边界情况一起考察，处理各种情况的子程序分别被称为面面程序、边面 程序、点面程序等，对相关子程序的调用采用匹配的方式。 程序二 输入：确定两张n u r b s 曲面声0 ，v ) 、o ( s ，r ) 的所有信息及初始迭代值o ：”，z ：”，x ；”，x p ) 输出：最短距离d ，近点对赢，孔 置d 的值为1 w h i l e 一( 0 ) f o r i = 1 ：4 i f o l h 9 n u r b s 曲面问的最短距离 0 置x ! o 的值为1 e n d i f e n d f o r i fx ! o 都在( o ，1 ) 内 用面面程序搜索近点对 e l s e i fx o 等r0 ，其它参数都在( o ，1 ) 内 从声( “，v ) 中取出边界线芦( 0 ，v ) 的信息； 以( x ：，x p ，x p ) 为输入参数用边面程序搜索近点对 边面程序的输出参数和x f 0 组成新参数组( x ”，x p ，j ”，x ? ) e t s e i f z f “，x r 等于0 ，其它参数都在( o ，1 ) 内 从p ( “，v ) 中取出角点芦( o ，o ) 的信息 以( x p ，z ：o ) 为输入参数，用点面程序搜索近点对 点面程序的输出参数和x f 0 1 ，工p 组成新参数组 ( x f ，x ；叭，工p ，x ：) e l s e i f x ，x f 等于0 ，其它参数都在( o ，1 ) 内 从p ( u ，v ) 中取出边界线声( 0 ，v ) 的信息 从q ( s ，f ) 中取出边界线q ( o ，) 的信息 以( x r ，t ：o ) 为输入参数，用边边程序搜索近点对 边边程序的输出参数和x f ”，z p 组成新参数组 ( x n x 乳z 扎x 4 ”) e l s p i fx x ，x p 等丁0 x 在( o ，i ) 内 从卢( “，v ) 中取出角点哥( o ，0 ) 的信息 从厅( s ，r ) 中取出边界线每( 0 ，r ) 的信息 南京航空航天大学硕士学位论文 以x p 为输入参数，用点边程序搜索近点对： 点边程序的输出参数和z ( 0 ，x ? 1 x ；0 1 组成新参数组 ( 工 “，x 乳j 弘j 0 ) ： e l s e i f所有的参数值都为0 置口= p ( o ，o ) ，虿。= 彳( o ，o ) ，d = j j a 一孔4 e n d i f e n d w h i l e 输出风，牙。，d 最后，作者要指出的是，虽然n e w t o n r a p h s o n 迭代具有诸多优点，特别是它 快速的收敛性能使它受到了广泛的注意。但是，这种收敛性能只有在曲面，：是 凸曲面的情形下才能得到保证，在，z ：为一般曲面的情况下是没有保证的，情形 最好时也只能获得一个局部最小值1 1 9 1 。因此，按本文第五章的算法虽然可以对 般n u r b s 曲面获得精确近点对的一个很好的近似值，也难以用n e w t o n - r a p h s o n 迭代去提高精度。 n u r b s 曲面间的最短距离 第三章凸n u r b s 曲面间的最短距离( 一) 本章在分析证明了凸多面体和凸曲面的几何性质的基础上，引人相对凸的概念 来描述两个凸曲面之间相对位置，给出了相对凸情形下的n u r b s 曲面间最短距离的 一个求解算法：公垂线法。公垂线法是将曲面离散成一系列的点，以两个点集的凸 壳之间的距离近似代替曲面之间的距离。然后根据( 1 2 ) 式，将两个点集的凸壳之间 的距离转化为其在公垂线上的投影点集之间的距离，再将公垂线方向：i j 求解的问题 抽象为一个线性规划问题。本文采用应用广泛的单纯形法求解此优化问题，得到的 近点对是快速可靠的，可用n e w t o n r a p h s o n 迭代法使解进一步精化。该算法对参数 曲面以及以参数曲面为边界的任何凸几何体也适用。 3 1 两个凸集之间的距离 定义1 设s 是一个非空点集，卢、声：是s 中任意两点，如果点 声= 啊l + ( 1 一f ) 芦2 0 ，l 属于s ，则称s 是凸集。 引理i 设s 是闭凸集，牙g s 则有唯一的一点赢s 与孑的的距离最近。另外， 磊为s 中与牙最近的点的充要条件是：对印s 有( 芦一风) 7 ( 风一百) 0 。 证：设d = i n f 1 牙一别i pe s ) 。显然d o ，且有 芦) s ，使得忙+ 一圳斗d 于是， 芦) 有收敛子列。不妨令声斗死，则怕。一列= d 。y n 为s 是闭集，所以一定有 芦。es ，这说明风为s 中与辱最近的点。设还有卢e s ，使得峪一酬= d 于是有 如 掣i | 2 ：| 眵剐+ 妒们n 扣砒m 勺 ( 辱一卢。) 7 ( 每一p ) = l 旧一声。l 旧一芦| | 这表明厅一风与孑一声线性相关，所以有五使得：厅一声。= 丑( 辱一声) ，且= 1 。显然， 五一1 。这样，五= 】，芦。= 芦。因此，s 中与虿距离最近的点是唯一的。下面证明引 理的后一部分。 2 南京航空航天大学硕士学位论文 设对叩s 有：( 卢一声。) 7 ( 风一牙) 0 。由此，对印s ， f 卢一每f f = l 眵一声。+ 声。一牙f f = i l 卢一p o0 2 + l i 乃。一o l l2 + 2 ( 芦一p o ) 7 ( 卢。一厅) i 卢。一虿0 这说明风为s 中与厅最近的点。反之，设对we s 有怕一剥2 - l l 芦。一驯，于是对 v 丑( o ，】) 有：j j 币+ ( 1 一五) j 。一手旷- 1 1 芦。一辱j | ，即：j j ( p 。一百) + 五( 声一卢。) 02 - 1 1 o 一手胪。 由此可得( 风一百) ( p - 磊) 0 。 群 这里约定，形如h = 多l 矿多= a ) 的集合叫超平面，其中口是纯量，谛0 为h 的法 矢量。超平面确定了两个闭半空间：h + = ( 声1 矿卢口 一= ( p l 帚7 芦口) ； 也确定了两个开半空间：h “= 声i 矿卢 a ) ，日”= p i 谛7 p 口，w 7 p 口。 证：由引理1 ，有唯一的五。e s ，使得：l i o - 死4 = r a i n j 1 0 一圳i j s ，且 ( 风一i ) 7 ( 多一赢) 0 。构造一个过风且以w = 虿一p 。为法向的超平面： h = p i 帚7 p = 茹7 风 ，取口= ( i p o ) 7 赢，可以使得： 茹7 辱= ( i 一哥。) ( i p o ) + 口 口 而且，对s 有：茹7 p = ( 可一p o ) 7 ( 芦一p 。) + a 口。 # 定理1 设赢，吼是两个不相交的闭凸集墨、s 的一个近点对，则必存在分别过 p 一0 砒且垂直于公垂线段p o g o 的平面以，盯：，使得巩，l ：之间( 不含巩，) 没有s 、 品上的点。 证：对玩来说，a 是s 中距民最近的点，由引理2 ，存在平面雹： j i ( 卢一声。) 7 ( i 。一芦。) = 0 ) ，此时对呖s 1 1 n u r b s 曲面间的最短距离 ( 西一芦。) 1 ( 百。一p 。) 0 又 ( 虿。一芦。) 7 ( 牙。一芦。) 0 丌1 的“上侧”( 即磊所在的一侧记为石? + ) 没有s 中的点 同理，存在平面z ： 于i ( i 一风) 7 ( q o 一风) = o ，厅：的“下侧”( p 。所在的一 侧，记为z ：0 + ) 没有s ，中的点。 于是，石? + n 盯2 0 + 内，即平行平面牙，石2 之间没有s is 2 中的点。 舟 定理2 设两个不相交的凸集s ，马的一个近点对是磊，磊，相应的公垂线是1 ， s 1s ：在f 上的投影线段分别是f 即，s ，则线段f 即，s ：间的距离即为s l ，s 2 之间的距离。 证：。赢在，上的投影是它本身，且它是，。的一个端点。若不然，在线段p 。q 。上就 还有异于风的一点贰，它也是s ，中的某一点p 在，上的投影，此时芦一定 位于过蟊且垂直于直线l 的平面石上，由于石亡厅? + n 石：o + ，所以p 疗? + n 口：0 + ，这和定理1 矛盾! 同理，巩也是k 的一个端点。 k ，。：之间的距离为怕。一醌即s i , s ：间的距离。 3 2 两个点集之间的距离 定义2 设s 是一个有限点集，称包含s 的最小闭凸集为s 的凸壳，记为c 矾l s ，该 凸壳的边界记为b c h ( s ) 。 定义3 设p 是一个多面体，如果该多面体的表面由平面凸多边形所围成，且该多 面体每一对相交的面由体内测量的二面角均小于或等于石则称该多面体是凸多面 体。 多面体实际上是指它的表面及由表面所围成的空间，但在本章也将多面体理 解为它的表面，并且，如果不特别指明，对凸壳和凸壳的边界这两个术语不加以区 分。由于点集s 的凸壳c h ( s ) 是包含s 的所有闭凸集的交，或者说，c h ( s ) 是包含s 的所有闭半空间的交，因此空间点集s 的凸壳的边界b c h ( s ) 是一个凸多面体。 南京航空航天大学硕士学位论文 定理3 两个凸多面体鼻，p 2 之间至少有一个近点对卢。，巩，且在只，b 中各有一个顶 点武，芦：，芦。，声：在风，吼所在公垂线，上的投影分别是风，磊。 证：先证明定理的第一部分。显然，凸多面体所围成的空间连同它本身是一个闭凸 集，因此，在e ，b 之间至少存在一个近点对磊，玩。 再证定理的第二部分。易知，两个凸多面体之间的距离只能是以下四种情形之 一： ( a ) 鼻( 或b ) 的某个顶点到含巴( 或只) 的某个面的平面的距离： ( b ) 只( 或尸2 ) 的某个顶点到含最( 或只) 的某条边的直线的距离； ( c ) 鼻的某个顶点到含最的某个顶点的距离； ( d ) 含只( 或最) 的某条边的直线到含p 2 ( 或鼻) 的某条边的直线的距离； 当为情形( d ) 时，j 。，i 。分别落在e 、b 的边a 8 1 ，a 2 皿上，此时， p 。吼上a 。且，p 。吼上a 2 b ：，所以，一，马在，上的投影是风，a 2 , b ：在z 上的投影是 巩。对其它三种情形的证明与之类似。 荐 定义4 两个点集墨，s 2 之间的距离是它们各自的凸壳c h ( s 1 ) 、c h ( s z ) 2 _ n 的距离。 由上述定义，要计算出两个点集s ，s ：之间的距离，只要计算出它们各自的凸壳， 再算出凸壳之间的距离就可以了，但计算它们各自的凸壳是特别繁琐的。这里给出 另一种计算点集s ，s 2 之间的距离的算法。实际上，对于两个凸壳b c h ( s ) 、b c h ( s 2 ) ， 这里所关心的是它们之间的公垂线方向，而与公垂线f 的位置无关。不妨设公垂线， 过某一定点( 如坐标原点) ，其方向为秽，满足忡忙1 这样空间一点芦向f 的投 影位置由实数y = 矿x 唯一确定。设c h ( s ) 、a 羁釉在，上的投影区域是k ，i s , ，则 s 。，足内的点在，上的投影点一定分别在区域b ，i s , 内由定理3 ，s ls ：内一定有点 蟊，磊，它们在，上的投影为b c h ( s ，) 、b c 蜀( s 9 的近点对赢，蟊。于是 - i p a 得到如下 定理， 定理4 两