计算几何
241
计算几何
9.3.4 算法分析
我们在单位正方形内随机生成的二维点集上进行了
100
次实验,并且去掉了最好和最坏
的结果。表
9-2
所示为剩余
98
次实验的平均结果。这张表也展示了平均时间中,有多少
时间花费在启发式函数的计算上,可以很明显地看到
凸包扫描
算法最为高效。
随着输入数据规模的增长,越来越多(几乎有一半)的点被启发式函数删掉。而更令人
惊讶的是,规模如此之大的点集,却只需要如此之少的点便可组成凸包。表
9-2
的第2
列证明了
Preparata
Shamos
的论断
1985
他们认为构成凸包的点个数应该为
O(log
n
)
这是非常令人吃惊的结论。当然,点的分布情况也很重要:如果选择在一个单位圆内平
均分布的点集,那么凸包将会包含大概
n
的立方根个点。
9
-
2
:实验的结果
凸包中的 计算的 删除掉的 函数计算的 函数算法的
n
/ 平均点个数 平均时间 /ms 点的平均个数 / 平均时间 /ms 平均执行时间 /ms
4,096 21.65 8.95 2,023 1.59 4.46
8,192 24.1 18.98 4,145 2.39 8.59
16,384 25.82 41.44 8,216 6.88 21.71
32,768 27.64 93.46 15,687 14.47 48.92
65,536 28.9 218.24 33,112 33.31 109.74
131,072 32.02 513.03 65,289 76.36 254.92
262,144 33.08 1168.77 129,724 162.94 558.47
524,288 35.09 2617.53 265,982 331.78 1159.72
1,048,576 36.25 5802.36 512,244 694 2524.30
凸包扫描
算法的第一步是使用标准的基于比较的排序方法,其性能费用为
O(
n
log
n
)
。计算
上凸包的
for
循环需要处理
n
2
个点。内部的
while
循环最多也只会执行
n
2
次,
计算下凸包也如此。因此,
凸包扫描
算法其余步骤的总时间是
O
(
n
)
但是当
凸包扫描
算法计算叉积时,可能会出现浮点运算的误差。因此
PartialHull
cp
<
δ
而不是
cp
< 0
,这里
δ
10
9
9.3.5 衍生算法
如果输入的点是有序的,那么
凸包扫描
算法的排序步骤可以过。在这种情况下
凸包
扫描
算法的性能可达
O
(
n
)
。如果输入的点是均匀分布的,那么可以使用
桶排序
(详见
第4章),也能够
O
(
n
)
的性能。另一种计算凸包的衍生算法是
QuickHull
Eddy,
242
9
1977
),它受到
快速排序
的启发使用分治思想,能够在
O
(
n
)
的时间内完成均匀分布
点集的凸包计算。
最后我们还要讨论另一类衍生算法。
凸包扫描
算法在构建上凸包时,并不是真正地需要
一个有序的数组,它仅仅是按照
x
坐标小到大的顺序遍历
P
所有点。所以我们可
以使用二叉堆来存储
P
,并且只需要重复地从堆中删除最小的元素即可。如果使用链表
来存储删除的点,那么可以很容易地从链表中以逆序的方式将这些点重新加回去。这类
衍生算法的代码(在图
9-5
中标记为堆)可以在本书的代码库中找到。
9-5:凸包衍生算法的性能
9-5
给出了两种不同的数据分布情况下算法的性能:
环形分布
在一个单位圆上均匀分布着
n
个点。所有这些点都属于凸包,所以这是一种极端情况。
计算几何
243
计算几何
均匀分布
n
个点均匀分布在一个单位正方形上,随着
n
的增长,只有越来越少的点最终会能
够构成凸包,所以这也是一种极端情况。
这一系列实验使用数据的规模
n
512-131 072
,并且呈两种形式分布这里采用了两个
不同的实现版本:例
9-2
的实现和代码库中的实现。这里没有采用
Akl-Toussaint
启发式
函数。对于每个数据集,我们会进行
100
次实验,然后掉最好的结果和最坏的结果。
9-5
是剩余
98
次的平均结果(单位为
ms
)。在使用基于比较的排序方法时,使用平
衡二叉树的实现版本表现出了最好的性能。而在输入是均匀分布时,
桶排序
的实现效率
最高。一般情况下,计算凸包所花费的时间是
O(
n
log
n
)
但是,如果输入数据的偏差较,那么这些实现的性能将会退化得非常严重。假设点集
P
包含
n
个点,其中两个是
(0, 0)
(1, 1)
,然后剩余
n
2
个点围绕着两个点聚合成
两个簇,簇之间的距离为
0.502
。这份数据是为了应对
桶排序
而设计的。表
9-3
展示了依
赖于
插入排序
桶排序
是如何退化到
O
(
n
2
)
的性能的。
凸包可以扩展到三维或者更高的维度。不幸的是,在更高的维度,实现会变得更为复杂。
9
-
3
对偏差较大数据的不同实现的比较
n
/ 凸包扫描 平衡二叉树 桶排序
512 0.28 0.35 0.33 1.01
1024 0.31 0.38 0.41 3.30
2048 0.73 0.81 0.69 13.54
Melkman
1987
)提出了一个算法,它能够在
O
(
n
)
的时间为一个简单多边形或者折线
计算出凸包。其思想非常简单,它利用多边形自身点的有序排列这个信息避免了对初始
数据进行排序。
如果数据集是动态变化的,那么使用
Overmars
van Leeuwen
1981
)的方法可以高效
地维护已经计算好的凸包。凸包点存储在一个支持插入和删除的树结构中。插入或者删
除的费用
O
(log
2
n
)
,所以构建凸包的时间复杂度是
O
(
n
log
2
n
)
,空间复杂度为
O
(
n
)
结果有力地支持了这样一种观点:正确地取舍能够有效改善算法的性能。
GrahamScan
是最早出现(
1972
年)的凸包算法,它需要用到简单的三角函数性质
我们已经在第
3
章中讨论过该算法。使用之前提过的行列式计算,我们可以只需要简单
的数据结构和基本的数学计算就能够完成算法实现。
GrahamScan
首先将所有点按照和
最左下方的点
s
的夹角进行排序,它能在
O(
n
log
n
)
的时间内计算出凸包。唯一有挑战
的地方是需要在排序时,如果遇到夹角相同的点,那么需要检查它们与点
s
的距离。

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.