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

284

■

9

章 計算幾何学

する。言い換えると、

x

座標の最も小さい点である。そのような点が複数ある場合は、

y

座標の最も小さい点を選ぶ。

n

個の点が与えられると、

C(n, 3)

、すなわち

n*(n

−

1)*(n

−

2)/6

個の異なる三

角形ができる。点

p

i

∈

P

が、

P

内の他の異なる

3

点が構成する三角形の内部に含ま

れているなら、凸包を構成する要素にはなりえない。例えば、図 9-1の点

p

6

は、

p

4

,

p

7

, p

8

の作る三角形により排除される。各三角形

T

i

について、力任せの

遅い凸包

（

Slow Hull

）アルゴリズムで残りの

n

−

3

個の点のいずれかが

T

i

の内部にあるか確

かめて、凸包の候補から取り除くことができる。

凸包の点がわかったなら、左端の点を

L

0

とラベル付けして、

L

0

を通る垂線との角

度で、他のすべての点を整列することができる。凸包の任意の

3

点列

L

i

, L

i

＋

1

, L

i

＋

2

は、右回りになる。この性質が

L

h

-2

, L

h

-1

, L

0

についても成り立つことに注意する。

この非効率な方式は、

O(n

4

)

回の三角形の検出ステップが必要になる。次に、凸

包を計算する、効率的な

凸包走査

（

Convex Hull Scan

）アルゴリズムを提示する。

図9-1　平面上の点集合とその凸包を描いた例

9.3

 凸包走査

Andrew

によって発明（

1979

）された

凸包走査

は、問題を、上側の凸包部分の構

築と下側の凸包部分の構築とに分割する。最初に、全点を

x

座標で整列する。

x

座

標が同じなら

y

座標で整列する。上の凸包部分は、

P

の左端の

2