計算幾何(4)

問) ある多角形の頂点列 Point[0],Point[1],…,Point[N-1]が与えられたときに、この多角形が凸多角形であるかどうかを判定するアルゴリズムを示せ。


但し、ここで言う凸多角形とはその内角がすべて180゜以下*1とする。



与えられた点を全て内包する最もタイトな(小さな)凸多角形を(点集合の)凸包と呼ぶ。凸包の示す領域とは要するに凸多角形の内側の領域である。凸包は交差判定などがしやすいので計算幾何で頻繁に問題になる。


コンピュータグラフィックスの世界でも、ポリゴンにテクスチャを貼り付けて描画するときにたいていの3Dシステムは転送元テクスチャの領域および転送先スクリーンの領域とは共に与えた頂点集合の凸包に制限される。よって凸包について正しく理解しておくことは非常に重要だ。


答)
id:yaneurao:20070118で用意したCCW関数(robustなarg関数)を用いれば、例えば以下のように書ける。



/// <summary>
/// 多角形の頂点列を与えて、それが凸多角形かどうかを判定する。
/// </summary>
/// <param name="a"></param>
/// <returns></returns>
public static bool IsConvex(Point[] a)
{
int N = a.Length;
bool[] b = new bool[3];
for (int i = 0; i < N; ++i)
{
// CCWは-1,0,1しか返さない。
// ループの最中にCCWが-1とを返した場合にのみfalse
b[CCW(a[i], a[(i + 1) % N], a[(i + 2) % N]) + 1] = true;

if (b[0] && b[2])
return false;
}

// return !(b[0] && b[2]);
return true;
}

上記のプログラムではループ中で凸包でないとわかった時点でfalseを返すようにしてあるが、これは高速化のためで、コンパイラが利口であればこの処理は明示的に書かずとも関数末尾に単にreturn !(b[0] && b[2]); と書けば良い。

*1:ここを「180゜未満」とする定義する場合もあるが180゜を含めておいたほうが都合が良いので180゜も含める