多角形の内外判定アルゴリズム

アルゴリズム難易度: ★★★☆☆

指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について、点から水平に延ばした半直線との交差回数を調べる。点Aのように交差回数が奇数回ならば内部、点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合、二つの辺の端点(上端又は下端)と交差することになるが、このときの交差回数の数え方として、適切なものはどれか。ここで、多角形には水平な辺はないものとし、辺の上の点は考えない。

多角形の内外判定

出典: 平成22年度春期 応用情報技術者 午前 問6