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

48

■

3

章 アルゴリズムの構成要素

public int compare(IPoint one, IPoint two) {

if (one == two) { return 0; }

// atan2

関数を使って両者の角度を計算する。

// one.y

が常に

base.y

以上なのでうまくいく。

double oneY = one.getY();

double twoY = two.getY();

double oneAngle = Math.atan2(oneY - baseY, one.getX() - baseX);

double twoAngle = Math.atan2(twoY - baseY, two.getX() - baseX);

if (oneAngle > twoAngle) { return -1; }

e

lse if (oneAngle < twoAngle) { return +1; }

//

同じ角度なら、大きさの降順にして凸包アルゴリズムが

//

正しくなるようにする。

if (oneY > twoY) { return -1; }

else if (oneY < twoY) { return +1; }

return 0;

}

}

n

＞

2

のすべての点が共線（同一直線上）なら、その特別な場合には、凸包は集合

内の

2

つの端点で構成される。計算された凸包には、共線の点が含まれるかもしれ

ないが、それを除く特別な処理は含んでいない。

3.5.5

 分析