多角形のループの向き

多角形のループの向き（時計回り/反時計回り）を求めるには？
要素は２次元空間内に存在するものとします。

解法１

解説

多角形の、端（左端や右端、上端、下端）の点を求め、その点とその点の前後の点を用いて、多角形のループの向きを求めることができます。
端の点を点B、点Bの一つ前の点を点A、点Bの一つ次の点を点Cとすると、
点Cが線分ABの右にあるとき、ループは、時計回り
点Cが線分ABの左にあるとき、ループは、反時計回り
です。
※端の点が複数あるときには、複数ある端の点の中のさらに一番端の点を求めます。（左端で処理するとしたときに、左端の点が複数あったならば、その左端の点の中の下端の点を求める。などをします。）

// 0 : 不定 -1 : 時計回り 1 : 反時計回り int CalcLoopwise( const unsigned int uiCountPoint, const CNhPoint2d* aPoint ) { if( 2 >= uiCountPoint ) { return 0; } unsigned int ui; // 左端（同じ左端ならば下側）の点を求める。 unsigned int uiIndexLeft = 0; for( ui = 1; ui < uiCountPoint; ui++ ) { if( aPoint[uiIndexLeft].x > aPoint[ui].x || (aPoint[uiIndexLeft].x == aPoint[ui].x && aPoint[uiIndexLeft].y > aPoint[ui].y ) ) { uiIndexLeft = ui; } } // 左端点の前後の点を求める（座標値が左端点と異なる点まで進める） unsigned int uiIndexLeft_prev; if( 0 == uiIndexLeft ){ uiIndexLeft_prev = uiCountPoint - 1; } else { uiIndexLeft_prev = uiIndexLeft - 1; } for( ui = 0; ui < uiCountPoint; ui++ ) { if( aPoint[uiIndexLeft] != aPoint[uiIndexLeft_prev] ) { break; } if( 0 == uiIndexLeft_prev ){ uiIndexLeft_prev = uiCountPoint - 1; } else { uiIndexLeft_prev--; } } if( ui == uiCountPoint ) { // 左端点と異なる前の点がない⇒すべて同じ座標値⇒多角形は点に縮退している。 return 0; } unsigned int uiIndexLeft_next = (uiIndexLeft + 1) % uiCountPoint; for( ui = 0; ui < uiCountPoint; ui++ ) { if( aPoint[uiIndexLeft] != aPoint[uiIndexLeft_next] ) { break; } uiIndexLeft_next = (uiIndexLeft_next + 1) % uiCountPoint; } double dOuterProduct = (aPoint[uiIndexLeft] - aPoint[uiIndexLeft_prev]).CalcOuterProduct( aPoint[uiIndexLeft_next] - aPoint[uiIndexLeft] ); if( 0 > dOuterProduct ) { // 時計回り return -1; } else if( 0 < dOuterProduct ) { // 反時計回り return 1; } return 0; }

考察

多角形に自己交差があり、判定点が、自己交差部分にある場合には、ループの向きが反対に求まってしまいます。（下図は、ループの向きが反対に求まってしまう図形の例）

解法２

解説

ループの向き判定に備えて、負の値が返ってくることもあるように設計してある多角形の面積計算を用いて、多角形の面積計算を行い、
面積が、正の値なら、ループは反時計回り（もしくは、反時計回りの部分の方が時計回りの部分より大きい）
面積が、負の値なら、ループは時計回り（（もしくは、時計回りの部分の方が反時計回りの部分より大きい）
面積が、ゼロなら、ループは潰れている（もしくは、時計回りの部分と反時計回りの部分の大きさが等しい）
と判定します。

double CalcPolygonArea( const unsigned int uiCountPoint, const CNhPoint2d* aPoint ) { double dArea = 0; for( unsigned int ui = 0; ui < uiCountPoint; ui++ ) { dArea += aPoint[ui].CalcOuterProduct( aPoint[(ui+1)%uiCountPoint] ); } return 0.5 * dArea; } // 0 : 不定 -1 : 時計回り 1 : 反時計回り int CalcLoopwise2( const unsigned int uiCountPoint, const CNhPoint2d* aPoint ) { double dArea = CalcPolygonArea( uiCountPoint, aPoint ); if( 0 > dArea ) { // 時計回り return -1; } else if( 0 < dArea ) { // 反時計回り return 1; } return 0; }

考察

多角形に自己交差がある場合でも、適切なループの向きを求めることができます。
解法１よりも速度においては劣りますが、多角形に自己交差があるかもしれない場合には、解法２を使用すべきです。
（「自己交差があるかを判定し、自己交差を除去し、解法１を用いてループの向きを判定」するよりは、「解法２を用いてループの向きを判定する」方が、はるかに高速に処理できます。）

ダウンロード

サンプルプロジェクト