¿Cómo determinar si se cruzan 2 rayos?
Se nos dan las coordenadas 2D de 2 puntos: el primer punto es donde comienza el rayo y pasa por el segundo punto. Se nos da otro rayo de la misma manera. ¿Cómo determinamos si tienen un punto de intersección? Me gustaría conocer el algoritmo general y su explicación, no me preocupo por los casos extremos (por ejemplo, cuando los rayos tienen el mismo punto de partida). PD: Vi una pregunta similar en otro intercambio de pila, pero las respuestas no estaban respaldadas por una explicación.
Respuestas
No estoy seguro de si responde a su pregunta, pero aquí hay algo que escribí hace unos años para un artículo.
Dejar $\mathbf{p}_0$ y $\mathbf{p}_1$ ser los puntos finales del primer segmento y dejar $\mathbf{q}_0$ y $\mathbf{q}_1$ser los puntos finales del segundo segmento. Entonces las ecuaciones paramétricas de las dos líneas son$$ \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 \,. $$ En el punto de intersección, $\mathbf{p} = \mathbf{q}$, es decir, $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ El reordenamiento de la ecuación da $$ \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} \,. $$ Por lo tanto, $$ \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) $$ Una vez que hayamos resuelto $t_p$ y $t_q$podemos encontrar el punto de intersección fácilmente. Si el punto de intersección está fuera del$\mathbf{p}$ línea entonces $t_p \notin [0, 1]$. De manera similar, para el otro segmento, si el punto de intersección está fuera del segmento, entonces$t_q \notin [0, 1]$.
Dado que dos líneas no paralelas deben cruzarse en algún lugar (según Euclides), imagino que el OP pretendía una pregunta ligeramente diferente. Por ejemplo, ¿los rayos se cruzan dentro del casco convexo de los cuatro puntos dados (realmente, implícitos)? (el casco convexo es la región encerrada por una banda elástica estirada alrededor de los cuatro puntos sin cruzar). Ese es el problema resuelto por Biswajit Banerjee. Necesita saber dónde está la intersección.
Si solo necesita saber si los rayos se cruzan, no tiene que encontrar el punto de intersección. Lo siguiente puede ser más estable y eficiente que resolver las ecuaciones para el punto de intersección, ya que solo involucra restas y productos escalares, no división.
Tienes tu primer rayo a partir de $p_0$ y yendo en la dirección de $p_1$ (e infinitamente más allá $p_1$), y su segundo rayo a partir de $q_0$ y yendo en la dirección de $q_1$ (e infinitamente más allá $q_1$). Piense en ello visualmente. Por un fijo$p_0$, $p_1$, y $q_0$, que valores de $q_1$resultar en una intersección? La respuesta es que$q_1$debe estar en una región en forma de cuña del avión. Un lado de la cuña es la línea entre$q_0$ y $p_0$, y el otro lado de la cuña es paralelo al primer rayo. En el diagrama,$q_1$ debe estar en la región azul para que los rayos se crucen.
Podemos expresar un lado de la cuña diciendo que $q_1$ debe estar en el mismo lado de la $q_0$ a $p_0$ línea como $p_1$es. Si$p_0 - q_0 = (l_x, l_y)$, entonces podemos rotar $(l_x, l_y)$ 90 grados para obtener un vector perpendicular a la línea: $(-l_y, l_x)$. Entonces para comprobar eso$q_1$ y $p_1$ están del mismo lado, comprobamos que $(q_1 - q_0) \cdot (-l_y, l_x)$ tiene el mismo signo que $(p_1 - q_0) \cdot (-l_y, l_x)$.
Podemos expresar el otro lado de la cuña mirando la línea que pasa por $q_0$ y $q_0 + (p_1 - p_0)$. $q_1$ y $p_1$debe estar en el mismo lado de esta línea. Un vector paralelo a la recta es$p_1 - p_0 = (m_x, m_y)$ que giramos 90 grados para obtener $(-m_y, m_x)$. Para comprobar eso$q_1$ y $p_1$ están en el mismo lado de esta línea, comprobamos que $(p_1 - q_0) \cdot (-m_y, m_x)$ tiene el mismo signo que $(q_1 - q_0) \cdot (-m_y, m_x)$.
Entonces, para resumir: los dos rayos se cruzan si y solo si $(q_1 - q_0) \cdot (-l_y, l_x)$ tiene el mismo signo que $(p_1 - q_0) \cdot (-l_y, l_x)$, y $(p_1 - q_0) \cdot (-m_y, m_x)$ tiene el mismo signo que $(q_1 - q_0) \cdot (-m_y, m_x)$.