点の多角形内包チェック

ある点が多角形（ポリゴン）の内部にあるかどうかをチェックするアルゴリズムを実装したくてちょっと調べてみました。凸多角形限定のアルゴリズムは以前実装したことがあったのですが、このページ（http://bal4u.dip.jp/mt/program/archives/2004/11/_ph.html）を見たら限定でなくても結構簡単に実装できるみたいなので、C++的に書き直しながら内部を把握してみました。
ちなみに、高速化を考え、線上は外側とみなすようにしてあります。
（追記）これ、原理的には穴が開いている多角形でも対応可能なのですが、ただ与えられた頂点配列の処理のしかたがそこまで対応できていませんね。しかし、それぞれの閉じた多角形の頂点配列を分けて処理するというか、頂点配列の中に区切りヒントでも埋め込むか、そんな感じで簡単に対応できそうです。

#include "stdafx.h"
#include <stdio.h>
#include <assert.h>

/*!
  ２次元ベクトルクラス.
*/
class VEC2{
public:
  float x, y;
public:
  VEC2() : x(0.0f), y(0.0f){;}
  VEC2( const float& cx, const float& cy ) : x(cx), y(cy){;}
  ~VEC2(){;}

  void  set( const float& cx, const float& cy ){
    x = cx;
    y = cy;
  }

  bool  insidePolygon( const int& numV, const VEC2* pV );
};

/*!
  与えた多角形データの内側かどうかを判定します.
  @note 線上は外側とみなします.
  @note 多角形は凸多角形でなくてもよく、内側に切抜きがあっても良い.
  @param  numV  [in]  頂点数（pVの要素数）.
  @param  pV    [in]  多角形データの頂点データ配列.
*/
#define DEBUG_INSIDEPOLYGON 1 // 1のとき、逆側のチェック.
bool VEC2::insidePolygon( const int& numV, const VEC2* pV )
{
  if( numV < 3 ){
    return false;
  }

  bool  retInside = false;
#if DEBUG_INSIDEPOLYGON
  bool  retInside_d = false;
#endif
  int   i, j;
  float xx;
  for( i=0; i<numV; i++ ){
    j = i+1;
    if( j>=numV ){
      j -= numV;
    }
    const VEC2& pv0 = pV[i];
    const VEC2& pv1 = pV[j];

    // まず, Y座標のチェック.
    if( (y <= pv0.y && y <= pv1.y) 
      || (y >= pv0.y && y >= pv1.y) ){
      // チェック対象にならないのでスキップ.
      continue;
    }
    // 次に, X座標のチェック.
    xx = ((pv1.x-pv0.x)/(pv1.y-pv0.y)) * (y-pv0.y) + pv0.x;
    if( x < xx ){
      retInside = !retInside; // flip.
    }
#if DEBUG_INSIDEPOLYGON
    if( x > xx ){
      retInside_d = !retInside_d; // flip.
    }
#endif
  }

#if DEBUG_INSIDEPOLYGON
  assert( retInside == retInside_d );
#endif
  return retInside;
}

bool test_insidePolygon()
{
  // テストする矩形.
  int   numPolygon  = 4;
  VEC2  polygon[4];
  polygon[0].set( 1.0f,  1.0f );
  polygon[1].set( 3.0f, -2.0f );
  polygon[2].set( 5.0f,  1.0f );
  polygon[3].set( 2.0f,  3.0f );

  bool  br;
  br  = VEC2(2.0f, 0.0f).insidePolygon( numPolygon, polygon );
  if( br != true ){
    return false;
  }

  br  = VEC2(0.0f, 0.0f).insidePolygon( numPolygon, polygon );
  if( br != false ){
    return false;
  }

  br  = VEC2(2.0f, 3.0f).insidePolygon( numPolygon, polygon );
  if( br != false ){
    return false;
  }

  printf("テスト成功.\n");
  return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
  bool  result  = test_insidePolygon();
  assert( result );

  return 0;
}

なるほどね〜。
(2007-05-05 バグ修正.. forループのインデックスチェックバグ)