平成22年度春期 応用情報技術者試験 午前 問6
指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について，点から水平に延ばした半直線との交差回数を調べる。点Aのように交差回数が奇数回ならば内部，点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合，二つの辺の端点（上端又は下端）と交差することになるが，このときの交差回数の数え方として，適切なものはどれか。ここで，多角形には水平な辺はないものとし，辺の上の点は考えない。
- ア それぞれの辺について，下端での交差は0回，上端での交差は1回とし，合計したものを交差回数とする。
- イ 二つの辺それぞれを0回とし，交差回数には加えない。
- ウ 二つの辺それぞれを0.5回，つまり合計で1回の交差回数とする。
- エ 二つの辺それぞれを1回，つまり合計で2回の交差回数とする。
解答・解説を見る
正解：ア
AI解説
点内外判定アルゴリズム(レイキャスティング法)では、半直線が多角形の頂点をちょうど通過する場合、その頂点を共有する2辺の扱いによって交差回数の数え方を工夫する必要がある。一方の辺の端点(下端)を交差回数0、もう一方(上端)を1として合計することで、頂点通過を1回の交差として正しく扱う。この方法により正解はアとなる。 ア: 頂点を共有する2辺について、下端での交差を0回、上端での交差を1回とし合計することで、頂点通過を全体として1回の交差として一貫して扱える方法。これが正解。 イ: 両方の辺を0回として交差回数に加えないと、実際には半直線が多角形の境界を横切っている(あるいは横切っていない)場合との整合が取れなくなる。 ウ: 0.5回ずつの数え方でも合計は1回になるが、整数値でカウントする一般的な実装(上端・下端で扱いを変える方式)としては適切でない。 エ: 両方の辺を1回ずつ、合計2回とカウントすると、実際には1回だけ交差しているはずの頂点通過が2回の交差として扱われ、内外判定を誤る可能性がある。 💡 頂点通過時の交差回数の数え方は「上端は数える・下端は数えない(またはその逆)」というルールを一貫して適用することで、頂点通過を二重カウントしないようにする典型的な実装上の工夫である。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。