問題プレビューID: 0aef26a4応用情報技術者試験 2010年(平成22年度)春期 午前

問 6
応用情報技術者試験 2010年(平成22年度)春期 午前

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

図では,多角形(六角形)の辺に 辺 1〜辺 6 の番号が付されており,点 A と点 C は多角形の内部に,点 B は外部にある。点 C から右に延ばした半直線は,多角形の頂点(辺 2 と辺 3 が接する端点)を通過する。

解説

正解は「ア」です。

半直線が多角形の頂点をちょうど通る場合,その頂点を共有する 2 つの辺は,一方が半直線より上側に,他方が下側に伸びています(多角形がその頂点で折れ曲がっている場合)。このとき,交差回数の数え方を統一しないと,交差回数の偶奇がずれて内外判定を誤ります。

適切な数え方は,頂点を通過する場合に,その頂点を下端に持つ辺(頂点から下側へ伸びる辺)は交差 0 回,上端に持つ辺(頂点から上側へ伸びる辺)は交差 1 回と数える方法です。これにより,半直線が多角形を横切る通常の頂点では 2 辺の合計が 1 回となり,正しく 1 回の交差として数えられます。

  • イ: 2 つの辺をともに 0 回とすると,本来 1 回と数えるべき交差が 0 回になり,内部と外部の判定が反転します。
  • ウ: 2 つの辺をそれぞれ 0.5 回とすると,半直線が頂点を通るものの多角形を横切らない場合(両方の辺が半直線の同じ側に伸びる山や谷の頂点)まで 1 回と数えてしまい,内外判定を誤ります。
  • エ: 2 つの辺をそれぞれ 1 回とすると,本来 1 回の交差が 2 回(偶数)となり,内部が外部と判定されてしまいます。

よって,正解は「ア」です。

関連問題

本文が同じ・似ている問題を表示しています