2つの光線が交差するかどうかを判断する方法は？
2点の2D座標が与えられます。最初の点は光線が開始する場所であり、2番目の点を通過します。同じように別の光線が与えられます。それらに交点があるかどうかをどのように判断しますか？一般的なアルゴリズムとその説明を知りたいのですが、極端な場合（たとえば、光線の開始点が同じ場合）は気にしないでください。PS私は別のスタック交換で同様の質問を見ましたが、答えは説明によって裏付けられませんでした。
回答
それがあなたの質問に答えるかどうかはわかりませんが、これは私が数年前に論文のために書いたものです。
しましょう $\mathbf{p}_0$ そして $\mathbf{p}_1$ 最初のセグメントの終点になり、 $\mathbf{q}_0$ そして $\mathbf{q}_1$2番目のセグメントの終点になります。次に、2つの線のパラメトリック方程式は次のようになります。$$ \mathbf{p}(t_p) = (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 \quad \text{and}\quad \mathbf{q}(t_q) = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ 交差点で、 $\mathbf{p} = \mathbf{q}$、すなわち、 $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ 方程式を並べ替えると、次のようになります。 $$ \mathbf{q}_0 - \mathbf{p}_0 = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix} \begin{bmatrix} t_p \\ t_q \end{bmatrix} \,. $$ したがって、 $$ \begin{bmatrix} t_p \\ t_q \end{bmatrix} = \begin{bmatrix}\mathbf{p}_1 - \mathbf{p}_0 & -(\mathbf{q}_1 - \mathbf{q}_0)\end{bmatrix}^{-1} (\mathbf{q}_0 - \mathbf{p}_0) $$ 解決したら $t_p$ そして $t_q$交点を簡単に見つけることができます。交点が外にある場合$\mathbf{p}$ 次に行 $t_p \notin [0, 1]$。同様に、他のセグメントの場合、交点がセグメントの外側にあると、$t_q \notin [0, 1]$。
（Euclidによると）2本の非平行線はどこかで交差する必要があるので、OPはわずかに異なる質問を意図していると思います。たとえば、光線は、指定された4つの（実際には暗黙の）点の凸包内で交差しますか？（凸包は、交差することなく4点すべての周りに張られた弾性バンドで囲まれた領域です。）これは、BiswajitBanerjeeによって解決された問題です。交差点がどこにあるかを知る必要があります。
光線が交差するかどうかだけを知る必要がある場合は、交差点を見つける必要はありません。以下は、減算と内積のみを含み、除算を含まないため、交点の方程式を解くよりも安定して効率的である可能性があります。
あなたは最初の光線を $p_0$ との方向に行く $p_1$ （そして無限に超えて $p_1$）、および2番目の光線は $q_0$ との方向に行く $q_1$ （そして無限に超えて $q_1$）。視覚的に考えてください。固定の場合$p_0$、 $p_1$、および $q_0$、の値 $q_1$交差点になりますか？答えはそれです$q_1$平面のくさび形の領域にある必要があります。くさびの片側は間の線です$q_0$ そして $p_0$、そしてくさびの反対側は最初の光線に平行です。図では、$q_1$ 光線が交差するには、青色の領域にある必要があります。
ウェッジの片側を次のように表現できます $q_1$ の同じ側にある必要があります $q_0$ に $p_0$ 行として $p_1$です。場合$p_0 - q_0 = (l_x, l_y)$、次に回転できます $(l_x, l_y)$ 線に垂直なベクトルを取得するには90度： $(-l_y, l_x)$。次に、それを確認します$q_1$ そして $p_1$ 同じ側にいる、私たちはそれをチェックします $(q_1 - q_0) \cdot (-l_y, l_x)$ と同じ記号があります $(p_1 - q_0) \cdot (-l_y, l_x)$。
通過する線を見れば、くさびの向こう側を表現できます。 $q_0$ そして $q_0 + (p_1 - p_0)$。 $q_1$ そして $p_1$この線の同じ側にある必要があります。線に平行なベクトルは$p_1 - p_0 = (m_x, m_y)$ これを90度回転させて $(-m_y, m_x)$。それを確認するには$q_1$ そして $p_1$ この線の同じ側にある、私たちはそれをチェックします $(p_1 - q_0) \cdot (-m_y, m_x)$ と同じ記号があります $(q_1 - q_0) \cdot (-m_y, m_x)$。
つまり、要約すると、2つの光線は、次の場合にのみ交差します。 $(q_1 - q_0) \cdot (-l_y, l_x)$ と同じ記号があります $(p_1 - q_0) \cdot (-l_y, l_x)$、および $(p_1 - q_0) \cdot (-m_y, m_x)$ と同じ記号があります $(q_1 - q_0) \cdot (-m_y, m_x)$。