如果输入的点是已知有序,那么凸包扫描算法的排序步骤可以跳过,在这种情况下,凸包扫描算法的性能是O(n)。如果输入的点是均匀分布的,那么我们可以使用桶排序(详见第4章“桶排序”),也能够得到O(n)的性能。另一种计算凸包的变种是QuickHull(Preparata和Shamos,1985),受到快速排序的启发,使用分治思想计算凸包。
最后我们还要讨论另一类变种。我们已经讨论过,凸包扫描算法在构建上部凸包时,并不是真正地需要一个有序的数组,它仅仅是从x坐标最小到最大,遍历P中所有的点。如果我们使用二叉堆来存储P,那么我们只需要重复地从堆中删除最小的元素即可。如果使用链表来存储删除的点,那么这些点可以轻易地从链表中以逆序的方式回滚。这类变种的代码(在图9-12中标记为堆)在本书的代码库中可以找到。
图 9-12 凸包变种的性能图9-12的性能结果基于以下三种数据。
环数据
在一个单位圆上均匀分布着n个点。所有这些点都属于凸包,所以这是一种极端情况。
均衡数据
n个点均匀分布在一个单位正方形上,随着n的增长,这些点会只有越来越少的部分属于凸包,所以这也是一种极端情况。
不平衡数据
n个点在平面上是非均匀分布的,而且n-2个点集中在0.502的左边一小部分簇中。数据集也会包括(0,0)和(1,0)。这个数据集的构建目的是使桶排序不能发挥作用。
我们将会进行一系列的实验,数据集的规模n从512~131 072[1],并且数据有两种形式的分布,而且采用了两种不同的实现:例9-2的实现和代码库中的实现。我们同时会使用堆排序来简单地对这些点排序,其性能结果作为比较的基准。我们不会采用Akl-Toussaint启发式函数。对于每个数据集,我们会进行100次的实验,然后抛弃最好和最坏的结果。图9-12的是剩余98次的平均结果(单位为毫秒)。我们可以清楚地看到排序和计算凸包之间的关系。在使用基于比较的排序方法中,性能表现最好的实现采用的是平衡二叉树。仅仅在输入是均匀分布时,使用桶排序的实现效率最高。一般情况下,计算凸包所花费的时间是O(n log n)。
凸包可以扩展到三维或者更高的维度。但是很不幸的是,在更高的维度,实现的复杂性大大提高。
Melkman(1987)提出了一个算法,能够在O(n)的时间为一个简单多边形或者折线计算出凸包。它不会对初始数据进行排序,但是会利用多边形自身点的有序排列这个信息。
[1]我们将不平衡数据集的规模限制在2048,因为桶排序很快会退化到O(n2)的性能。