计算几何是计算机算法研究领域中一个重要部分，而凸壳是计算几何中最普遍、最基本的一种结构，它被广泛地应用在模式识别、图象处理、图形学和人工智能等方面，在实际应用过程中，许多问题都可以转化成凸壳问题来加以解决。作为多年来计算机研究领域的热点问题，目前已有不少凸壳算法，但随着实际问题所涉及的信息量不断增长，并且传统凸壳算法在处理海量数据方面不能满足用户的需要，因此本文将寻求一种新的基于海量数据的凸壳算法。　　 作为解决各领域问题的基本方法，凸壳算法为高性能应用系统的研究与实现提供了稳健的基础算法。基本算法是研究问题的基础，基本算法的优劣直接关系整个应用程序运行效率。不同的算法有不同的应用环境，常用的传统凸壳基本算法总的来说都不适合海量数据情况下使用，为此提出了一个易于实现的新凸壳算法-金字塔算法。快速优化算法是高性能凸壳算法的核心技术，旨在通过剔除海量数据中的更多无需参加遍历运算的内点，来提高海量数据的凸壳求取处理能力。目前国内外凸壳基本算法的研究主要集中在预先对数据进行排序的凸壳算法方面，而对基于无序海量数据的凸壳算法研究较少，将快速优化算法应用于无序的凸壳算法研究就更少，使得这方面研究进展一直微乎其微。而本文正是着眼于海量数据凸壳算法的研究，其目标是从海量数据自身特征及实际运算应用需求出发，提出一套海量数据凸壳基本算法和在此基础上的快速优化运算策略及应用机制，以实现在无序的平面点集环境下海量数据凸壳的高效求取。　　 本文按照算法分析理论原则，对金字塔算法及其三种快速优化算法进行了详细的阐述与理论分析。首先从算法的构建基础、算法的基本思想和算法的正确性分析，再到算法实现步骤的设计，最后结合实际运行数据，讨论算法的时间复杂度以及与其它凸壳算法执行效率的对比分析。本文工作主要从以下四个方面展开：　　 (1)金字塔算法的提出　　 经典格雷厄姆扫描法在凸壳生成过程中不断有回溯过程出现，这是该算法在实际运行中的重要瓶颈。为了避免回溯过程的出现，可以通过回溯法的逆算法，分枝-限界方法来加以解决，进而提出一种新凸壳算法。该算法首先找出点集S中的最左最右的2个凸壳顶点，然后分别沿着顺时针和逆时针方向找出斜率最大和最小点。寻找到的这2个点必是凸壳顶点，再以这2点为起点循环下去，好像搭建金字塔一样，一层一层构建出点集S的凸壳边界BCH(S)。　　 (2)应用动态塔尖快速遍历算法对新算法的改进　　 金字塔凸壳算法每次查找新顶点都要进行n次遍历，如果预先删除不可能是凸壳顶点的内点，则将大幅度提高算法运行效率。应用金字塔算法建立凸壳时，每次将生成两个新凸壳顶点，通过证明可以知道位于这两个点连线下方的点必定是凸包内点，可将其剔除。下一次在生成新凸包顶点时，就不必再进行n次比较，只需在剩余点中判断即可，从而减少搜索新顶点时点判定次数。这种算法实现比较简单，只需计算一个行列式即可剔除不可能成为凸包顶点的内点。　　 (3)与以往的快速优化算法的结合　　 通过对金字塔凸壳算法的分析可知，要提高算法的时间效率，可从两方面入手：一是减少单次点集遍历次数n；二是减少凸包顶点个数h。传统快速凸壳求取算法是使用一种简单的方法找到一个凸包的边界，而被这个边界所包围的点不可能成为最终凸包的顶点，这样就可将这部分内点剔除出去，来达到减少单次点集遍历次数n的目的，进而提高基本算法执行效率。本文结合金字塔算法自身特点，将上述的传统快速凸壳算法改造成适应本算法的初始近似凸壳算法。点集分组算法则是从减少凸包顶点个数h角度提高执行效率的，将其与金字塔算法相结合，同样可以达到进一步优化金字塔算法的目的。通过与这两种快速算的结合，金字塔算法的时间效率提高了25～43倍。　　 (4)金字塔算法与传统算法时间复杂度的比对分析　　 根据金字塔算法的基本原理和实现步骤可知，每找到一个顶点都需要遍历n次，若顶点个数为h则算法的时间复杂度为O(hn)。根据凸壳顶点与内点关系定理可知，实际应用当中凸壳顶点个数远远小于内点个数，所以在平面海量数据的凸壳求解过程中执行时间主要取决于n的数值。与动态塔尖快速遍历算法结合后，金字塔算法的时间复杂度提升为O(1/4hn)。为了便于对比，本文介绍两种传统的凸壳算法，并且两者都是基于无序点集的，一种是卷包裹法，其时间复杂度为O(n2)，另一种是增点递推法，其时间复杂度为O(2hn)。本文通过大量的实验对比也证明金字塔算法的时间效率高于上述两种同是基于无序的凸壳算法。　　 论文中的算法取得了如下结果：　　 (1)金字塔算法的思想比较简洁易于实现，并且容易与快速算法相结合，达到进一步提高运算效率的目的。　　 (2)对动态塔尖快速遍历算法，只需在塔尖区域上的点集中进行凸壳顶点查找运算，大大减少了实际处理过程中参加运算点的个数，提高了算法执行速度。　　 (3)利用行列式能确定点与线位置关系的性质，回避了通过计算斜率最值来确定凸包顶点，并且避免了生成不正确凸壳和有漏点现象的出现。　　 (4)初始近似凸壳算法以往确定近似凸包的边界时极点越多优化效率越高，但与动态塔尖快速遍历算法相结合时，4个极值点组成的四边形作为初始凸壳效率最佳。