Come determinare se 2 raggi si intersecano?
Ci vengono fornite le coordinate 2D di 2 punti: il primo punto è dove inizia il raggio e passa per il secondo punto. Ci viene dato un altro raggio nello stesso modo. Come determiniamo se hanno un punto di intersezione? Vorrei conoscere l'algoritmo generale e la sua spiegazione, non importa i casi estremi (es. Quando i raggi hanno lo stesso punto di partenza). PS Ho visto una domanda simile su un altro scambio di stack, ma le risposte non sono state supportate da spiegazioni.
Risposte
Non sono sicuro che risponda alla tua domanda, ma ecco qualcosa che ho scritto alcuni anni fa per un giornale.
Permettere $\mathbf{p}_0$ e $\mathbf{p}_1$ essere i punti finali del primo segmento e lascia $\mathbf{q}_0$ e $\mathbf{q}_1$essere i punti finali del secondo segmento. Allora le equazioni parametriche delle due linee sono$$ \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 \,. $$ Nel punto di intersezione, $\mathbf{p} = \mathbf{q}$, cioè $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ La riorganizzazione dell'equazione dà $$ \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} \,. $$ Perciò, $$ \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 volta che abbiamo risolto per $t_p$ e $t_q$possiamo trovare facilmente il punto di intersezione. Se il punto di intersezione è esterno a$\mathbf{p}$ linea allora $t_p \notin [0, 1]$. Allo stesso modo, per l'altro segmento, se il punto di intersezione è esterno al segmento, allora$t_q \notin [0, 1]$.
Poiché due linee non parallele devono intersecarsi da qualche parte (secondo Euclide) immagino che l'OP intendesse una domanda leggermente diversa. Ad esempio, i raggi si intersecano all'interno dello scafo convesso dei quattro punti dati (realmente, impliciti)? (lo scafo convesso è la regione racchiusa da una fascia elastica tesa attorno a tutti e quattro i punti senza incrociarsi). Questo è il problema risolto da Biswajit Banerjee. Devi sapere dove si trova l'incrocio.
Se hai solo bisogno di sapere se i raggi si intersecano, non devi trovare il punto di intersezione. Quanto segue può essere più stabile ed efficiente rispetto alla risoluzione delle equazioni per il punto di intersezione, poiché implica solo sottrazione e prodotti puntiformi, nessuna divisione.
Hai il tuo primo raggio che inizia a $p_0$ e andando in direzione di $p_1$ (e infinitamente oltre $p_1$) e il secondo raggio che inizia da $q_0$ e andando in direzione di $q_1$ (e infinitamente oltre $q_1$). Pensaci visivamente. Per un fisso$p_0$, $p_1$, e $q_0$, quali valori di $q_1$risultato in un incrocio? La risposta è questa$q_1$deve trovarsi in una regione a forma di cuneo dell'aereo. Un lato del cuneo è la linea di confine$q_0$ e $p_0$e l'altro lato del cuneo è parallelo al primo raggio. Nel diagramma,$q_1$ deve trovarsi nella regione blu affinché i raggi si intersechino.
Possiamo esprimere un lato del cuneo dicendo questo $q_1$ deve essere sullo stesso lato del file $q_0$ per $p_0$ linea come $p_1$è. Se$p_0 - q_0 = (l_x, l_y)$, quindi possiamo ruotare $(l_x, l_y)$ 90 gradi per ottenere un vettore perpendicolare alla linea: $(-l_y, l_x)$. Quindi per verificarlo$q_1$ e $p_1$ sono dalla stessa parte, lo controlliamo $(q_1 - q_0) \cdot (-l_y, l_x)$ ha lo stesso segno di $(p_1 - q_0) \cdot (-l_y, l_x)$.
Possiamo esprimere l'altro lato del cuneo guardando la linea che passa attraverso $q_0$ e $q_0 + (p_1 - p_0)$. $q_1$ e $p_1$deve trovarsi sullo stesso lato di questa linea. Un vettore parallelo alla linea è$p_1 - p_0 = (m_x, m_y)$ che ruotiamo di 90 gradi per ottenere $(-m_y, m_x)$. Per verificarlo$q_1$ e $p_1$ sono sullo stesso lato di questa linea, lo controlliamo $(p_1 - q_0) \cdot (-m_y, m_x)$ ha lo stesso segno di $(q_1 - q_0) \cdot (-m_y, m_x)$.
Quindi riassumendo: i due raggi si intersecano se e solo se $(q_1 - q_0) \cdot (-l_y, l_x)$ ha lo stesso segno di $(p_1 - q_0) \cdot (-l_y, l_x)$, e $(p_1 - q_0) \cdot (-m_y, m_x)$ ha lo stesso segno di $(q_1 - q_0) \cdot (-m_y, m_x)$.