Как определить, пересекаются ли 2 луча?
Нам даны двухмерные координаты двух точек: первая точка - это точка начала луча, и он проходит через вторую точку. Таким же образом нам дается другой луч. Как определить, есть ли у них точка пересечения? Я хотел бы знать общий алгоритм и его объяснение, не обращайте внимания на крайние случаи (например, когда лучи имеют одну и ту же начальную точку). PS Я видел аналогичный вопрос на другом обмене стеками, но ответы не были подтверждены объяснением.
Ответы
Не уверен, что это ответ на ваш вопрос, но вот кое-что, что я написал несколько лет назад для статьи.
Позволять $\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]$.
Поскольку любые две непараллельные линии должны где-то пересекаться (согласно Евклиду), я полагаю, что ОП намеревался немного другой вопрос. Например, пересекаются ли лучи в выпуклой оболочке четырех заданных (на самом деле подразумеваемых) точек? (выпуклая оболочка - это область, окруженная эластичной лентой, натянутой вокруг всех четырех точек без пересечения.) Эту проблему решил Бисваджит Банерджи. Вам действительно нужно знать, где находится перекресток.
Если вам нужно только знать, пересекаются ли лучи, вам не нужно искать точку пересечения. Следующее может быть более стабильным и эффективным, чем решение уравнений для точки пересечения, поскольку оно включает только вычитание и скалярные произведения, а не деление.
Ваш первый луч начинается с $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)$.