2 개의 광선이 교차하는지 확인하는 방법은 무엇입니까?
두 점의 2D 좌표가 주어집니다. 첫 번째 점은 광선이 시작되는 곳이고 두 번째 점을 통과합니다. 우리는 같은 방식으로 또 다른 광선을받습니다. 교차점이 있는지 어떻게 확인합니까? 일반적인 알고리즘과 그 설명을 알고 싶습니다. 극단적 인 경우 (예 : 광선이 동일한 시작점을 가질 때)에 대해서는 신경 쓰지 마십시오. 추신 다른 스택 교환에서 비슷한 질문을 보았지만 답변은 설명으로 뒷받침되지 않았습니다.
답변
그것이 당신의 질문에 대한 대답인지 확실하지 않지만 여기에 몇 년 전에 논문으로 쓴 것이 있습니다.
허락하다 $\mathbf{p}_0$ 과 $\mathbf{p}_1$ 첫 번째 세그먼트의 끝 점이되고 $\mathbf{q}_0$ 과 $\mathbf{q}_1$두 번째 세그먼트의 끝 점이됩니다. 그러면 두 선의 매개 변수 방정식은 다음과 같습니다.$$ \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에 따르면) OP가 약간 다른 질문을 의도했다고 생각합니다. 예를 들어, 광선이 주어진 4 개의 (실제로, 암시 된) 점의 볼록 껍질 내에서 교차합니까? (볼록한 선체는 교차하지 않고 네 점을 모두 둥글게 뻗은 탄성 밴드로 둘러싸인 영역입니다.) 이것이 Biswajit Banerjee가 해결 한 문제입니다. 교차로가 어디에 있는지 알아야합니다.
광선이 교차하는지 여부 만 알아야하는 경우 교차점을 찾을 필요가 없습니다. 다음은 나누기가없는 빼기와 내적 만 포함되므로 교차점에 대한 방정식을 푸는 것보다 더 안정적이고 효율적일 수 있습니다.
첫 번째 광선은 $p_0$ 그리고 방향으로가는 $p_1$ (그리고 무한히 넘어 $p_1$), 두 번째 광선은 $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)$.
요약하자면 두 광선은 다음과 같은 경우에만 교차합니다. $(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)$.