（应用数学专业论文）图形变形处理的能量算法.pdf

摘要 ? 6 2 5 0 7 在地图的制作，电子线路的安排等大量实际应用中，经常会要求对图形做 一些变形的处理使之适合一些特殊的要求，良中有一类实际问题是将原本稀疏 不均的图形在相对拓扑不变的情况下加以变形使其均匀以便于观看和进一步的 利用，苯文主要针对此类问题设计了一个算法，并在实际的应用中取得了较好 的效果。 本文设计一个算法解决上述问题，主要分以下几个步骤：一、利用物理的 力学原理构造了一个数学模型，将原来的实际问题归结为一个数学上的多目标 非线性规划问题；( 因为利用了力学中的能量原理，所以此算法称为“能量算法”一r 一 二、考察了原有的多目标非线性规划的相关理论，池括梯度射影法和罚函数法 等已有的理论算法，7 以及在自由曲线曲面设计中所使用的能量算法，结合实际 应用的需要，设计了一个新的算法；三、讨论了此算法解的相关性质，并通过 编程实现此一算法；陬据实际应用的需要对算法进行了优化，转化到具体的应 用中，良好的解决了原来的实际问题；i 四、将此算法和已有的算法在计算复杂 度等方面进行比较分析，举出了几个实际应用中的例子；最后提出了一些可能 改进的方向。 关键词 图形【，目标规划，能量函数，迭代，优化 分类号： 0 2 2 1 ，0 2 4 1 ，0 2 4 4 ，6 5 d ( a m s ) 磅 f， a b s t r a c t o nd e a l i n gw i t ha l lk i n d so fa p p l i c a t i o n so fm a k i n gm a pa n dp l a n i n gw i t h c i r c u i t r i e s ，i ti so f t e nn e e d e dt ot r a n s f o r mt h eg r a p h i c st os o m ee s p e c i a ls t y l e o n e p r o b l e m i st h a tt r a n s f o r mt h es p a r s ea n da s y m m e t r i cg r a p h i c st oas t y l ew h i c hi se a s y t ov i e wa n df o rm o r eu $ ea n dk e e pt h et o p o l o g i e s i nt h i sp a p e ro n ea l g o r i t h mi s b r o u g h tf o r w a r df o rs o l v et h i sk i n do fp r o b l e ma n d t h i sa l g o r i t h mh a sb e e nu s e di n p r a f i c e t h i s p a p e rd e s i g n aa l g o r i t h mt os o l v et h e p r o b l e m s f i r s t ，b a s e d o nt h e p t i c i p l e o f p h y s i c s am a t h sm o d e lw a sf o r m a f i o n e d ，t h e nt h eo r i g i n a lp r o b l e mc a l n ed o w nt oa m u l t it a r g e tp r o g r a m m i n gn o n l i n e a rp r o b l e m ；s e c o n d ，s e e i n ga b o u tt h et h e o r i e so f m u l t it a r g e tp r o g r a m m i n gn o n l i e a rp r o b l e m ，f o re x a m p l e ，c o m b i n i n gt h en e e do f p r a t i c e ，an e wa l g o r i t h m i sd e a l g n e d ；t h i r d ，a s t r i n g e n c ya n ds t a b i l i t yo f t h es o l u t i o n o ft h e p r o b l e mi sd i s c u s s e d p r o g r a m i s p r o d u c e da n do p t i m i z e d t os o l v et h e p r o b l e m f o r t h ，t h i sa l g o r i t h m i sc o m p a r e dw i t ho t h e ra l g o r i t h m so n c o m p l e x i t yo f c o m p u t i n g s o m ea e u l a le x a m p l e sa r eb r o u g h tf o r w a r d a tl a s t ，s o m ep o s s i b l e d e v e l o p m e n t sa r ed i s c u s s e d k e y w o r d ： g r a p h i c s ，t a r g e tp r o g r a m m i n g ，e n n e r g yf u n c t i o n ，i t e r a t i v e ，o p t i m i z e 3 月u 舌 图形的分析和处理正在得到越来越广泛的应用，包括地图制作、全球定位 系统、线路设计等多个领域都要用到。因此也涌现了大量的算法，并且转化为 实际的应用软件，以满足需要，如m a p i n f o 、i n t e r g r a p h 、a r c v i e w 等都是比较 成熟且通用的软件，这些软件可以解决很多常见的问题，满足大部分人的需要， 然而由于用户实际需求的多样性，有些比较专门的功能及算法还需要开发。 在上海市电话局的一个项目中，我们遇到了这样的一个问题：实际的电话 线路是在一个区域内相当密集，比如某个小区内，而在区域之间却比较松散( 见 附录图一图三图五) 。为了获得更为详细的信息，需要将局部密集的图形放大， 但是现有的软件只提供按照比例放大和缩小的功能，于是当局部放大的时候， 就丧失了对于整体性质的宏观把握。实际应用中更关心分支结构等几何性质而 不是真实的比例，因此很自然的就希望可以通过某种拓扑变换，使得在一个画 面内既可以显示局部的详细信息，又可以获得宏观上对于整体性质的把握。 事实上，不止在电话线路设计的应用方面，在其他方面也有类似的需求， 比如旅游地图的绘制，游客往往需要的是旅游景点内部的详细资料和与此相连 的交通线路等情况，但是在真实比例下，交通线路和旅游景点内部的比例往往 很悬殊，两者不可能同时清晰呈现。如果忽略真实比例的要求，将其进行拓扑 变换，那么就可以绘制出让人满意的旅游地图。 另一方面，在曲线曲面的造型设计中，基于物理能量模型的算法开始得到 应用。1 9 9 1 年，m i t 的g o s s a r d 教授和c e l n i k e r 博士发展了能量优化思想并使 用于自由曲线曲面的交互设计中d - a 。其后该方法在曲线曲面的造型方面得到了 深入的发展t 4 - 9 l ，这些工作对于本文的算法有很大的启发性。 本文是在实际的项目基础上向数学提炼抽象，基本思想是借用物理的力学 原理构建了一个数学模型，并归结到一个多目标数学规划问题，然后根据已有 的算法原理构造了一个迭代算法来解决这个问题，最后通过编程实现，并应用 到实际的分析之中，取得了良好的效果。 在第二节中利用物理的力学原理构建了一个模型，并提出了相应的能量函 数，第三节则将此模型转化为多目标数学规划问题，第四节介绍了多目标数学 规戈1 j 和非线性数学规划的一些原理，并提出了初步的迭代算法，第五节讨论了 该算法的收敛性及稳定性，第六节考虑了编程的问题，并根据实际的需要对算 法实行了优化，第七节举出了几个实际的图例，并和已有的算法进行了比较， 最后一节给出了结论并提出了一些可能的发展方向。 6 二模型的原理和建立 图的简要特征，我们所处理的图形为二维图形全部由点和边( 线段) 构 成，并且满足如下条件。 1 ) 图是无向的，本算法不考虑图中边的方向。 2 ) 图是直线图，即图中的每一条边都是直线。( 对于非直线地图，可以用一 些预处理将其改变为直线图，如先将曲线变成分段折线等方法。在此不 做更多介绍。) 3 ) 图是有界的。一般情况下，可以通过比例的改变显示在一个矩形区域内， 此矩形区域通常是某张图纸或者计算机的显示屏幕。 4 ) 图中的边可以有相交的情况，但交点并不作为图中的点，也可以有环路。 5 ) 图中没有重点和重边。( 如原图有，可以先用预处理解决) 定义p ( x ，y ) 为点，其中x ，y 为直角坐标： l ( 1 ，r ) 为连接两点的线段，其中l ，r 为点的序号。 则上图可以用两个数组表示，一个是点的数组p ( 五y ) i = 1 , 2 ，月， 一个是边的数组l ，( ，) ，j = 1 , 2 ，j ，l ，k 1 , 2 ，l ，r = 1 , 2 ，n ，其中n 为点 的数目，m 为边的数目。 我们将利用物理学力学原理来构建模型，图中的边可以看成是弹性杆子， 有一定的标准长度，当被拉伸或压缩时，就会产生弹性势能；图中的点可以看 成质量相同的质点，相互间有力的作用，因此有引力和斥力势能存在，从而对 图的各类要求都可以转化成求某个能量函数的极值。这样就可以转化为数学上 的多目标规划模型。 根据实际的应用，本文主要讨论以下几类要求： 1 边长均匀，即各条边的边长应趋于均匀。 2 结构均匀，为了使细节清晰，希望点与点之间、点与边之间边与边之间 的相互距离拉大，但是不能超过规定的边界，以防止无限制的放大。 3 保持拓扑结构，即原图中边与边的相交性不变，原图边的角度尽量不变。 下面引入相应的能量函数表示，则各类要求均可转化为对各自的能量函数 7 、 求极值。 对于边长均匀的需求，给定标准长度l ( 根据实际的图形确定，见第六节) ， 将边看成弹性杆，由物理力学中的h o c k 定律，其弹性力为f = k a l ，为其弹性 势能为e = 三七( a i ) ：，其中k 为弹性系数，由杆的材料性质决定，a l = l z 为 当前长度和标准长度的差。根据以上公式，采用如下的能量表示： 毋= ，( 三，一上) 2 其中局为相应的能量系数，e 为给定的边长常数，上，为图中的某一条边。 为了点与点之间的相互距离拉大的要求，相似于物理力学中的万有引力定 律，f = g 乞争，其中g 为万有引力常数，肌t ，m ：为质量，d 为距离，将点看 成单位质量的质点，把引力改为斥力，得到如下的能量表示： e 屯= 瓦k d 其中k 。为相应的能量系数，巩为两点之间的距离。 为了保持边与边之间相交性的拓扑结构，若两边原来相交，则两边距离为0 ， 能量为0 ，若两边原来不相交，则当距离为0 的时候能量为无穷大。记为e 。1 0相交性不变， i 0 0 相交性改变， 为了保持边的角度，若调整后的边与原图的边有角度差，则应产生势能， 给出如下能量函数： e = k 。a a 女 其中也为相应的能量系数，a 4 。为三。和原图相应边之间的角度。 则此问题转化为求以上各个能量函数最小的多目标规划模型 已知变量为所有点的坐标位置p ( x ，y ) 和边的端点信息。 约束条件为所有的坐标都必须在给定的矩形区域内部。 目标函数为各个能量函数最小。 以下即为所归结的多目标线性规划模型，命名为m p 0 问题： r a i n e = ( 毛，气，气，疋) 7 ( 2 1 ) ，= j 1 j - i，j - if j - x i y i q 其中q 为矩形区域，在应用中相当于显示范围的大小，e 为总能量，m 为总边数， 为总顶点数。 9 三多目标规划问题的一些原理 线性规划问题( 1 i n e a rp r o g r a m m i n g ，简记为l p 问题) ，就是在一组线性 的等式或不等式的约束之下，求一个线性函数的最大值或最小值的问题。 其一般数学形式如下： m m c l l + 。+ c h x h 约束条件 a r l x l + + 口l 。x n b a mr x l 七- + n 。x ，s b 。 x i ，x n 0 ( l p o ) 线性规划在各种实际应用如工农业生产和交通运输等方面有非常广泛的应 用，利用单纯形法等方法很容易得出线性规划的解。 然而，在实际问题中，往往会碰到多个因素的优化问题，并且很多问题不 能用线性函数来表示。于是就产生了比线性规划更一般性的多目标规划问题。 多目标规划对于众多的目标分别确定一个希望实现的目标值，然后根据不 同的实际情况提供不同的方法来解决。一般来说，多目标规划模型有以下的数 学形式： m a x z = f ( ) ( ) 约束条件 x 0 g ( x ) b 其中z ，x ，b 等均为n 维向量向量， c 是矩阵，则为线性规划。 以下介绍几个定义： ( g p l ) 如果f ( x ) = c x ，g ( x ) = a x ，其中a ， 定义1 ：设r = x ! g ( ) b ，x o j ，则称r 为多目标规划闯题( g e l ) 的可 行解集合。 定义2 ：设闯题( g p l ) 的可行解集合非空，y e r ，且对任意x e r ，有f f 聊 f ( x ) ，则称y 为问题( g p i ) 的绝对最优解，简称最优解。 由于多且标规划的各个目标之间往往是相互冲突的，因此问题( g p l ) 的绝对 最优解不一定存在，所以解决多目标规划问题一般采用在“有效解”集合中寻 i o 找“满意解”的方法。 定义3 ：设问题( g p l ) 的可行解集r 非空，y r ，若不存在x r ，满足 f ( x ) f ( y ) ，且至少有一个i 1 ，2 ，n 使( f ( ) ( ) ) ( j ) ( f ( ) ( i ) ，则称y 为 问题( g p l ) 的有效解。其中记号( f ( ) ( ) ) ( j ) 表示向量( f ( x ) ) 的第j 个向量。 对于多目标规划问题( g p l ) 的某个可行解x e r ，如能使问题提出者感到满 意，则称为满意解。 至今为止，已有很多种求解多目标规划问题的计算方法，但是大都基于以 下三种基本思想： t 权系数方法。这类方法是力图在各个目标之问寻找一种统一的度量标准 一权系数，然后将多目标模型转化为单目标模型。困难在于确定可信的 权系数，一般与实际应用相结合使用； 2 优先等级方法。这类方法类似于1 ，试图将多目标模型转化为单目标模 型，将目标按照重要程度分成优先等级，事实上相当于多次单目标规划； 3 有效解方法。求出所有的有效解，由用户判断是否满意。由于有效解的 数目众多，因此此方法不是很实用。 在实际应用中，以上三种方法往往结台使用，在本文中，主要采用权系数 法并结合优先等级法的思想。 四模型的改进和转化 在我们的问题中，事实上有四个目标，即： 1 边长均匀，相应函数e ， 2 点分布均匀，相应函数为e 。 3 湘交性不变，相应函数为e 4 尽量保持原图边的角度，相应函数为e 。 其中1 2 ，4 三个目标优先级别相仿，第3 个目标则属于比较高的优先级， 因此很自然的产生了对于目标3 采用优先等级法，对于其他目标采用权系 数法的思想。在实际的应用中，要求计算效率比较高，因此通过给目标3 赋予充分大的权来简化算法，以提高计算效率。 同时，考虑到第二节中所提出的函数本身已经带有不定系数，因此可以和 权系数合并，得到以下简化形式的单目标规划问题。 将目标3 的函数写为如下的形式，以和其他目标的形式相统一 e ：蔓 q d 0 其中k 。为待定系数，d o 为点i 和边j 的距离。 则m p 0 问题转化为以下的问题，称为n l p 0 问题： m i n e = e j ，十气+ ( + 疋) ( 4 1 ) i = i f 户lf p l x i ，r q 其中q 为整体的显示区域，e 为总能量，埘为总边数，n 为总顶点数。 当给定系数以后，此问题转化为单目标规划问题。因为能量函数中有根号及倒 数等形式，所以这是一个有约束的非线性规划问题。 1 2 五非线性规划的算法和本文的应用 上一节中将原问题归结到了一个单目标的非线性规划问题，其约束是线性 的，目标函数是非线性的，对于此类问题，已经有很多成熟的解法a 此类线性规划的一般表现形式为： m i n f ( x ) s t g ( x ) o ( 5 1 ) h ( x 户0 一般采用基本方法求解此类问题，所谓基本方法，是指一种搜索方法，通 过在可行域内直接搜索最优解的办法来求解原始问题，搜索过程中的每一点都 是可行的，并且目标函数值连续减少。基本方法有三个重要的优点，首先，因 为搜索过程中所产生的每点都是可行的，所以，如果在达到解之前过程就结 束，那么总点是可行的，于是，最后这一点是可行的，而且很可能几乎就是原 始问题的最优解，因而也就可能代表着引出这个线性规划的实际问题的较优解。 第二，如果此搜索过程产生一个收敛的序列，那么序列的极限点至少是一个局 部极值。第三，大多数基本方法不依赖于具体问题的结构，比如凸性，因此这 些方法适用于一般的非线性规划问题。基本方法包括可行方向法、梯度射影法 等方法。对于约束则用无约束问题来逼近，常用的包括惩罚法和碰壁法呻“3 1 等。 下面介绍本文所采用的梯度射影法的简单原理。 对于形如( 4 1 ) 式的非线性规划，很显然可以取得一个可行点x 然后在这个 可行点x 处寻找一个满足v ( 力d 0 的可行方向矢量d ，于是沿方向d 的移动 将使函数f 减小。 首先，我们研究满足使得所有起作用的约束仍保持起作用的方向，这个要 求相当于要求方向矢量d 位于由起作用约束所定义的切子空间m 中。我们将要 使用的这种特殊的方向矢量，就是负梯度在这个子空间上的射影。 为了计算这个射影，令爿。定义为由起约束条件所组成的矩阵。由于约束条 件的正则性，a 。就是一个其秩q n 的q n 矩阵。d 所在的切子空间m 是满足 a q d = 0 的矢量子空间。这意味着，由组成4 的行的矢量所构成的子空间n 是 正交于m 的。则任一矢量都能写成这两个互补子空间的矢量之和。特别的，负 梯度矢量一g 。能写为 一g t = d + a ；a ( 5 2 ) 其中d 。m ，鼠e 。我们可以通过令a q d t = 0 解出危。于是 a q d i = 一a q g t 一( 4 。4 ) 鼠= 0 ( 5 3 ) 这就导致 。= 一( 4 口爿：) a ，g 。 ( 5 4 ) 和 d 。= - ，一爿：( 4 彳；) a 。 g 。= 一只g t ( 5 5 ) 矩阵 只= ，一4 ：( 4 。一；) - 1 彳， ( 5 6 ) 称为对应于子空间m 的射影矩阵，它对于任一矢量的作用就产生该矢量在m 上的投影。 我们容易检验，如果矾0 ，那么它就是一个下降方向。 我们来研究步长的选择问题。当n 从零开始增大时，点x + qd 最初将保持 是可行的，并且f 的相应值是下降的。我们找出由x 出发的直线上的可行线段 的长度，然后再在此线段上使f 取极小。 其次，研究也可得出所射影的负梯度一般不为零。也就是说d 。不仅是一个 下降方向，而且也是一个可行方向。 以上即是梯度射影法的理论基础。 ， 由于算法可能被干扰产生间断，梯度射影法无法得出全局收敛性的证明， 但是在实用中，梯度射影法几乎没有发现过干扰现象。并且由于此方法的简单 性，大大弥补了可能性很小的干扰危险。 下面介绍惩罚法。 惩罚法是用无约束问题来逼近约束最优化问题的方法，在惩罚法中，是通 过在目标函数上加了一项，该项为破坏约束规定了一个高代价；在碰壁法中， 4 加上一个使得可行域的内点比边界附近的那些点有利的项。同这些方法相连带 的是一个参数u ，它确定了惩罚的严厉或碰壁的严重程度，因此也就确定了无 约束问题近似于原始约束问题的程度。当u o o 时，近似就变得逐步精确。 在本文的算法中，通过把构成矩形边界的四条边考虑成图的一部分，但是 这四条边不参与变形，只和其他点和边相互间有力的作用，本质上是碰壁法的 一种变形。 具体的迭代步骤如下： 1 对所有点和边做循环，计算总能量e ( o ) ； 2 根据梯度射影法对点做出调整，得到新的图，并计算其总能量e ( n ) ，使 得e ( n + 1 ) e ( n ) ： 3 如果f e ( n + 1 ) 一e ( n ) i e ，则结束，否则转2 。 对于每一个点，都计算与其相关的能量，将此能量作为该点的能量值e 。 选择当前能量最大的点，在该点的切线方向对该点进行调整，使该点的能 量减少，e ( n + 1 ) = e ( n ) 。 如此形成一个总能量单调减少的算法。当e 充分小的时候我们就得到了一 个解。 从计算的角度考虑，不采用直接计算能量的方法，而采用计算点所受的力， 也就是能量函数在该点的切向，这样可以简化计算，加快收敛速度 从物理的角度来看，因为物体之间有力的作用所以产生一定的势能，而整 体将向能量最低的方向变化，也就是按照力的方向变化 和以上能量函数相关的力函数分别是： 对于边d d ，其端点所受力为 e l = k l x ( 丽一麓- ) = k lx ( j 蚓_ - ) 麓 ( 5 2 ) k 。为弹性系数，厶黾我们要求的边长常量。 对于端点d id ：，d l 所受d ：的斥力为： f0 ，若i d 。d 2 障d 耻卜t 壶一务羔孙划。 筘3 ， 其中k 。为斥力系数，d 为临界距离常量 对于边d 。d ：以及边外一点d ，记d 到d 。d ：的垂足为d ，则祈受的d d ：的斥力为 ( 5 4 ) k h 为斥力系数，h 为临界距离常量。边的每一个端点d ，和d ：受到的反作用力为一0 5 f h x c t ：边d ，d ：，输入图对应边为矾d ：，则d ：所受扭转力为 f a = k a c 器一稳 氍卵 其中k 。为扭转系数。注意，式中角度是一个近似值。 1 ) 对于给定的图，按照以上力函数计算每个点所受的力； 2 ) 将受力最大的一个点在力的方向上移动一个微小的距离6 ，从而得到 个比原图的总能量减少的新图； 3 ) 判断这个新图是否满足收敛条件，若不满足，则转1 ) ，若满足，则结 束。 这里收敛条件是预先给定的，可以是总能量小于某一个数值，也可以是迭 代的次数到了某个数，也可以是点上所受力的最大值小于某一个数值，根 据实际的需求由用户加以调节或者固定在程序代码之中，参见第六节关于 优化的有关内容。 日 d 耻卜去( 最叫斋引划如 2 fo ，若i d ，d ：除h 耻b 吉c 南卸高剖纠m g = k a x c 麓一蔫， ( 6 3 ) ( 6 4 ) 由于三，d ，h 均为事先给定的常数，将其与系数合并，得到新的待定系数 k ：= k l 彤：= k 。石1 k ：= k “。百1 k = k 经过以上转换以后，我们可以看到，( 6 1 ) 一( 6 4 ) 各式的形式一致，属于同 数量级，因此待定系数砭，k ：，k ：，k j 也取成同一数量级，不妨定为系数k ，k 的具体数值理论上对结果并没有影响，可以根据实际的计算进行调整，使得计 算效率和精度提高。 而，d ，日则根据实际情况取成平均长度的数量级，并可以由用户加以调整。 下面对函数进行优化。根据物理力学原理导出的函数虽然比较直观，易于 理解，但是存在着收敛速度慢，精度不高等缺点。因此需要对函数加以优化使 其更适合实用。 从前面几节的内容可以看到，函数的具体形式并不是特别的重要，只要保 证定性的需要就可以了。 在满足边长均匀的目标中，其能量函数的本质即随着与标准边长差距的增 大能量值也随之增大，原函数是采用简单的线性函数，其性质过于简单，无法 满足实际的需求，根据实践经验，我们发现将其换为二次多项式就可以取得比 较好的效果，同时也不增加太多的计算量。 同样道理，在其他几个目标中，都根据实际情况对函数做了修正，一般是 以低次分段多项式函数进行替换，在不增加计算复杂度的情况下得到较高的精 度和收敛速度。在保持平行性方面，则采用正切函数。这些替换主要是根据实， 际的需求作出的，对于算法的本质并没有太大的影响。 另一个重要的因素是收敛条件的选择，主要是对总能量差加以判断。 e 和乞+ ，分别是第n 次和第n + 1 次迭代以后的系统总能量，n ( 4 1 ) 式计算 得出，当i 压。一。l 小于给定的阈值，则迭代自动终止，其中e 根据图的数 量级可以事先估计，也可以由用户根据结果进行调整，以获得令人满意的精度。 七复杂度分析和一些例子 在第五节的算法中，对于1 1 个点、m 条边的图，其主要计算量为循环计算 2 各项能量，其中e t 为m 次，岛为冬次，以为l n 次，e o 为m 次，每次循环 内部的计算量属于同一数量级，则此算法的整体复杂度为o ( n ( n 2 + m ) ) ，在实际 的应用中，边的数目和点的数目相近，m 近似于n ，可以简化为o ( n 2 o 附例中给出了几个实际的图例，均为p i l 2 6 6 ，3 2 m 内存的p c 机上运行的 结果。这些图例是从上海市电话规划局的电话线路布局图经过简化以后得到的。 图为5 1 个点，5 4 条边，运行时间不到2 秒，处理后的结果见图二； 图三为1 0 8 个点，1 2 2 条边，运行时间为1 0 秒，处理后的结果见图四； 图五为2 1 6 个点，2 4 0 条边，运行时间为4 2 秒，处理后的结果见图六； 实际的程序中提供给用户即时的人机交互功能，将每一次的迭代都显示出 来，使得用户可以观察图形的即时变化，根据自己的实际需要，可以在没有完 全收敛之前自行终止本程序。 9 ， ) 八结论和改进方向 本文通过以力学为基础构造了一个图形处理的数学模型，将其转化为一个 多目标规划问题，利用权系数法给出了一个算法，并得出了解的存在性稳定性 和收敛性。 此算法具有速度快，容易实现，便于移植等优点，只需要把能量函数稍加 变化就可以适应不同的要求，从而达到不同的效果。同时此算法很容易推广到 三维的情形。 虽然此算法最初是为了电话线路方面的相关项目设计的，但是也可以在旅 游地图的制作和电路设计及其他具有类似问题的图形处理方面应用。 由于此算法应用性很强，因此为了得到较好的效果，目前很多参数需要用 户自己设定，今后可以考虑在参数自动设定的方面再进行深入的探讨。 九 1 2 3 】 4 5 】 6 】 7 f 8 9 】 1 0 】 1 1 1 2 】 ( 1 3 】 【1 4 参考文献 c l e n i k e r ，g a n dg o s s a r d ，d ，c o n t i n u o u sd e f o r r n a b l ec u r v e sa n dt h e i r a p p l i c a t i o n t of a i r i n g3 dg e o m e t r y p r o c i f i pt c 5 w g 5 2w o r k i n g c o n f ，g e o m e t r i cm o d e l l i n g ，r e n s s e l a e v i l l e ，n y ，u s a ，1 9 9 1 ，5 2 9 c l e n i k e r ，g a n dg o s s a r d ，d ，d e f o r m a b l ec u r v ea n ds u r f a c ef i n i t e e l e m e n t s f o r f r e e f o r ms h a p e d e s i g n ，a c m c o m p u t e r g r a p h i c s ，v 0 1 2 5 ， n o 4 ，1 9 9 1 ，2 5 7 - - 2 6 6 c l e n i k e r ，g a n dw e l c h ，w ，l i n e a rc o n s t r a i n t sf o rd e f o r m a b l eb - s p l i n e s u r f a c e s ，i np r o c e e d i n g so ft h es y m p o s i u mo ni n t e r a c t i v e3 d g r a p h i c s ， a c m ，n e wy o r k ，1 9 9 2 ，6 l 一6 8 宋德军，朱心雄，基于数学规划的曲面造型方法，工程图学学报，n o 1 ， 1 9 9 8 ，4 1 _ 4 7 关志东，经玲，宁涛，唐荣锡，基于物理模型的变形曲线曲面研究及 应用，计算机学报，v 0 1 1 9 ，1 9 9 6 ，1 8 7 一1 9 4 宋德军，基于能量优化的曲线曲面造型理论及应用研究，北京航空航 天大学博士学位论文，1 9 9 8 g r e i n e r ，g ，s u r f a c ec o n s t r u c t i o