凸壳算法代码

① 王晓东的人物简介

职称 教授
职务 博士生导师
主讲课程 算法与数据结构、算法设计与分析、文献阅读与选题报告
研究方向 计算机算法设计与算法评价、并行和分布式算法设计、计算复杂性理论等
1998年任福州大学计算机系主任。2003年任福州大学数学与计算机学院院长、博士生导师。2007年8月起任泉州师范学院副院长(副厅)。现任福建省计算机学会理事长、中国计算机学会理事、福州大学一级责任教授、福州大学计算机应用技术省重点学科学科带头人。先后主持了国家自然科学基金项目、国家优秀留学回国人员基金项目、福建省杰出人才基金项目和省自然科学基金项目等8个研究课题，获得国家科技进步二等奖1项，省科技进步二等奖3项；主持国家精品课程算法与数据结构和算法设计与分析的课程建设。2008年被评为福建省教学名师，获福建省教学成果一等奖等。在国内外重要学术刊物上发表有创见性的论文50余篇；在算法复杂性研究方面取得了一系列理论研究和应用成果。例如，在对着名的凸壳问题的计算复杂性研究成果中推广了关于判定树模型下问题的计算复杂性下界着名的Ben-Or定理，并应用于分析凸壳问题的计算复杂性，在较一般的情况下改进和完善了国际算法界知名学者Aggarwal，Steele和Yao等提出的关于凸壳问题计算复杂性下界的结果，研究成果得到同行专家的好评并被国内权威刊物所引用。正式出版与算法设计与分析、数据结构相关的学术着作和教材11部，其中4部为普通高等教育“十一五”国家级规划教材，《算法设计与分析》被国内多所大学和科研机构列为博、硕士生入学考试指定教材。

② 周培德算法

平面点集三角剖分的周培德算法是周培德于1996提出的(周培德，1996，2000)，该算法首先对点集逐层求凸包，如图3.8(a)所示为需要剖分的点集，图3.8(b)为对点集逐层求凸包，对点集逐层求凸包时可能存在1个或2个孤立点无法组成凸包，此时恰好没有剩下孤立的点;然后将两两凸包之间的环状区域分割成三角形，最后调整相邻环域的三角剖分便能获得最小权的三角剖分，如图3.8(c)为从内到外将凸包之间的环状区域分割成三角形，图3.8(d)为点集的三角剖分结果。

第十三步:对以C_m中的边(或已变动的边)为共用边的三角形对，采用第十二步的方法检查是否需要改变原有的三角剖分。然后，沿C_m-1，…，C₂的各条边(或已变动的边)寻找两个有共用边的三角形对，并用第十二步的方法检查是否需要改变原来的三角剖分，直到所有凸壳的边检查完为止。

③ 贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。

3.2.2.1 贪心算法1

第一步:设置一个记录三角剖分中边的数组T。

第二步:计算点集S中所有点对之间的距离d(p_i，p_j)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d₁，d₂，…，d_n(n-1)/2，相应的线段记为e₁，e₂，…，e_n(n-1)/2，将这些线段存储在数组E中。

第三步:从线段集E中取出长度最短的边e₁存到T中作为三角剖分的第一条边，此时k=1。

第四步:依次从E中取出长度最短的边e_k，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除e_k。这一步运行到S中没有边为止，即至k=n(n-1)/2。

第五步:输出T。

该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n²lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n³)。

3.2.2.2 贪心算法2

第一步:求点集的凸壳，设凸壳顶点为p₁，p₂，…，p_m，凸壳的边为e₁，e₂，…，e_m。并将凸壳顶点按顺序连接成边的e_i加入T(三角剖分的边集合)，并且e_i的权值被赋为1。凸壳内点的集合为S₁={p_m+1，p_m+2，…，p_n}。

第二步:从内部点S₁中任取一点p_i，求与p_i距离最近的点p_j，将线段 存入T。

第三步:求与p_j距离最近的点(除点p_i外)，设为p_k，并将线段 加入T，并将这些边的权值设为1，而w_ij、w_jk和w_ki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。

第五步:对权值为1的边(除e₁，e₂，…，e_m外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。

第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e₁，e₂，…，e_m外)。

贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求p_k要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)