Как найти пересечение линий по координатам

Для того, чтобы решить геометрическую задачу методом координат, необходима точка пересечения, координаты которой используются при решении. Возникает ситуация, когда требуется искать координаты пересечения двух прямых на плоскости или определить координаты тех же прямых в пространстве. Данная статья рассматривает случаи нахождения координат точек, где пересекаются заданные прямые.

Точка пересечения двух прямых – определение

Необходимо дать определение точкам пересечения двух прямых.

Раздел взаимного расположения прямых на плоскости показывает, что они могут совпадать , быть параллельными, пересекаться в одной общей точке или скрещивающимися. Две прямые, находящиеся  в пространстве, называют пересекающимися, если они имеют одну общую точку.

Определение точки пересечения прямых звучит так:

Точка, в которой пересекаются две прямые, называют их точкой пересечения. Иначе говоря, что точка пересекающихся прямых и есть точка пересечения.

Рассмотрим на рисунке, приведенном ниже.

Нахождение координат точки пересечения двух прямых на плоскости

Перед нахождением координат точки пересечения двух прямых, необходимо рассмотреть предлагаемый ниже пример.

Если на плоскости имеется система координат Оху, то задаются две прямые a и b. Прямой a соответствует общее уравнение вида A1x+B1y+C1=0, для прямой b – A2x+B2y+C2=0. Тогда M0(x0, y0) является некоторой точкой плоскости необходимо выявить , будет ли точка М0 являться точкой пересечения этих прямых.

Чтобы решить поставленную задачу, необходимо придерживаться определения. Тогда прямые должны пересекаться  в точке, координаты которой  являются решением заданных уравнений A1x+B1y+C1=0 и A2x+B2y+C2=0. Значит, координаты точки пересечения подставляются во все заданные уравнения. Если они при подстановке дают верное тождество, тогда M0(x0, y0) считается их точкой пересечения.

Переходим к нахождению координат точек пересечения двух прямых при помощи заданных уравнений на  плоскости.

Задаются две пересекающиеся прямые a и b уравнениями вида A1x+B1y+C1=0 и A2x+B2y+C2=0, расположенных в Оху. При обозначении точки пересечения М0 получим, что следует  продолжить поиск координат по уравнениям A1x+B1y+C1=0 и A2x+B2y+C2=0.

Из определения очевидно, что М0 является общей точкой пересечения прямых. В этом случае ее координаты должны удовлетворять уравнениям A1x+B1y+C1=0 и A2x+B2y+C2=0. Иными словами это и есть решение полученной системы A1x+B1y+C1=0A2x+B2y+C2=0.

Значит, для нахождения координат точки пересечения , необходимо все уравнения добавить в систему и решить ее.

Поиск координат сводится к решению системы линейных уравнений. Если по условию дан другой вид уравнения, тогда следует привести его к нормальному виду.

Имеется еще способ для нахождения координат точки пересечения прямых, находящихся на плоскости. Он применим, когда одна из прямых задается параметрическими уравнениями, имеющими вид x=x1+ax·λy=y1+ay·λ, λ∈R. Тогда вместо значения x подставляется x=x1+ax·λ и y=y1+ay·λ, где получим λ=λ0, соответствующее точке пересечения, имеющей координаты x1+ax·λ0, y1+ay·λ0.

Для полного понимания темы, необходимо знать некоторые нюансы.

Предварительно необходимо понять расположение прямых. При их пересечении мы найдем координаты, в других случаях решения существовать не будет. Чтобы не делать эту проверку, можно составлять систему вида A1x+B1y+ C1=0A2x+B2+C2=0 При наличии решения делаем вывод о том, что прямые пересекаются. Если решение отсутствует, то они параллельны. Когда система имеет бесконечное множество решений, тогда говорят, что они совпадают.

Нахождения координат точки пересечения двух прямых в пространстве

Таким же образом находятся точки пересечения прямых пространства.

Когда заданы прямые a и b в координатной плоскости Охуz уравнениями пересекающихся плоскостей, то имеется прямая a , которая  может быть определена при помощи заданной системы A1x+B1y+C1z+D1=0A2x+B2y+C2z+D1=0 а прямая b – A3x+B3y+C3z+D3=0A4x+B4y+C4z+D4=0.

Когда точка М0 является точкой пересечения прямых, тогда ее координаты должны быть решениями обоих уравнений. Получим линейные уравнения в системе:

