（计算机应用技术专业论文）同构化二维点集凸壳算法研究.pdf

旦塑些三丝皇叁鱼壅竺鲨堡壅 ： 优划分；模式识别中，可借模式凸壳，描述模式外形的重要特征；物体分类 中，可凭各物体凸壳相似度，勾画出这些物体所属类别；计算机图形学中， 可用一组点的凸壳，显示出其点簇( c l u s t e ro fp o i n t s ) ：在指纹识别中， 可以根据指纹边缘轮廓点集凸壳，获得高质量的指纹，所以说凸壳的应用范 围非常广泛，它必将具有非常广阔的市场前景和经济价值。 关键词：计算几何；同构化：点集；凸壳；算法时间复杂度 a b s t r a c t n 忙p r o b l e mo f c o n v e xh u n i st h em o 髓i m p o r t a n tm o s tb a s i c a n da l s og e t sa l o to fp r o f o u n dr e s e a r c hi nc o m p u t a t i o n a lg e o m e t r y i ti sa p p l i e di ns t a t i s t i c s i t w a sp u tf o r w a r di nt h e2 0 t hc e n t u r y s i n c et h e19 7 0 s ，m a n yd o m e s t i ca n df o r e i g n e x p e r t sa n ds c h o l a r sh a v ep a i da t t e n t i o nt ot h ec o n v e xh u l la l g o r i t h mb e c a u s eo f t h ec o m p l e x i t ya n dt h ei m p o r t a n c eo f a p p l i c a t i o no f t w o - d i m e n s i o n a lc o n v e xh u l l t h e r ea r em a n yf a m o u sc o n v e xh u i la l g o r i t h m si nt h el a t e2 0 t hc e n t u r y , s u c ha s g r a m h a mc o n v e xh u l la l g o r i t h m ，h a l f - d i v i d i n gc o n v e xh u l la l g o r i t h ma n ds oo i l 1 1 l er e s e a r c ho fc o n v e xh u l la l g o r i t h mb e g a ni nt h e1 9 7 0 s ，d e v e l o p e di n19 8 0 s ， m o s ti nt h e1 9 9 0 s b u tt h er e s e a r c ho fc o n v e xh u l la l g o r i t h ms t o p p e di nt h es t a r t o ft h e2 1 s tc e n t u r y s ot h ea l g o r i t h mi s1 1 0 1m a n y t h ce x i s t i n gc o n v e xh t i l l a l g o r i t h mi sn o to n l ys e r i a lo rp a r a l l e r ，b u ta l s ob yp o 础r e c u r s i v ea n dc u tp o i n t r e c u r s i v ed i s t i n c t i o n i nt h i sp a p e ro nt h eb i s i so f p r e v i o u ss t u d i e s ，ic a r r i e do u tt h e s t u d y i n go fc o n v e xh u l la l g o r i t h mb a s e do l lt h ei s o m o r p h i co f t h eb a s i ct e n e t so f t h en e w p e r s p e c t i v ep o i n ts e t ( n o t e ：i n c l u d i n gt h es e r i a la l g o r i t h ma n dt h ep a r a l l e l a l g o r i t h m s ，t h eg r i l l eb e l l o w ) t h em a i nc o n t e n t so fc o n v e xh u l la l g o r i t h mb a s e do n i s o m o r p h i s mp o i n ts e ta r e ： 1 1 1 忙s t u d y i n go fe x i s t i n gc o n v e xh l l l la l g o r i t h mi no r d e rt of i n do u tt h e w e a k n e s s e s ，a n dl e a r nf r o mt h ee x p e r i e n c e 2 n 忙s t u d y i n go ft h ei s o m o r p h i cs t r u c t u r eo ft h ec o n v e xh u na l g o r i t h mt o s e e ki t si s o m o r p h i cn a t u r eo f c o n f i g u r a t i o n 3 t h es t u d y i n go ft h ei s o m o r p h i cc o n v e xh u l la l g o r i t h mi l lo r d e rt oc r e a t e b e = t t e rp e r f o r m a n c ec o n v e xh u l la l g o r i t h mi np o i n ts e t a tt h eb a s eo fi s o m o r p h i cn ；s e a r c l lt h ep a p e rp r e s e n t ss o m er e p r e s e n t a t i v e a l g o r i t h m s s u c ha s “an e wa l g o r i t h mf o rf i n d i n gc o n v e xh u l lw i t ham a x i m u m p i t c ho ft h ed y n a m i c a lb a s el i n e ”? an e wa l g o r i t h mf o rf i n d i n gc o n v e xh u l l b a s e do nc o i l i n gw i t ham i n i m u ml e v e rp i t c hi nd o u b l ed o m a i na n dd o u b l e d i r e c t i o n ”，”an e wp a r a l l e la l g o r i t h mf o rf i n d i n gc o n v e xh u l lb a s e d0 1 1 同构化二维点集凸壳算法研究 c o w 。”a ni m p r o v e r n e n t f o r e - s i g n a t u r et e c h n i q u e s b a s e do n d i g i t a l e n c r y p t i o na n di n f o r m a t i o nh i d i n g , t h ef i r s tt i m ep u tt h et e c h n o l o g yo f c o n v e x h u l li nd i g i t a le n c r y p t i o n i na d d i t i o nt ot h ea p p l i c a t i o n sa b o v e ，c o n v e xh u l la l s oh a v ew i d e - r a n g i n g a n di m p o r t a n ta c a d e m i cs i g n i f i c a n c ea n dv a l u ei n c o m p u t i n gg r a p h i c s ，i m a g e p r o c e s s i n g , p a t t e r nr e c o g n i t i o n ，f i n g e r p r i n tr e c o g n i t i o n , g e o l o g i c a le x p l o r a t i o n , d i s t r i b u t i o nn e t w o r k s ，e n v i r o n m e n t a lm o n i t o r i n g ”f o re x a m p l e , i ni a m g n p r o c e s s i n gw ec o u l df i n dc o n v e xh u l lo ft h ei m a g ei no r d e rt og o tt h ek e y s h a p e ，i nt h ed e c o m p o s i t i o no f t h ew o r d s ，w ec o u l ds t r u c t u r et h ec o n v e xh u l li n o r d e rt og n tt h eb e s tw r i t i n gd i v i s i o n i np a t t e r nr e c o g n i t i o n , w ec o u l dd e s c r i b et h e i m p o r t a n tc h a r a c t e r i s t i co fp a r e r nw i t hc o n v e xh u l l i no b j e c tc l a s s i f i c a t i o n ，w e c o u l dl a yo u tt h ec l a s so f o b j e c t sw i t ht h es i m i l a r i t yo f t h eo b j e c t s c o n v e xh u l l i n c o m p u t e rg r a p h i c s ，ac o n v e xh u l lo fag r o u p o fp o i n t sc o u l dd i s p l a yt h ec l u s t e r o fp o i n t s i nf i n g e r p r i n tr e c o g n i t i o n , w ec o u l dg o th i g h - q u a l i t uf i n g e r p r i n t s a c c o r d i n gt ot h ec o n v e xh u l lo ff i n g e r p r i n tc d g e s o ，t h es c o p e o f t h ea p p l i c a t i o n o fc o n v e xh u l li sv e r ye x t e n s i v e t h em a r k e tp r o s p e c t sa n de c o n o m i cv a l u ei s v e r yb r o a d k e yw o r d s ：c o m p u t a t i o n a lg e o m e t r y ；i s o m o r p h i s m ；p o i n ts e t ；c o n v e xh u l l ； a l g o r i t h mt i m ea o m p l e x i t y 2 西南财经大学 学位论文原刨性及知识产权声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标 明。因本学位论文引起的法律结果完全由本人承担。 本学位论文成果归西南财经大学所有。 特此声明 学位申请人：关 1 24 - 2 0 0 7 年1 1 月2 0 日 预备知识 1 1 计算几何简介 1 1 1 前言 1 预备知识 计算几何是于七十年代中期出现的一门新兴学科，它的内容属于欧几里 得的几何构造范畴，主要涉及几何对象的算法、数据结构及复杂性分析，其 中它的重点就是设计更快的算法。欧几里得的几何构造满足算法的所有要求： 无二义性，有穷性，确定性，输入，输出，正确性等。那么计算几何和我们 谈论到的计算机图形学以及几何的区别在哪昵? ( 1 ) 计算几何与计算机图形学的区别：计算机图形学是近三十年来发展迅 速、应用广泛的新兴学科。它主要研究用计算机及图形设备进行图形的输入、 表示、修改、变换和输出，而不是算法分析 ( 2 ) 计算几何与几何定理机器证明的区别：几何定理机器证明包括多种不 同的方法，比如：吴方法、g r o b n e r 基方法、单点例证法、数值并行法。其中， 1 9 7 7 年由吴文俊先生提出来的一种用代数的方法来证明几何定理的新的方法 吴方法，是其代表。它主要研究定理证明的探索方法及证明过程的推断， 而不是几何本身。 计算几何作为计算机科学的一个分支，是方法论，而不是严密的公理化 的科学体系，其目的在于寻找能用计算机高效解决几何构造问题的算法。而 经典的几何的观念、几何对象的表征并不适于有效的算法设计；因此要建立 一些几何实体。计算几何是从实践中来，回到实践中去，它属于应用范畴。 同构化二维点集凸壳算法研究 1 1 2 几何学的历史及发展 几何学的起源可以追溯到埃及和希腊时代。当时，人们为了丈量土地， 修建建筑物，必须要计算长度、面积和体积，这时几何学的主要目的是研究 几何体的简单度量性质随着计算机时代的到来，计算机图形学得到充分的 发展，但是由于传统几何学的限制，人们在解决某些特殊问题的时候遇到了 很大的困难，而这些问题与欧几里得的几何构造有关，但是当时人们所重视 的是公理化证明，主要研究的是几何体的几何性质，而忽视了几何构造问题， 这就迫使人们重新研究这一古老但被人遗忘的课题，且融合了计算机算法、 计算复杂性等学科的知识，便形成了一个崭新的交叉学科计算几何。正 式提出计算几何这个概念可以追溯到1 9 7 5 年s h a m o s ( 沙莫斯) 和h o e y ( 霍伊) 利用计算机有效地计算出了平面点集的v o r o n o i 图，并发表了一篇著名的论 文i np r o c e e d i n g so ft h e1 6 t ha n n u a li e e es y m p o s i u mo nf o u n d a t i o n s o fc o m p u t e rs c i e n c e ，从此计算几何诞生了。计算几何是几何学的一个扩 展，随着计算机技术的飞速发展，它研究的对象已经远超出了几何学的研究 范围它研究的几何问题往往包括了大量的几何对象，比如点或线的集合。 它是理论计算机领域中一个新的极有生命力的子领域，其研究成果己在计算 机图形学、化学、统计分析、模式识别、地理数据库等众多领域中得到广泛 的应用 1 1 3 计算几何的研究对象 计算几何研究的问题主要有以下几种类型： ( 1 ) 子集选取。例如求凸壳的顶点； ( 2 ) 计算。类似于解析几何的计算： ( 3 ) 判定问题。例如两个凸壳是否相交? 某个点是否在多边形内? 由上，我们可以看出计算几何的目的是，为用计算机解决一些域几何实 体有关的问题而设计有效的算法。最典型的基本问题有：1 几何搜索问题；2 几何实体相交问题；3 邻接问题；4 凸壳计算问题。而确定平面点集的凸壳 是计算几何中的基本问题，也是首要问题之一，它在算法设计中有着重要的 作用，更具有重要的理论和应用价值。 2 i 预备知识 1 2 算法的预备知识 1 2 ，1 算法的概念及特征 众所周知，算法是求解一个问题类的无二义性的有穷过程。这里的过程 是指求解问题执行的一步一步的动作的集合，每一步动作只需要有限的存储 单元和有限的操作时间。另外，如果详细说明了一台典型的计算机以及与这 种计算机通信的语言，那么凡用这种语言编写的可以在给定的计算机上执行 的过程便称为算法，一个问题可以用多种算法来解决，一个给定的算法解决 一个特定的问题。算法是对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。但不是任何指令序列都可以称 作算法，要能够称作算法，必须具备以下五个重要的特征： l 、有穷性：就是指算法在执行一段时间后结束，而不是无止境地执行下 去 2 、确切性：算法中的每一条指令必须有确切的定义，人们对它的理解不 会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径也就是 说，对于相同的输入，只能得出相同的输出。 3 、输入：一个算法有0 个或多个输入，用来刻画运算对象的初始情况， 所谓0 个输入是指算法本身定义了初始条件。 4 、输出：一个算法有一个或多个输出，用来反映对输入数据加工后的结 果没有输出的算法是毫无意义的 5 、可行性：就是指一个算法必须是能行的，即算法中描述的操作都是可 以通过已经实现的基本运算执行有限次数来实现的。 应该指出，算法不等于程序，算法和程序是两个不同的概念。因此描述 算法的方式将是多种形式的，为了把算法转换成上机程序，还需要进行编程 工作。一个计算机程序被认为是对一个算法使用某种程序设计语言的具体实 现。算法必须可终止意味着不是所有的计算机程序都是算法。例如：操作系 统是一个程序，而不是一个算法。然而，我们可以把操作系统的各种任务看 成是单独的问题，每个问题由一部分操作系统程序通过特定的算法来实现， 同构化二维点集凸壳算法研究 得到输出结果后便终止 对算法设计的要求，在不同的场合，不同的应用领域，要求是不一样的， 一般情况下算法的性能标准有：正确性( c o r r e c t n e s s ) 、可计算性 ( c o m p u t a b i l i t y ) ，可读性( r e a d a b i l i t y ) 、健壮性( r o b u s t n e s s ) 、通用性 ( g e n e r a l i t y ) 、效率及存储量要求。 其中算法执行效率需依据该算法编制的程序运行时消耗的资源，包括计 算机运行时间和所占用的内存空间来度量。与之相对应，算法的效率就分为 时间效率和空间效率两个方面，也就是说算法的复杂性包括算法的时间复杂 性和算法的空间复杂性为了说明复杂性的概念，先介绍问题规模的概念。 用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的 尺度，称为问题规模。比如：行列式的规模可以用其阶数来表示。图问题的 规模可以用其边数或顶点数来表示，等等。 1 2 2 算法的时间复杂度分析 利用某算法来处理一个问题规模为n 的输入所需要的时间称为该算法的 时间复杂性，它显然是n 的函数，可以记为t ( n ) 它可以通过计算一个程序 的执行时间来得到，而一个程序执行时间等于其所有语句执行时间的总和， 任意语句的执行时间为该语句执行一次所需时间与执行次数的乘积，即： 算法的执行时间= 操作的执行次数操作的执行时间 就是说算法的执行时阃与操作执行次数之和成正比。所以我们看到要想 精确计算各种语句执行一次所需时间时十分困难的，甚至是不可能的( 因为一 个算法的不同输入往往产生不同的运算次数，而一个算法的所有不同输入的 数目可能十分庞大) ，它与执行程序的硬件环境、书写程序的语言、所用编译 程序的质量及运行环境等因素有关，因此，在算法分析中我们只要知道时间 耗费的增长率大体在什么范围内，粗略的估计一下算法中语句执行的最大次 数来作为算法时间效率的度量就可以了，而不必精确计算具体执行时间或者 算法的平均运算次数 也许有人会说现代计算机的运算速度越来越快，研究精良算法已经没有 必要了，这是错误的观点，例如： 4 l 预备知识 假设有5 个算法 。 2 ， 尢 时间函数增长情况如表1 1 所示： 表1 1 算法与时间复杂度对比表 时间复杂性 n n l o g n n j n 2 i 算法名称 算法a l算法a 2算法a 3算法算法a 5 时间复杂度 r l l o g n n 2 n 3 2 。 闩 1l 0 1l2 题 222 4 84 规 4481 66 41 6 882 4 6 45 1 2 2 5 6 模 1 61 6 6 4 2 5 64 0 9 66 6 5 3 6 n 3 23 2l 1 0 2 43 2 7 6 84 2 9 4 9 6 7 2 9 6 例如表1 1 所示：时间复杂度函数不同的数算法 算法 5 ，其时间复 杂度函数近似值随其问题规模n 而快速增长的对比。表1 1 说明：算法时间 复杂度函数为n 2 、1 1 3 、2 时，时间复杂度将随问题规模增大变得极为巨大，使 解决问题的时间严重失控 表1 2 输入与提高效率的关系对比表 算法时间 可处理问题规模( 数据输入单位：个d , 时) 名称复杂度 原最大规模s b 。电脑速度提高l o 倍s a is b i 与s a i 的关系 a i n3 6 1 0 93 6 1 0 o s a i - 1 0 s b i a s n l o g n 1 3 3 3 7 8 0 5 81 1 9 3 9 0 1 9 2 3 l s a 2 = 8 9 5 s b 2 a s n 2印0 0 03 1 6 2 s a 3 = 3 1 6 s b 3 a 4 n ，1 5 3 2 3 3 0 1 s a 4 = 2 1 5 s b a s 2 。3 1 73 5 s a 5 = s b 5 + 3 3 又例如表1 2 所示：时间复杂度函数不同的数算法a 。算法凡，其提高 时间复杂度远比提高计算机速度更为经济表1 2 中：设算法 在1 秒内可 同杓化二维点集凸壳算法研究 处理问题规模为1 0 6 个数据输入；记s b 为算法i 的原最大可处理问题规模， s j 为电脑速度提高1 0 倍后的算法i 最大可处理问题规模。对算法时间复杂 度较高的算法a ，若改用复杂度较低的a 。、a 。代替，则分别可解比原问题规 模大3 9 、8 7 0 6 1 倍的同一问题。由此足见，算法改进所提升的软件效果，远 远大于电脑速度提高的硬件效果。 1 2 3 算法的空间复杂度分析 一个算法的空间复杂度，一般是指该算法在执行过程中所占辅助存储空 间的大小，包括算法程序所占的空间，输入数据所占的存储空间以及算法执 行过程中所需要的辅助空间。如程序执行过程中的工作单元以及某种数据结 构所需要的附加存储空间等。若输入数据只取决于问题本身，与算法无关， 则只需要分析除输入和程序之外的额外空间，在许多实际问题中，通常采用 压缩技术以尽量减少不必要的额外空间。 类似于算法的时间复杂度，空间复杂度作为算法所需存储空间的量度， 记做s ( n ) = 0 ( f ( n ) ) ，其中n 为问题的规模( 或大小) ，即算法所需存储空间的 多少 1 3 凸壳的简介 二维点集凸壳( 即覆盖给定点集的最小凸多边形) 及其算法研究【l 叫0 7 】， 是计算几何学的基本内容广义凸壳( 亦称凸包) ，是覆盖给定图形集的最小 凸图形。但本文只论及计算几何学的基本问题与重要内容之一的狭义凸壳一 一二维点集凸壳( 下称点集凸壳，即覆盖给定二维点集的最小凸多边形) 及 其算法。点集凸壳算法间的同构化本质与联系及其算法创新研究，是计算几 何学的新问题 点集凸壳，人们早己关注，广泛应用于：计算图形中，可用一组图形点的 点集凸壳，显示出其点簇；图象处理中，可用寻求图象点的点集凸壳，找到 数字图象中的关键凸面；机器人学中，可据人工视觉下视物点的点集凸壳， 6 l 预备知识 指挥机器人行为；指纹识别中，可据指纹边缘轮廓点的点集凸壳，获得高质 量的指纹；模式识别中，可借模式点的点集凸壳，描述模式外形的重要特征： 地物辨识中，可借航空航天遥测地面视物点的点集凸壳，快速识别地物的平 面场景区域；公路规划中，可借所论区域内各城、镇、乡、村位置点的点集 凸壳，科学规划该区域的最佳环形公路；物体分类中，可让各物体点的点集 凸壳相似度，勾画出这些物体所属类别；古繁体文字分解中，可凭构造字形 点的点集凸壳，形成对文字的最优划分；等等。 显然深化点集凸壳已有的广泛应用中，生成所论点集凸壳的算法首当 其冲，而进一步研究点集凸壳的新算法更显得举足轻重；推进点集凸壳算法 创新研究中，研究它们的同构化构造本质势在必行，而进一步应用它们的同 构化构造联系尤至关重要因此，开展同构化点集凸壳算法创新研究，对“有 力促进计算几何学的丰富与发展，大大提升点集凸壳的应用与水平，捷足抢 占同构化点集算法创新研究制高点”，具有重要学术意义与重大应用价值 1 3 国内外研究现状及分析 1 3 1 点集凸壳算法国外研究现状及分析 迄今已三十多年的国外点集凸壳算法研究，始于2 0 世纪7 0 年代、盛于 8 0 年代、巅于9 0 年代，但滞于2 1 世纪，至今己久无新进展。较具影响的串 行点集凸壳算法及其研究者，主要有：1 9 7 0 年，d c l l 加da n ds 1 ( 冲盯提出 了第一个最早的凸壳算法。卷包裹”算法“，但只可惜它是o ( n h ) 的低效近 似算法( 其中：n 为输入二维点集的点数，h 为输出凸壳的顶点数) ；1 9 7 2 年 rg r a h a m 发表了第一个最流行的“格莱汉姆扫描算法”，但其o ( n l o g n ) 的算法处理较繁；1 9 7 3 年a rj a r v i s 、1 9 7 7 年w f e d d y 、1 9 7 8 年九b y k a 分别给出了正相关于凸壳顶点数的行进算法呻1 、快速凸壳算法嘲、快找凸壳 算法1 ，但三者o ( n h ) 的算法效率欠佳。随后数十年间研究所得点集凸壳算法， 绝大多数( 例如：1 9 7 7 年f p r e p a r a t a s j h o n g 、1 9 7 8 年a b y k a t 、 1 9 7 8 年s g k l g t t o u r r i n t 嘲、1 9 7 9 年 m a n d r e w 、1 9 7 9 年 p j g r e e n 矗b - s i l v e r m a n o ”、1 9 8 4 年m i ( a l l a y 恤l 、1 9 8 6 年 7 同构化二维点集凸壳算法研究 d k i r k p a t r i c k r s i e d e l 乜盯等人提出的凸壳算法) 都是o ( nl o g n ) ，也有 一些算法( 例如：1 9 7 8 年j l b e n t l e y m i s i i m o s p ”、1 9 8 1 年l p d e v r o y e | 2 7 l 、等人所提出算法) 在一定的凸壳顶点分布约束下可期达o ( n ) 。 而较具影响的并行点集凸壳算法及其研究者，主要有：1 9 8 8 年t lm i l l e ra n dq f s m u t 捌、1 9 9 5 年m j a t a l l a h d z c h e r t l l 8 】等人提出的并行凸壳算法等 此外，不少著作、网站也较详细介绍了点集凸壳及其算法研究，例如j o r o u r k e 的 c o m p u t a t i o n a lo e o m e i r y i nc ( e n de d i t i o n ) ) ( 1 9 9 8 ) l l z 】与此同期， 1 9 7 8 年d a v i s 3 6 、1 9 8 1 年a c y 幻【冽等人证明了找出凸壳的时间下限为0 ( n l o g n ) 。1 9 9 7 年c b a r b e r 等人提出的以“删除以初始点集的最左点、最右点、 最高点、最低点为顶点的四边形内各点”与“在随后逐步缩小的各自剩余区 域内寻找其制高点”为特色的快速凸壳算法i 。3 l ，事实上成为全球点集凸壳算 法研究的迄今顶峰。此后，a e r n s t l l 8 l 、b s a r a l 9 】等人对分治技术、随机技 术等的凸壳算法研究作了有益探索。2 l 世纪前后，点集凸壳算法研究，越来 越多地集中到的应用化、并行化、高维化方向，并出现了2 l 世纪的裹足不前。 i 3 2 点集凸壳算法国内研究现状及分析 至今也二十来年的国内点集凸壳算法研究，始于2 0 世纪8 0 年代、巅于 9 0 年代，同滞于2 l 世纪。1 9 8 5 年周之英最早提出平面点集凸壳的实时算法， 1 9 9 0 年代起最专注点集凸壳算法研究是周培德。较具影响的点集凸壳算法及 其研究者，主要有：1 9 8 0 年代，最早期的周之英l l o i ( 平面点集凸壳的实时算 法) ，汪嘉业1 1 0 6 1 ( 单多边形求凸包的线性时间算法) ；1 9 9 0 年代，最突出的 周培德 9 9 - 1 0 5 1 ( 求凸壳顶点的一种算法、) ，杜玉越瞰1 ( 一种求简单多边 形凸包的最优算法) ，周洪玉【i o o l ( 图像处理系统中快速凸化算法) ，以及吴中 海【9 l l 、文尚猛【8 9 】、金文华l l l l 、王志强1 8 3 - 8 5 、李秀忠叫等人及其研究；2 0 0 0 年来，陈国良【删( 并行计算：结构算法编程) ，周培德【7 6 l ( 计算几何： 算法分析与设计) ，以及汪学明 4 6 1 、庞明勇1 4 7 l 、郝小柱船】、彭认灿1 4 9 1 、胡 鹏即l 、余翔字唧1 、郝小柱【竭、杨勋年【s i l 等人及其研究。尤其可贵的是，王 晓东 i 0 4 ( 凸壳问题的计算时间下限) 1 9 9 4 年证明了比国外更精确的凸壳找 出时间下限。但进入2 1 世纪来，我国点集凸壳算法研究同国外一样也停滞不 i 预备知识 前 尽管国内点集凸壳算法研究【2 1 0 7 j 至今也二十来年，也不乏重要学术成果 ( 例如：平面点集凸壳的实时算法0 0 7 1 、图像处理系统中快速凸化算法【1 0 0 、 求平面点集凸壳的一个最优算法【删，等等) ；但与国外同行相比仍有较大差距， 不仅我国起步期学术成果最早问世时问i 1 0 7 】比国外同行晚整整1 5 年，更因长 期来我国此领域大多数研究尚属介绍或应用国外同行学术成果的跟踪研究， 从而使我国的点集凸壳算法研究总体上一直无法超越国外1 9 9 7 年已达项峰 这就不能不使我国此领域有独立知识产权的原创性、源头性、系列性、自主 性创新研究成果，一直寥若晨星事实上，点集凸壳的各算法之间，点集凸 壳算法与圆集凸壳算法之间，本质上一定必有其相应的同构化本质联系与构 造关系 i 3 2 二维凸壳问题与凸壳算法描述 定义l 设多边形q 的顶点是给定平面内的点q ( x ，y 。) ，如( x 2 ，y ：) ， q ( ) 【- ，y ) 。如果线段q ；q j ( i j ，1 i n ，1 j n ，3 n + 一) 总不在多 边形q 外，则称q 为凸多边形 定义2 设二维点集s = p - ( x ，y 。) l l i m ，3 m 一 由给定平面内 的点构成。如果凸多边形q 顶点q i s ，且q 是可覆盖s 中各点的最小凸多边 形；则称凸多边形q 为二维点集s 的凸壳 定义3 如何寻求给定二维点集s = p 。( x 。，y t ) l l i m ，3 m + 一l 的二 维凸壳，称为二维凸壳问题。 定义4 凡能构造性生成给定二维点集s = p ；( x ，y 1 ) 1 1 i m ， 3 m 一) s = f p 。( x j ，y 。) 1 1 i m ，3 m 一) 的二维凸壳的算法，统称二维凸壳生 成算法 二维凸壳问题几何原型，可简单的形象说明如图1 1 所示：对1 i m ， 在木板的点集中各点p ( x j ，y 。) 处分别钉1 个图钉，再用一条橡皮带从外沿围 绕这些图钉。显然有：首先，被缠紧的橡皮带必构成凸多边形q ：其次，所有 图钉总不在该橡皮带( 即：凸多边形q ) 所围成的区域之外。 9 同构化二维点集凸壳算法研究 o q ) 木版t 所钉备十圈钉町外圈缠绕各图钉的皮帚 围1 1二维凸壳问题几何原型的形象说明示意田 s 2 现有凸壳算法介绍 2 现有凸壳算法介绍 2 1 卷包裹凸壳算法 2 1 算法描述 2 0 世纪提出的凸壳问题，其算法研究始于7 0 年代、盛于8 0 年代、极于 9 0 年代；然而，进入2 1 世纪以来，传统的凸壳算法研究出现了停滞不前的尴 尬窘况。1 9 7 0 年d c h a n d 和s k a p u r 提出较有代表性的卷包裹凸壳算法“”， 如图2 所示。其算法思想可概括为：先取二维有限点集s 的点p ( x ，y ) ，使 y - ：i i i i n y ，il i m ，3 m + 一 ；显然，点p 就是凸壳q 的初始顶点q ，( 即 第1 个顶点) ：过点q 一画一水平直线l 。然后使l 改绕顶点q 按逆时针方向旋 转若干个转角a ，可碰到s 中的第2 个点p 2 ；而点p ：就是凸壳q 的第2 个顶 点q ：，且线段q q ：就是凸壳q 的第2 个边。继续旋转下去，最后直线l 旋转 3 6 0 度回到初始顶点q 。便得到所要求的凸壳。( 如图2 1 所示) 算法( 卷包裹算法) 图2 1卷包裹凸壳算法示意田 同构化二维点集凸壳算法研究 输入：平面点集s 上n 个点q ，q 2 ，q _ 的坐标“，乃) ，f ：历 输出：点集 a ，q 2 ，q 的凸壳顶点 第1 步计算咒，见，只的最小值，其对应的点设为p 1 第2 步从p - 向右引一水平射线，记为屯 第3 步计算q l q ；与乞的夹角a n g l e ( q , q i ，乞) 及 m i na n g l e ( q q ，k ) ，2 2 一，设为q 。么是角岛的一条边，q 的另一 条边的端点是凸壳顶点，记为q 2 第4 步- 卜一，七卜3 ，肼卜2 。 第5 步以g g + 代替q 1 锡( 瓦西= k ) ，计算岛g + 。与g + q ( 卢七，“) 的夹角a n g l e ( q i + 。q ，g 锡+ ，) 及m i a na n g l e ( q + q ，岛g + ) ，设为口- 的 另一条边的端点即凸壳顶点记为见。 第6 步，卜，+ 1 七卜七+ 1 ，历卜册+ 1 g o t o 第5 步，直至 的另一条边的端点为q i 第7 步输出凸壳顶点q i ，q 2 ，q - 在算法中，第1 步耗费n - 1 次比较，第2 步中画水平线l 只需要常数时 问，第3 步需要计算夹角n 一1 次，然后耗费n 一2 次比较可以求得嵋。第4 步 至第6 步循环n 一2 次，每次循环需要计算夹角n - i 1 次，比较n i 一2 次， i 2 1 ，万一2 。第7 步耗费常数时间。因此，算法需要计算夹角的次数为： 月一1 + z ( n i 一1 ) o ( n 2 ) i - ! 比较次数： 开一2 + e ( n i 一2 ) o ( n 2 ) 2 现有凸壳算法介绍 所以算法的时间复杂度为d ( 一2 ) 2 1 2 卷包裹凸壳算法的弱点 显然。卷包裹凸壳算法仅可无误差地确定其初始顶点q 。而对其它顶点q 。 的确定都可能存在误差( 即：其凸壳精度、算法效率都取决于它每次逆时针 方向旋转时的固定转角) 。所以，它只是近似算法，并有两个主要缺点：第一、 若该转角设定过小，则凸壳精度较高但算法效率偏低；反之，若该转角设定 过大，则凸壳算法效率较高而精度偏低。第二、它只能进行串行计算，而不 利并行化，因为其凸壳当前顶点q 。依赖前一项点q 。但它较真实地反映了凸 壳的自然态同构化特点，是图1 橡皮带外绕法的朴素模拟圈绕与计算机实现 2 2 格雷厄姆凸壳算法 2 2 1 算法描述 1 9 7 2 年，g r a h a m 在“a na f f i c i e n ta l g o r i t h mf o rd e t e r m i n i n gt h ec o n v e x 嘶1 lo faf i n i t ep l a n a rs e t ”一文中提出格雷厄姆凸壳算法其算法思想 可概括为： 第0 步：任取点集s 的内点p o 作为坐标原点0 。 第1 步：求点集s 中的各点相对于轴o x 的倾角l p o x ：按其倾角么p 。o x ， 升序捧列点集s 中其余各点，并仍记之为p i 。其中，1 i m 3 。 第i 步：删除格雷厄姆三角形q 0 q 的所有内点并记之为点p 。即如图 2 2 所示，如果某点p 。不是凸壳顶点，则它必为位于原点0 与凸壳最邻近的 两个项点q 、q 。所成格雷厄姆三角形q 0 q 。的内点，故删除这些内点p 。其 中，2 i n - i 。 第1 r l 步：删除格雷厄姆三角形q o q ，的所有内点p 同构化二维点集凸壳算法研究 圈2 2 格雷厄姆三角形示意田 由于每个顶点之多被删去一次，删去的顶点的个数也不可能超过n ，因此 在第i 步需要线性时间。在第l 步中要计算n 1 个夹角并按夹角分类，计 算每个夹角只需要常数时间，计算n 一1 个夹角耗费线性时间，分类需要 o ( n l o g n ) 因此格雷厄姆算法的时间复杂度为o ( n l o g n ) 2 2 2 格雷厄姆凸壳算法的弱点 显然，格雷厄姆凸壳算法存在三个主要缺点：第一、凸壳的初始顶点q - 与其倾角p ，o x 并无必然直接联系故确定其初始项点q ，的处理效率较低。 第二、格雷厄姆三角形内点的判定，是制该算法效率提高的瓶颈。第三，它 只能进行串行计算，而不利并行化，因为其凸壳当前顶点q 。依赖前一顶 点q 2 3 折半分治凸壳算法 2 3 1 算法描述 p r e p a r a t a 和h o n g 把分治技术首先应用于凸壳问耐朔。基于分治技术与 递归方法的折半分治凸壳算法的算法效率高于卷包裹凸壳算法、格雷厄姆凸 壳算法。 折半分治凸壳算法的算法思想，可简述如下： 1 4 2 现有凸壳算法介绍 第0 步：使初始二维点集s 的点只囟，满足x l x 。，其中1 i m - 1 ， 3 皿 i p p + l ，则删去n ) ，得到一个顶点序列，将这个顶点序列可以 记为岛，儿，以，依次连接这些点，便可以得到一个多边形a 是凸壳边界 b c h ( s ) 的起点，见与见也必是凸壳的顶点 第l 步：判定一( f = 丽) 的凹凸性 第2 步：对于所有的凹顶点序列吼，q 2 ，吼将每个序列两端的凸顶点9 1 ，靠连 接，删去q 。，“之间的凹顶点，并将吼，“记为新顶点，然后重新判定吼， “的凸凹性 第3 步：如果新顶点中仍然有凹顶点，则重复第1 步、第2 步中的操作，直到新 顶点中没有凹顶点为止 第4 步：设由以上四步得出顶点序列为a ，p ：，n 。，儿，输出 2 4 2 算法分析 定理l 上述算法中第o 步所产生的顶点a ，见，儿依次连接所形成的多边形p 1 7 同构化二维点集凸壳算法研究 为简单多边形( 如图2 4 所示) 田2 4 定理1 的示意图 证明：由上述算法中第o 步的描述可知由p j 出发的n - l 条射线p i p 2 ，a 见，a 几 将平面分为n - 1 个域，多边形p 的边岛见，p 3 p 4 ，n 一。见位于前( n 2 ) 个域中。故 多边形p 的边 见，p 2 p 3 ，岛儿，p , - i ，p n p j 两两互不相交。p 为简单多边形 定理2 给定任意一个简单多边形p ，一个凸多边形，设p 的顶点均为p 的 顶点，且p 包含p 的所有顶点，则，是p 的顶点集s 的凸壳边界 证明：假设p 不是p 的凸壳边界，则设p 的凸壳i 2 2 雕j b c h ( s ) ，由于p 的顶点 集包含p 的顶点集s ，而b c h ( s ) = p ，故是包含s 的最小凸多边形，p = b c h ( s ) ，p 为p 的顶点集s 的凸壳边界。 定理3 上述算法中第2 步，在每次执行第2 步时，设未执行时顶点数目为( - 0 ， 则执行第2 步后至多有【詈j + 1 个需要重新判定凹凸性的顶点 证明：设在未执行第2 步时凸顶点数为c ，凹顶点数为c 。 情况1 ：若c c 斟以引 则执行第2 步后产生至多【詈j + 1 个需要重新判定凹凸性的顶点 s 2 现有凸壳算法介绍 情况2 ：若c s c 即c s 【