計算幾何(1)

問) 2次元上のN多角形(Nは自然数)の頂点列が与えられたとき、その頂点列が右回りか左回りか判定するアルゴリズムを示せ。ただし多角形はねじれてはいないものとするが、すべてが同じ点であることは有り得るものとする。

これはジオメトリ変換するときに必要になる。よくありそうな問題なのだけど私は寡聞にしてこの解法を見たことも聞いたこともない。私が考えたのは以下の方法だった。

前準備)

Point[0],…,Point[N-1]を与えられた頂点列とする。また便宜上、Point[-1]はPoint[N-1] , Point[N]はPoint[0]を意味するものとする。(さらに一般化して Point[x] は Point[x % N]を意味するものとする)

次に辺を意味するベクタを定義する : Vector[i] = Point[i+1]-Point[i]

簡単に考えつく解法は以下の2つだが、実はどちらもアルゴリズム的な欠陥がある。

解法1) 回転角を足していき、その正負で判定する。
つまり、 i=0,…,Nに対して r += (Vector[i+1]とx軸となす角 - Vector[i]とx軸の成す角)を-180〜180゜の範囲に正規化したもの。最終的なrの符号で判定する。

※これは直感的だがAtanを必要とするのであまり軽い処理ではない。
Point[0] = (0,0)
Point[1] = (2,0)
Point[2] = (1,0)のような場合、-180゜〜180゜の範囲に正規化するときに-180゜として扱うことも180゜として扱うことも出来ない。要するに、この方法はアルゴリズム的な欠陥がある。

解法2) ねじれていないのだから、xが最小となるPointを含む2辺の位置関係から判定する。
つまり、i=xを最小とするPoint[i]として Vector[i+1]とVector[i]との外積の符号で判定できる。

※これは優れたアイデアのようだが、その2辺が重なっていて外積が0となった場合、次の辺を調べに行く必要がある。またすべての点が同じ点であった場合の処理も必要で、意外と明解ではない。

また、xが最小となるPointが2つ以上ある場合、この方法では正しく判定できない。例)本日の画像

※　この問題に対する正しい解答はコメント欄を参照のこと。

さらにコメント欄でこの問題は『コンピュータグラフィックス理論と実践』に載っているとの情報をもらった。