点の多角形に対する内外判定

点が多角形ループの内側にあるか外側にあるかを判定するには？
要素は２次元空間内に存在するものとします。

解説

内外判定の基本的な考え方として、「内外を判定したい点から発するレイ（ray：一条の光）を仮定し、レイが多角形の辺を何回横切るかを数え、偶数回横切るとき、点は多角形の外側、奇数回横切るとき、点は多角形の内側と判定することができる」という考え方があります。

ただ、この考え方に従って実装を行うと、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合に判定を誤ってしまう実装になることがあります。

下に示す実装では、レイをＸプラス方向に発して、多角形の辺がレイを、「上から下に横切るときには横切り回数を１引き、下から上に横切るときには横切り回数を１足すこととする」ことや、「レイの線上にある点はレイより上にあることとする」ことにより、レイに対して点接触になる点のある多角形や、レイに対して線接触になる辺のある多角形の場合でも正しく内外判定できるようになっています。

bool IsPointInPolygon( const CNhPoint2d& pointTarget, const unsigned int uiCountPoint, const CNhPoint2d* aPoint ) { int iCountCrossing = 0; CNhPoint2d point0 = aPoint[0]; bool bFlag0x = (pointTarget.x <= point0.x); bool bFlag0y = (pointTarget.y <= point0.y); // レイの方向は、Ｘプラス方向 for( unsigned int ui = 1; ui < uiCountPoint + 1; ui++ ) { CNhPoint2d point1 = aPoint[ui%uiCountPoint]; // 最後は始点が入る（多角形データの始点と終点が一致していないデータ対応） bool bFlag1x = (pointTarget.x <= point1.x); bool bFlag1y = (pointTarget.y <= point1.y); if( bFlag0y != bFlag1y ) { // 線分はレイを横切る可能性あり。 if( bFlag0x == bFlag1x ) { // 線分の２端点は対象点に対して両方右か両方左にある if( bFlag0x ) { // 完全に右。⇒線分はレイを横切る iCountCrossing += (bFlag0y ? -1 : 1); // 上から下にレイを横切るときには、交差回数を１引く、下から上は１足す。 } } else { // レイと交差するかどうか、対象点と同じ高さで、対象点の右で交差するか、左で交差するかを求める。 if( pointTarget.x <= ( point0.x + (point1.x - point0.x) * (pointTarget.y - point0.y ) / (point1.y - point0.y) ) ) { // 線分は、対象点と同じ高さで、対象点の右で交差する。⇒線分はレイを横切る iCountCrossing += (bFlag0y ? -1 : 1); // 上から下にレイを横切るときには、交差回数を１引く、下から上は１足す。 } } } // 次の判定のために、 point0 = point1; bFlag0x = bFlag1x; bFlag0y = bFlag1y; } // クロスカウントがゼロのとき外、ゼロ以外のとき内。 return (0 != iCountCrossing); }

ダウンロード

サンプルプロジェクト

参考

Graphics Gems Ⅳ：Point in Polygon Strategies