応用情報技術者 2010年 春期 午前2 問06
問題文
指定された点が指定された多角形の内部にあるか外部にあるかを判定したい。多角形のすべての辺について、点から水平に延ばした半直線との交差回数を調べる。点 Aのように交差回数が奇数回ならば内部、点Bのように交差回数が偶数回又は0ならば外部とする。点Cのように半直線が多角形の頂点上を通過する場合、二つの辺の端点 (上端又は下端) と交差することになるが、このときの交差回数の数え方として、適切なものはどれか。ここで、多角形には水平な辺はないものとし、辺の上の点は考えない。
選択肢
ア：それぞれの辺について、下端での交差は0回、上端での交差は1回とし、合計したものを交差回数とする。（正解）
イ：二つの辺それぞれを0回とし、交差回数には加えない。
ウ：二つの辺それぞれを0.5回、つまり合計で1回の交差回数とする。
エ：二つの辺それぞれを1回、つまり合計で2回の交差回数とする。
点の多角形内外判定における頂点上の交差回数の数え方【午前2 解説】
要点まとめ
- 結論：頂点での交差は「下端での交差は0回、上端での交差は1回」と数えるのが正しいです。
- 根拠：半直線が頂点を通過するとき、隣接する2辺の交差判定が重複しないように調整する必要があります。
- 差がつくポイント：頂点での交差回数の数え方を誤ると、内部判定が誤るため、正確なルール理解が重要です。
正解の理由
点Cのように半直線が多角形の頂点を通過する場合、隣接する2辺の交差判定が重複してカウントされる可能性があります。
このため、頂点を「上端」と「下端」に分類し、上端での交差は1回、下端での交差は0回と数えることで、重複カウントを防ぎます。
このルールにより、交差回数の合計が正確に求まり、点の内外判定が正しく行えます。
したがって、選択肢アが正解です。
このため、頂点を「上端」と「下端」に分類し、上端での交差は1回、下端での交差は0回と数えることで、重複カウントを防ぎます。
このルールにより、交差回数の合計が正確に求まり、点の内外判定が正しく行えます。
したがって、選択肢アが正解です。
よくある誤解
頂点での交差を単純に2回カウントしたり、両方0回にしてしまうと、交差回数が正しく計算できず誤判定につながります。
解法ステップ
- 点から水平に右方向へ半直線を引く。
- 多角形の各辺と半直線の交差を調べる。
- 交差点が辺の内部にある場合は1回カウント。
- 交差点が頂点の場合は、その頂点が辺の「上端」なら1回、「下端」なら0回と数える。
- 全辺の交差回数を合計する。
- 合計が奇数なら点は多角形内部、偶数または0なら外部と判定する。
選択肢別の誤答解説
- イ: 頂点での交差を0回とすると、交差回数が不足し誤判定を招きます。
- ウ: 0.5回ずつカウントする方法は理論的根拠がなく、実装も複雑で誤りやすいです。
- エ: 2回カウントすると交差回数が過剰になり、内部判定が誤ります。
補足コラム
この判定方法は「射影法」や「半直線交差法」と呼ばれ、点の多角形内外判定で広く使われています。
頂点での交差回数の調整は、境界上の点の扱いを明確にし、判定の一貫性を保つために重要です。
また、多角形に水平辺がある場合は別途処理が必要ですが、本問題では水平辺がない前提です。
頂点での交差回数の調整は、境界上の点の扱いを明確にし、判定の一貫性を保つために重要です。
また、多角形に水平辺がある場合は別途処理が必要ですが、本問題では水平辺がない前提です。
FAQ
Q: なぜ頂点を上端・下端に分けるのですか？
A: 頂点での交差判定が隣接辺で重複しないように区別し、正確な交差回数を得るためです。
A: 頂点での交差判定が隣接辺で重複しないように区別し、正確な交差回数を得るためです。
Q: 水平辺がある場合はどう処理しますか？
A: 水平辺は交差判定に影響するため、別途特別なルールや前処理が必要です。
A: 水平辺は交差判定に影響するため、別途特別なルールや前処理が必要です。
関連キーワード: 多角形内外判定、半直線交差法、頂点交差数え方、点の内外判定、コンピュータグラフィックス
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！