A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=0A3x+B3y+C3z+D3=0A4x+B4y+C4z+D4=0

Рассмотрим подобные задания на примерах.

Система вида A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=0A3x+B3y+C3z+D3=0A4x+B4y+C4z+D4=0 имеет только одно решение. Значит, прямые a и b пересекаются.

В остальных случаях уравнение не имеет решения, то есть и общих точек тоже. То есть невозможно найти точку с координатами, так как ее нет.

Поэтому система вида A1x+B1y+C1z+D1=0A2x+B2y+C2z+D2=0A3x+B3y+C3z+D3=0A4x+B4y+C4z+D4=0 решается методом Гаусса. При ее несовместимости прямые не являются пересекающимися. Если решений бесконечное множество, то они совпадают.

Можно произвести решение при помощи вычисления основного и расширенного ранга матрицы, после чего применить теорему Кронекера-Капелли. Получим одно, множество или полное отсутствие решений.

Если прямые заданы при помощи кононических или параметрических уравнений, нужно привести к виду уравнений пересекающихся плоскостей, после чего найти координаты.

Нахождение точки пересечения двух прямых (и отрезков)

Введение

Довольно часто при разработке игр возникает необходимость находить точку пересечения прямых, отрезков, лучей и т.д. О том, как реализовать это максимально простым способом, в этой статье.

Популярные способы и их критика

Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти x, и подставить его в уравнение прямой, чтобы найти y (Подробнее здесь).

Однако данный способ становится достаточно громоздким при написании кода (возможно поэтому вы сейчас читаете эту статью), к тому же, он не является универсальным: если одна из прямых параллельна оси Y, мы получим ошибку деления на ноль при вычислении углового коэффициента, и нам придётся прописать код на этот случай; если две прямые перпендикулярны осям, требуется повозиться с обработкой и этого случая. Такой код становится длинным и некрасивым.

