平成22年度 春期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について，点から水平に延ばした半直線との交差回数を調べる。点Aのように交差回数が奇数回ならば内部，点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合，二つの辺の端点（上端又は下端）と交差することになるが，このときの交差回数の数え方として，適切なものはどれか。ここで，多角形には水平な辺はないものとし，辺の上の点は考えない。
出典：平成22年度 春期 応用情報技術者試験 午前 問6
- アそれぞれの辺について，下端での交差は0回，上端での交差は1回とし，合計したものを交差回数とする。
- イ二つの辺それぞれを0回とし，交差回数には加えない。
- ウ二つの辺それぞれを0.5回，つまり合計で1回の交差回数とする。
- エ二つの辺それぞれを1回，つまり合計で2回の交差回数とする。
正解：ア
解説
点Cのように半直線が多角形の頂点を通過する場合，その頂点に接続する2辺のうち，一方をその頂点を下端とする辺，もう一方を上端とする辺として扱います。下端での交差は数えず，上端での交差だけを1回と数えることで，頂点を通らない一般の辺との交差と整合する正しい内外判定ができます。
選択肢ごとの解説
- ア正しい。下端側の辺を0回，上端側の辺を1回として合計1回の交差とすることで，頂点を通る半直線も一般の辺の交差と同様に扱うことができ，正しい内外判定ができます。
- イ誤り。両方とも0回として交差回数に加えないと，本来奇数回交差すべき点を偶数回（0回）と判定してしまい，内外判定を誤る場合があります。
- ウ誤り。0.5回ずつを合計するという数え方は，整数回の交差として扱う一般的なアルゴリズムの実装には適していません。
- エ誤り。両方を1回ずつ，合計2回とすると，頂点を通過する場合に本来1回とすべき交差が2回とカウントされ，内外判定を誤ります。