2022-03-19 アルゴリズムと数学演習問題集 098 - Polygon and Point を解いた

アルゴリズムと数学演習問題集 098 - Polygon and Point を解いた。

点が多角形の内部にあるかを判定する問題だ。どう判定するのかちょっと見当がつかなかったので早々に検索した。次のページを参考にした。

基本的なアイデアは「点が多角形の内側にあるとき点から右に伸ばした水平線は多角形の辺と奇数回交わる」というものだ。例外的な状況としては点が辺上にある・水平線が辺と重なる状況がある。

制約から点が辺上にある状況はない。そのためこれは考慮しなくても良い。

水平線が辺と重なる状況は辺の始点・終点の y 座標を半開区間として判定することで回避できる。 下端 <= 点 < 上端 の形で判定すると上端と下端が同一のときその辺は処理の対象にならない。

また上記のページのコードだと (一部判定が間違っていそうなのと) 除算による精度の問題が出るので判定を変えている。

Slay the Spire のディフェクトで心臓を倒した。

今日のコミット。