算法技术手册（原书第2 版）

计算几何

｜

239

计算几何

为了避免平凡解，我们假设

|

P

|

≥

3

，而且不存在过于接近的两个点。如果两个点太过接

近，而且其中一个点属于凸包，那么

凸包扫描

算法将会错误地选择一个无效的凸包点（或

者抛弃一个有效的凸包点），但是考虑到两点过于接近，这种错误可以忽略不计。

9.3.2 使用环境

凸包扫描

算法只需要一些最基本的操作（如乘法和除法），因此比另外一种凸包算法

GrahamScan

（

Graham

，

1972

）要简单得多，这是因为该算法需要使用第

3

章证明过的

三角恒等式。由于

凸包扫描

算法并不采用递归，所以它可以处理大规模的数据。

如果输入的点均匀分布，那么可以使用

桶排序

，在

O

(

n

)

的时间内将点排好序，算法最后

的总体性能也是

O

(

n

)

，这种实现是最快的。但是如果没有点集的分布信息，那么可以使

用

堆排序

来将排序的性能限制在

O(

n

log

n

)

。这些实现的代码都可以在代码库中找到。

9.3.3 解决方案

例

9-1

的代码展示了

凸包扫描

算法如何计算上凸包。最后的凸包是需要合并上下两个凸

包。

例

9-1

：凸包扫描算法

public class ConvexHullScan implements IConvexHull {

public IPoint[] compute(IPoint[] points) {

//

排序

x

坐标，如果

x

坐标相等，排序

y

坐标。

int n = points.length;

new HeapSort<IPoint>().sort(points, 0, n - 1, IPoint.xy_sorter); ...