平成22年度 春期 午前 問6
アルゴリズム
アルゴリズムに関する問題
指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について，点から水平に延ばした半直線との交差回数を調べる。点 A のように交差回数が奇数回ならば内部，点 B のように交差回数が偶数回又は 0 ならば外部とする。点 C のように半直線が多角形の頂点上を通過する場合，二つの辺の端点（上端又は下端）と交差することになるが，このときの交差回数の数え方として，適切なものはどれか。ここで，多角形には水平な辺はないものとし，辺の上の点は考えない。
〔多角形と 3 つの点〕
辺1〜辺6 でできた六角形に、点A・点B・点C から右へ水平な半直線を引いた図。
点A … 多角形の内部にある
点B … 多角形の左外にあり、半直線が多角形を突き抜けていく
点C … 多角形の内部にあり、右へ延ばした半直線が
辺3 と辺4 が出会う【頂点】をちょうど通過する- アそれぞれの辺について，下端での交差は 0 回，上端での交差は 1 回とし，合計したものを交差回数とする。
- イ二つの辺それぞれを 0 回とし，交差回数には加えない。
- ウ二つの辺それぞれを 0.5 回，つまり合計で 1 回の交差回数とする。
- エ二つの辺それぞれを 1 回，つまり合計で 2 回の交差回数とする。
答えと解説を見る
✓ これが正解アそれぞれの辺について，下端での交差は 0 回，上端での交差は 1 回とし，合計したものを交差回数とする。
解説
下端は 0 回、上端は 1 回と数えて合計します。
この内外判定は、点から右へ延ばした半直線が多角形の辺と何回交わるかを数え、奇数なら内部と決めるアルゴリズムです。半直線がちょうど頂点を通るときに困るのは、そこで出会う二つの辺に 2 種類あるからです。ひとつは半直線の上下にまたがって続く頂点で、ここでは内と外が本当に入れ替わるので合計は奇数になってほしい形です。もうひとつは山の頂きや谷の底のように二つの辺が同じ側へ戻る頂点で、内と外は入れ替わらないので合計は偶数になってほしい形です。正解は、辺ごとに下端での交差を 0 回、上端での交差を 1 回と数えて合計する規則です。またがる頂点では一方の辺にとって上端、もう一方にとって下端になるので合計 1 回の奇数、山の頂きではどちらの辺にとっても上端なので合計 2 回、谷の底ではどちらの辺にとっても下端なので合計 0 回となり、2 種類とも欲しい偶奇が得られます。端の片側だけを数に入れるこの工夫は、区間の重なりを調べるときや値を区分へ割り振るときにも同じ形で出てきます。設問が水平な辺を除き、辺の上の点を考えないと断っているのは、上端と下端を必ず決められるようにするためです。
ほかの選択肢はなぜ違うのか
- イ二つの辺それぞれを 0 回とし，交差回数…：どの頂点も数に入れないため、半直線が本当に突き抜けた場所まで捨ててしまいます。またいだのに合計が偶数のままとなり、本来は内部と判定すべき点を外部と取り違えます。
- ウ二つの辺それぞれを 0.5 回，つまり合…：どの頂点も合計 1 回として扱うため、二つの辺が同じ側へ戻るだけの場所でも奇数がひとつ増えます。入れ替わっていないのに内と外が反転し、山の頂きや谷の底で判定を誤ります。
- エ二つの辺それぞれを 1 回，つまり合計で…：どの頂点も合計 2 回として扱うため、本当に突き抜けた場所が偶数になってしまいます。入れ替わるべきところで内と外が変わらず、こちらも 2 種類の頂点を区別できていません。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成22年度 春期 応用情報技術者試験 午前 問6
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）