凸壳算法实验报告

A. 在python如何实现TIN中凸壳生成算法

修改config-extensions.def ，在末尾添加如下内容，然后保存退出：
[ClearWindow]
enable=1
enable_editor=0
enable_shell=1
[ClearWindow_cfgBindings]
clear-window=<Control-Key-;>
打开Python的IDLE，options选项中就可以看到增加了Clear shell window ctrl+;。
在IDLE输入代码，然后按Ctrl+;（是指Ctrl和;），发现刚输入代码可以被清除了。

B. 王晓东的人物简介

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

C. 王晓东的人物简介

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

D. 周培德算法

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

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