アルゴリズムクイックリファレンス 第2版

9.3

 凸包走査

■

287

帰的ではないから、多数の点集合を処理できる。

最速の実装は、入力集合が一様に分布しており、それによって

バケツソート

を用

いて

O(n)

で整列できるときで、結果としての性能も

O(n)

となる。そうでない場合

は、

ヒープソート

を使って、初期の点をソートするのに

O(n log n)

振る舞いが達成

できる。ここに述べた実装でベンチマークを取ったものは、コードリポジトリから

入手できる

＊

1

。

9.3.3

 解

例9-1に、

凸包走査

がどのようにして最初に上側部分凸包を計算し、方向を反転

して、下側部分凸包を計算するかを示す。最後にできる凸包は、

2

つの部分凸包の

結合だ。

例

9-1

 凸包走査による凸包解

public class ConvexHullScan implements IConvexHull {

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

// x

座標で整列する（

==

なら、

y

座標で）。

int n = points.length;

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

if (n < 3) { return points; }

//

左端の

2

点から始めて凸包の上側を計算する

PartialHull upper = new PartialHull(points[0], points[1]);

for (int i = 2; i < n; i++) ...