アルゴリズム (全97問中51問目)
No.51
指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について，点から水平に延ばした半直線との交差回数を調べる。点Aのように交差回数が奇数回ならば内部，点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合，二つの辺の端点(上端又は下端)と交差することになるが，このときの交差回数の数え方として，適当なものはどれか。ここで，多角形に水平な辺はないものとし，辺の上の点は考えない。
出典：平成22年春期 問6
- それぞれの辺について，下端での交差は0回，上端での交差は1回とし，合計したものを交差回数とする。
- 二つの辺それぞれを0回とし，交差回数には加えない。
- 二つの辺それぞれを0.5回，つまり合計で1回の交差回数とする。
- 二つの辺それぞれを1回，つまり合計で2回の交差回数とする。
- [出題歴]
- ソフトウェア開発技術者 H15春期 問15
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
選択肢の中で「イ」と「エ」の数え方は図中の点Cの状態で値がそれぞれ0と2となってしまい内部と判定されないので間違っていることがすぐにわかると思います。問題は「ア」と「ウ」のどちらが正解かということです。確かにどちらも点Cからの半直線のときはどちらの数え方でも値が1となり正しい判定をします。
両者が異なる判定をするのは、下図の点Dからの半直線のように点からの半直線が多角形の接線となる場合です。
このような点を判定する場合「ウ」の数え方では値が(0.5+0.5=)1となり点Dが多角形の外側であるにもかかわらず内側と判定してしまいます。しかし「ア」の数え方では、上端同士の交差で値は2となり正しい判定を行うことができます。
これらのことから交差回数の数え方として正しい方法は「ア」になります。
両者が異なる判定をするのは、下図の点Dからの半直線のように点からの半直線が多角形の接線となる場合です。
これらのことから交差回数の数え方として正しい方法は「ア」になります。