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

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

解答：ア

＜解説＞

1. 点Cは、多角形の内部にあるので交差回数は奇数回となる。 したがって、アまたはウが正解である。

   ア	○	辺4は下端で半直線と交差しているので0である。 辺3は上端で半直線と交差しているので1である。 したがって1（奇数）である。
   イ	×	辺4は下端で半直線と交差しているので0である。 辺3は上端で半直線と交差しているので0である。 したがって0（遇数）である。
   ウ	○	辺4は下端で半直線と交差しているので0.5である。 辺3は上端で半直線と交差しているので0.5である。 したがって1（奇数）である。
   エ	×	辺4は下端で半直線と交差しているので1である。 辺3は上端で半直線と交差しているので1である。 したがって2（遇数）である。

2. ウは、次のような点X，点Yの場合1(0.5×2＝1)となり点が多角形の外側であるにもかかわらず内側となるので誤りである。
   

したがって、アが正解である。

分類

1. 応用情報技術者
2. テクノロジ系
3. 基礎理論
4. アルゴリズムとプログラミング
5. アルゴリズム