計算幾何(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つだが、実はどちらも