Comment déterminer si 2 rayons se croisent?
On nous donne les coordonnées 2D de 2 points: le premier point est l'endroit où le rayon commence et il passe par le deuxième point. On nous donne un autre rayon de la même manière. Comment déterminer s'ils ont un point d'intersection? J'aimerais connaître l'algorithme général et son explication, ne vous inquiétez pas des cas extrêmes (par exemple lorsque les rayons ont le même point de départ). PS J'ai vu une question similaire sur un autre échange de pile, mais les réponses n'ont pas été étayées par une explication.
Réponses
Je ne sais pas si cela répond à votre question, mais voici quelque chose que j'ai écrit il y a quelques années pour un article.
Laisser $\mathbf{p}_0$ et $\mathbf{p}_1$ être les extrémités du premier segment et laissez $\mathbf{q}_0$ et $\mathbf{q}_1$être les extrémités du deuxième segment. Ensuite, les équations paramétriques des deux lignes sont$$ \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 \,. $$ Au point d'intersection, $\mathbf{p} = \mathbf{q}$, c'est à dire, $$ (1 - t_p) \mathbf{p}_0 + t_p \mathbf{p}_1 = (1 - t_q) \mathbf{q}_0 + t_q \mathbf{q}_1 \,. $$ Le réarrangement de l'équation donne $$ \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} \,. $$ Par conséquent, $$ \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) $$ Une fois que nous avons résolu pour $t_p$ et $t_q$nous pouvons trouver facilement le point d'intersection. Si le point d'intersection est en dehors du$\mathbf{p}$ ligne alors $t_p \notin [0, 1]$. De même, pour l'autre segment, si le point d'intersection est en dehors du segment, alors$t_q \notin [0, 1]$.
Étant donné que deux lignes non parallèles doivent se croiser quelque part (selon Euclide), j'imagine que l'OP a voulu une question légèrement différente. Par exemple, les rayons se croisent-ils dans la coque convexe des quatre points donnés (vraiment, implicites)? (la coque convexe est la région entourée par une bande élastique tendue autour des quatre points sans se croiser.) Tel est le problème résolu par Biswajit Banerjee. Vous devez savoir où se trouve l'intersection.
Si vous avez seulement besoin de savoir si les rayons se croisent, vous n'avez pas besoin de trouver le point d'intersection. Ce qui suit peut être plus stable et efficace que la résolution des équations pour le point d'intersection, car il n'implique que des soustractions et des produits scalaires, pas de division.
Votre premier rayon commence à $p_0$ et aller dans la direction de $p_1$ (et infiniment au-delà $p_1$), et votre deuxième rayon commençant à $q_0$ et aller dans la direction de $q_1$ (et infiniment au-delà $q_1$). Pensez-y visuellement. Pour un fixe$p_0$, $p_1$, et $q_0$, quelles valeurs de $q_1$entraîner une intersection? La réponse est que$q_1$doit se trouver dans une région en forme de coin du plan. Un côté du coin est la ligne entre$q_0$ et $p_0$, et l'autre côté du coin est parallèle au premier rayon. Dans le diagramme,$q_1$ doit être dans la région bleue pour que les rayons se croisent.
Nous pouvons exprimer un côté du coin en disant que $q_1$ doit être du même côté du $q_0$ à $p_0$ ligne comme $p_1$est. Si$p_0 - q_0 = (l_x, l_y)$, alors nous pouvons tourner $(l_x, l_y)$ 90 degrés pour obtenir un vecteur perpendiculaire à la ligne: $(-l_y, l_x)$. Alors pour vérifier ça$q_1$ et $p_1$ sont du même côté, on vérifie que $(q_1 - q_0) \cdot (-l_y, l_x)$ a le même signe que $(p_1 - q_0) \cdot (-l_y, l_x)$.
On peut exprimer l'autre côté du coin en regardant la ligne qui passe $q_0$ et $q_0 + (p_1 - p_0)$. $q_1$ et $p_1$doit être du même côté de cette ligne. Un vecteur parallèle à la ligne est$p_1 - p_0 = (m_x, m_y)$ que nous faisons pivoter de 90 degrés pour obtenir $(-m_y, m_x)$. Pour vérifier ça$q_1$ et $p_1$ sont du même côté de cette ligne, nous vérifions que $(p_1 - q_0) \cdot (-m_y, m_x)$ a le même signe que $(q_1 - q_0) \cdot (-m_y, m_x)$.
Donc pour résumer: les deux rayons se croisent si et seulement si $(q_1 - q_0) \cdot (-l_y, l_x)$ a le même signe que $(p_1 - q_0) \cdot (-l_y, l_x)$, et $(p_1 - q_0) \cdot (-m_y, m_x)$ a le même signe que $(q_1 - q_0) \cdot (-m_y, m_x)$.