凸包算法的加速与改进研究

作     者：郝晓军 

作者单位：河北工业大学 

学位级别：硕士

导师姓名：沈西挺

授予年度：2003年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：凸包 加速 边界 加速权值 

摘      要：本文的主要内容是对凸包的算法进行改进。凸包的经典算法把凸包问题和分类问题联系在一起，如：Graham算法和快速凸包算法等，优点是在任何情况尤其在最坏的情况下（所有的点都是凸包的顶点），得到点集的凸包计算都有一个最优的时间复杂度O（nlogn），其它的一些算法如：jarvis行进算法，它不是基于排序，有些时候复杂度能够小于O（nlogn），但是在最坏的情况下复杂度却是O（n）。根据统计表明，在一般的情况下点集的点并不都是凸包的顶点，这时候，传统的经典算法的复杂度也是O（nlogn）。本文在研究了计算几何的基本规律的基础上，分析了传统的凸包算法的优缺点，同时提出了一个新的方法对于一般情况下的凸包的算法进行了加速和优化，它在一般的情况下工作得很好，对于最坏的情况，也没有增加运算的复杂度。 加速算法的思想是这样的，对于一个凸包，算法真正关心的是它的边界上的点，其它的点实际上是不需参与运算的，但是在传统的算法中，所有的点都要参加运算，这就会浪费一些不必要的时间。加速算法能够使用简单的方法找到一个凸包的边界，这个边界被真正的凸包所包围，而凸包的大部分点都被这个边界所包围，并且可以知道这些点不可能成为最后凸包的顶点，然后再使用较少(远远小于O（nlogn）)的时间去掉这些点。另外，根据研究，绝大多数的点集都服从均匀分布和正态分布，所以在求取边界的过程中，本文对这两种分布的边界求法进行了优化，得到了一个加速凸包算法的两种分布情况下的合理权值。然后利用加速后凸包的点被分成了若干个有序的小部分的特点，对传统的凸包算法中主要的时间消耗部分—排序部分，做了改进，进一步优化了算法。使得算法的时间复杂度的期望值是O（n），而对于最坏的情况下，它的复杂度并没有增加，依然是O（nlogn）。