凸多角形と直線の交差判定

[ei1333]

うしさんがやってくれるので話をするんですが、そうして求めた最大最小の頂点で多角形を分けると単調になるので二分探索ができて、直線との交点の候補が得られるから線分と直線の交差判定に落とし込めます

[Luzhiled]

N 頂点の凸多角形 P の頂点の列 P = (p_0, p_1, ..., p_{N-1}) と 点 l_0, l_1 を通る直線 L に対して h(i) を以下のように定義します

h(i) := cross(p_i - l_0, l_1 - l_0)

これは点 l_0, l_1, p_i からなる三角形の(符号付きの)面積の2倍なので、L と p_i との(符号付きの)距離に比例します

h(i) の極大・極小値をとる index をそれぞれ mn, mx として、ここで多角形を分けると単調になるので、h(i) の符号が変わる場所を二分探索ができます(多分)(辺が直線上にある場合は、困ります)

h(i) は周期関数なので、解けます 参考: noshi91様のツイート

追伸　いつもありがとうございます