「2D多角形の内部、外部判定のやり方」のメモ
判定とは一体
- 2Dの多角形に対し、AまたはBみたいな点が図形の内部にあるか外部なのかを判別することを示す。
図形の内部に位置する点の特徴は
- 図形の外部から点を通過するRay(光線)を放って、点Pに到達するまでの図形の交点の数を求めば、その点が図形の内部にあるかないかが分かる。
- 簡単ながらもすごいアルゴリズム。ちょっと変形すれば3Dの三角形トポロジーのメッシュにも適用が出来る。
こっちでは上の図とは違って、左から右へと放つRayを使用して交点を求めます。だとしても外部にある点は偶数で、内部にある点は奇数ということは変わりません。
実装
2Dの場合、ある点Pが図形の中にあるかを判断するために放つRayはXかY軸に並行したものとすれば実装が簡単になります。(3Dはちょっと複雑になります)
- Rayのスターティングポイントから点Pまでの直線を「半直線」という。
- 図形を成す全ての線分と、
- 半直線が「交差」して、
- 点PよりX座標値が小さい「交点」があるかを判断する(この場合、RayはX軸に平行するとする)
条件1が当たれば、「交点」は必ず存在します。しかしその点が点Pの前にあるか、後ろにあるかがわかりませんので位置の値を求めて判断しなければなりません。
以下のコードは2D図形に対してpoint
点Pが図形の内部にあるかないかを判断し、内部にあったらtrue
を返す関数です。
bool IsInside(const std::array<DVector, 10>& polygon, const DVector& point) { int intersected = 0; for (int i = 0; i < 10; ++i) { const auto& start = polygon[i % 10]; const auto& end = polygon[(i + 1) % 10]; // Compare point.Y is in [start.Y, end.Y] if ((start.y >= point.y) == (end.y >= point.y)) { continue; } // Get intersection. const float grad = float(end.y - start.y) / float(end.x - start.x); const float resX = (point.y + grad * start.x - start.y) / grad; if (resX < point.x) { intersected++; } } return (intersected % 2 != 0) ? true : false; }
- 図形を成す線分を取る。
point
点PがY軸に対して線分のY範囲の中にあるかを判断する(条件1)- 線分の勾配(傾き)を求め、線分と半直線が交差している部分の点のY値が同一だと判断し、X値を求む。
- X値が
point
点Pより小さいと、交点が点Pより前にあるものだと判断しカウンターを増す。 - 最後にカウントが奇数だったら
true
を返す。
したはアルゴリズムを検証するためのテスト図形std::array<DVector, 10>
とテスト点Pを使用してテストを回したコードです。
struct DVector final { int x, y; }; constexpr std::array<DVector, 10> kMesh = { DVector {8, 2}, {11, 10}, {22, 2}, {34, 20}, {26, 14}, {14, 15}, {27, 18}, {18, 25}, {9, 23}, {4, 17} }; int main() { constexpr DVector point = {8, 8}; if (IsInside(kMesh, point) == true) { std::printf("IsInside\n"); } else { std::printf("IsNotInside\n"); } return 0; }
点Pは上の図によれば図形の内部にあることがわかります。従って、結果もIsInside
と図形の内部にあるという結果を出します。もしある点P'がある場合には、この点は図形の外部にあるためIsNotInside
と結果を出します。
IsInside
参照
- 図は元記事にあるものを使いました。