В поисках более элегантного решения данной проблемы я наткнулся на весьма интересные способы, основанные на векторном умножении ( habr.com/ru/post/267037 ) и ray castinging’е ( ru.wikipedia.org/wiki/Ray_casting#Концепция ). Но на мой взгляд, они неоправданно сложные в вычислительном плане. Поэтому представляю вашему вниманию (и критике) мой способ.

Мой способ

Задача

Даны координаты двух отрезков. Нужно узнать, пересекаются ли отрезки, и если да, в какой точке. Для этой цели напишем функцию.

Решение

Условные обозначения для исключения недопониманий: a — вектор a, a(y) — проекция вектора a на ось Y, a{x1,y1} — вектор a, заданный координатами x1,y1.

Представим наши отрезки в виде двух векторов: a{x2-x1; y2-y1} и b{x3-x4; y3-y4}. Обратите, внимание, что вектор b имеет противоположное от ожидаемого направление. Введём вектор c{x3-x1; y3-y1}. Заметим, что a*k+b*n=c, где k,n — некоторые коэффициенты. Таким образом, получаем систему уравнений:

a(x)*k+b(x)*n=c(x)
a(y)*k+b(y)*n=c(y)
Наша задача сводится к нахождению этих коэффициентов (правда сказать, достаточно найти лишь один из них).

Предлагаю домножить обе части нижнего уравнения на q= -a(x)/a(y). Так после сложения двух уравнений, мы сразу избавимся от k. Нахождение n сведётся к решению обыкновенного линейного уравнения. Важно обратить внимание, что у n может не быть решения.

Внимательный читатель заметит, что при a(y)=0, мы получим ошибку. Пропишем ветвление на этапе нахождения a(y). Этот случай ещё проще, ведь мы сразу получаем уравнение с одной неизвестной.

Рекомендую попробовать вывести n самостоятельно, так будет понятнее, что откуда берётся в коде ниже.

Зная n, можно найти точку пересечения, для этого мы отнимем от координаты точки (x3,y3) вектор b*n

Собираем воедино

float dot[2];  // точка пересечения

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

Данная функция принимает координаты вершин и возвращает значение 1, если прямые отрезков (именно прямые) пересекаются, иначе 0. Если же вам нужны координаты вершин, вы сможете взять их из массива dot[].

Важно: при введении двух совпадающих прямых, алгоритм выводит отсутствие пересечения. Алгоритм находит точку пересечения прямых, на которых лежат отрезки, поэтому точка может оказаться за пределами отрезка (что вам придётся дополнительно проверить в уже своём коде).

Применим функцию:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

Послесловие

Хоть я и не встретил этот способ в процессе гугления своей проблемы и вывел алгоритм самостоятельно, я не претендую на его полную оригинальность (и правильность). Поэтому добро пожаловать в комментарии!

В евклидовой геометрии пересечение двух прямых может быть пустым множеством, точкой или прямой. Различение этих случаев и поиск точки пересечения используется, например, в компьютерной графике, при планировании движения^[en] и для обнаружения столкновений.

В трёхмерной евклидовой геометрии, если две прямые не лежат в одной плоскости, они называются скрещивающимися и не имеют точек пересечения. Если прямые находятся в одной плоскости, имеется три возможности. Если они совпадают, они имеют бесконечно много общих точек (а именно, все точки на этих прямых). Если прямые различны, но имеют один и тот же наклон, они параллельны и не имеют общих точек. В противном случае они имеют одну точку пересечения.

В неевклидовой геометрии две прямые могут пересекаться в нескольких точках и число непересекающихся с данной прямой других прямых (параллельных) может быть больше единицы.

Пересечение двух прямых[править | править код]

Необходимым условием пересечения двух прямых является принадлежность их одной плоскости, то есть эти прямые не должны быть скрещивающимися. Выполнение этого условия эквивалентно вырожденности тетраэдра, у которого две вершины лежат на одной прямой, а две другие — на другой (т.е. объём этого тетраэдра равен нулю). Алгебраическую форму этого условия можно посмотреть в статье «Проверка скрещенности».

Если заданы по две точки на каждой прямой[править | править код]

Рассмотрим пересечение двух прямых и на плоскости, где прямая определена двумя различными точками и , а прямая — различными точками и ^[1].

Пересечение прямых и можно найти при помощи определителей.

Определители можно переписать в виде:

Заметим, что точка пересечения относится к бесконечным прямым, а не отрезкам между точками, и она может лежать вне отрезков. Если (вместо решения за один шаг) искать решение в терминах кривых Безье первого порядка, то можно проверить параметры этих кривых 0.0 ≤ t ≤ 1.0 и 0.0 ≤ u ≤ 1.0 (t и u — параметры).

Если две прямые параллельны или совпадают, знаменатель обращается в ноль:

Если прямые очень близки к параллельности (почти параллельны), при вычислении на компьютере могут возникнуть числовые проблемы и распознавание такого условия может потребовать подходящего теста на «неопределённость» для приложения. Более устойчивое и общее решение может быть получено при вращении отрезков таким образом, что один из них станет горизонтальным, а тогда параметрическое решение второй прямой легко получить. При решении необходимо внимательное рассмотрение специальных случаев (параллельность/совпадение прямых, наложение отрезков).

Если заданы уравнения прямых[править | править код]

Координаты и точки пересечения двух невертикальных прямых можно легко найти с помощью следующих подстановок и преобразований.

Предположим, что две прямые имеют уравнения и , где и — угловые коэффициенты прямых, а и — пересечения прямых с осью y. В точке пересечения прямых (если они пересекаются), обе координаты будут совпадать, откуда получаем равенство:

.

Мы можем преобразовать это равенство с целью выделения ,

,

а тогда

.

Чтобы найти координату y, всё что нам нужно, это подставить значение x в одну из формул прямых, например, в первую:

.

Отсюда получаем точку пересечения прямых

.

Заметим, что при a = b две прямые параллельны. Если при этом c ≠ d, прямые различны и не имеют пересечений, в противном же случае прямые совпадают ^[2].

Использование однородных координат[править | править код]

При использовании однородных координат точка пересечения двух явно заданных прямых может быть найдена достаточно просто. В 2-мерном пространстве любая точка может быть определена как проекция 3-мерной точки, заданной тройкой . Отображение 3-мерных координат в 2-мерные происходит по формуле . Мы можем преобразовать точки в 2-мерном пространстве в однородные координаты, приравняв третью координату единице — .

Предположим, что мы хотим найти пересечение двух бесконечных прямых в 2-мерном пространстве, которые заданы формулами и . Мы можем представить эти две прямые в линейных координатах^[en] как и ,

Пересечение двух прямых тогда просто задаётся формулами ^[3]

Если , прямые не пересекаются.

Пересечение n прямых[править | править код]

Существование и выражение пересечения[править | править код]

В двухмерном пространстве[править | править код]

В двухмерном пространстве прямые числом больше двух почти достоверно не пересекаются в одной точке. Чтобы определить, пересекаются ли они в одной точке, и, если пересекаются, чтобы найти точку пересечения, запишем i-ое уравнение (i = 1, …,n) как и скомпонуем эти уравнения в матричный вид

где i-ая строка n × 2 матрицы A равна , w является 2 × 1 вектором (x, y)^T, а i-ый элемент вектора-столбца b равен b_i. Если столбцы матрицы A независимы, ранг матрицы равен 2. Тогда и только тогда, когда ранг расширенной матрицы^[en] [A | b ] равен также 2, существует решение матричного уравнения, а тогда существует и точка пересечения n прямых. Точка пересечения, если таковая существует, задаётся формулой

где — псевдообратная матрица матрицы . Альтернативно решение может быть найдено путём решения любых двух независимых уравнений. Но если ранг матрицы A равен 1, а ранг расширенной матрицы равен 2, решений нет. В случае же, когда ранг расширенной матрицы равен 1, все прямые совпадают.

В трёхмерном пространстве[править | править код]

Представленный выше подход без труда распространяется на трёхмерное пространство. В трёхмерном и более высоких пространствах даже две прямые почти наверняка не пересекаются. Пары непараллельных непересекающихся прямых называются скрещивающимися. Но когда пересечение существует, его можно найти следующим образом.

В трёхмерном пространстве прямая представляется пересечением двух плоскостей, каждая из которых задаётся формулой Тогда множество n прямых может быть представлено в виде 2n уравнений от 3-мерного координатного вектора w = (x, y, z)^T:

,

где A — матрица 2n × 3, а b — 2n × 1. Как и ранее, единственная точка пересечения существует тогда и только тогда, когда A имеет полный ранг по столбцам, а расширенная матрица [A | b ] таковой не является. Единственная точка пересечения, если существует, задаётся формулой

Ближайшая точка к непересекающимся прямым[править | править код]

В размерностях два и выше можно найти точку, которая является ближайшей к этим двум (или более) прямым в смысле наименьшей суммы квадратов.

В двухмерном пространстве[править | править код]

В случае двухмерного пространства представим прямую i как точку на прямой и единичную нормаль , перпендикулярную прямой. То есть, если и — точки на прямой 1, то пусть и

,

который является единичным вектором вдоль прямой, повёрнутым на 90º.

Заметим, что расстояние от точки x до прямой задаётся формулой

Следовательно, квадрат расстояния от x до прямой равен

Сумма квадратов расстояний до набора прямых является целевой функцией:

Выражение можно преобразовать:

Чтобы найти минимум, продифференцируем по x и приравняем результат нулю:

Таким образом,

откуда

В трёхмерном пространстве[править | править код]

Хотя в размерностях выше двух нормаль не определить, его можно обобщить на любую размерность, если заметить, что является просто (симметричной) матрицей со всеми собственными значениями, равными единице, кроме нулевого собственного значения в направлении прямой, что задаёт полунорму между точкой и другой точкой. В пространстве любой размерности, если является единичным вектором вдоль i-ой прямой, то

превращается в ,

где E — единичная матрица, а тогда

См. также[править | править код]

• Пересечение отрезков
• Расстояние от точки до прямой на плоскости
• Аксиома параллельности Евклида

Примечания[править | править код]

Литература[править | править код]

• Б. Н. Делоне, Д. А. Райков. Аналитическая геометрия. — М., Л.: ОГИЗ, Государственнон издательство технико-теоретической литературы, 1948. — Т. 1.

Ссылки[править | править код]

• Distance between Lines and Segments with their Closest Point of Approach, applicable to two, three, or more dimensions.

Была ли эта статья полезной?

Точка пересечения двух прямых на плоскости

Графический метод решения. Используя уравнения, начертить графики прямых и с помощью линейки найти координаты точки пересечения.

Точка пересечения двух прямых в пространстве

Замечание. Если уравнения прямых заданы параметрически, и в обоих уравнениях параметр задан одной и той же буквой, то при составлении системы в одном из уравнений необходимо заменить букву отвечающую за параметр.