計算幾何(3)

program

まずはウォーミングアップから。


問)
平面上の与えられた三点 a, b, c を a → b → c と進むときに時計回りになるか反時計まわりになるかを判定するアルゴリズムを示せ。ただし、時計回り、反時計まわりと言うときの座標系はx軸の正方向を右、y軸の正方向を上方向にとるものとする。


解説)
これはa,bを通る直線に対して、cがその直線の正領域にあるか負領域にあるのかを判定する問題であり、基本中の基本である。


答)
(b-a)×(c-a)の符号で判定すれば良い。この × は外積。


以下、サンプルコード。



// CCW(CounterClockwise:反時計回り)であるかの判定を行なう。

// +1 : 反時計まわり

// -1 : 時計まわり

// 0  : 3点が同一直線上にある。

public static int CCW(Point a, Point b, Point c)

{

    return global.System.Math.Sign( (b-a).Cross(c-a) );

}

これはrobustなarg関数として用いることが出来る。