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

Не такая тривиальная задача, скажу я вам. Всякий раз, когда возникает необходимость посчитать координату пересечения пары прямых, каждая из которых задана парой точек, снова беру блокнот и вывожу пару формул. И всякий раз – блин, ну это уже когда-то было, опять надо что-то делать с параллельными прямыми, опять появляется пакостная строго вертикальна линия, когда на (x₁-x₂) никак не разделить и т.д.

Поэтому – в подборку теории и практики, пригодится, сэкономим блокнот, спасем дерево.

Коэффициенты А, B, C

Все помним со школы формулу:

Тоже самое, но с претензией на образование (некоторые индивидуумы утверждают, что существует такая, и только такая, и никакая другая, формулировка):

Те же фаберже, только сбоку.

В теории надо составить и решить систему уравнений для первой и второй линии, где переменными будут X и Y точки пересечения.

Загвоздка в том, что мы не знаем коэффициенты для обеих линий.

В нашем случае известны координаты двух точек, по которым проходит линия. Поэтому мне, как последователю геометрического агностицизма, более привлекательная следующая формула:

Путем несложных операций приходим к следующей записи:

Глядя на вариант в исполнении высшего образования, получаем следующие формулы для нахождения коэффициентов:

Пока все идет отлично, нигде вероятного деления на ноль не встретилось.

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

Система уравнений

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

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

Сразу же запишем метод под нашу систему.

Имеем следующую систему:

Определители будут такими:

Исходя из метода, решение выглядит так:

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

Практика 1

Частные случаи

• Прямые параллельны: ∆_ab = 0
  • (A₁B₂ – B₁A₂ = 0);
• Прямые совпадают:  ∆_ab = ∆_X = ∆_Y = 0 
  • (A₁B₂ – B₁A₂ = 0) И (A₁C₂ — A₂C₁ = 0) И (C₁B₂ -B₁C₂ = 0);
• Прямые перпендикулярны:
  • (A₁ A₂ + B₁ B₂ = 0).

Принадлежность точки отрезку

В общем случае, чтобы определить принадлежность точки отрезку, надо установить две вещи:

1. Точка принадлежит прямой, проходящей через конечные точки отрезка. Для этого достаточно подставить значение X и Y в уравнение прямой и проверить получившееся равенство. В нашем случае, этот пункт уже выполнен, т.к. точка пересечения априори принадлежит обеим прямым.
2. Проверить факт нахождения точки между концами отрезка.

Займемся пунктом 2. Данный факт можно установить двумя способами:

• Логически, т.е. (x₁ <= x <= x₂) ИЛИ (x₁ >= x >= x₂). На случай «вертикальности» линии добавить проверку на Y:
  • (y₁ <= y <= y₂) ИЛИ (y₁ >= y >= y₂).
• Арифметически. Сумма отрезков |x-x₁| + |x-x₂| должна быть равна длине отрезка |x₁-x₂|. Аналогично, на случай «вертикальности» , добавить проверку:
  • |y-y₁| + |y-y₂| = |y₁-y₂|

Практика показывает, что арифметический способ быстрее примерно в 3 раза. Когда-то я считал, что операции сравнения самые быстрые. Это давно уже не так.

Задача нахождения принадлежности точки P(x,y) отрезку, заданного двумя точками с координатами P1(x1, y1) и P2(x2, y2) подробно рассмотрена в отдельной статье.

Угол пересечения прямых

Угол пересечения прямых — это угол пересечения направляющих векторов. Т.е., взяв уже знакомые ранее точки p₁ и p₂, получим направляющий вектор V(p₁,p₂), и аналогично второй вектор M(p₃,p₄). В теории мы должны вычислить достаточно «затратную» функцию, с корнями, квадратами, дробями и арккосинусом.

Давайте не будем останавливаться на ней, она долгая, нудная и в нашем случае ненужная. Рассмотрим вектор:

α — угол наклона вектора к оси X, который можно найти, как:

α = arctan (A₁ / B₁)

Где расстояния:

A₁ = (y₁ — y₂)

B₁ = (x₂ — x₁)

Что-то знакомое? Да это ни что иное, как коэффициенты в уравнении прямой от образованных фанатов. Может они и правы в своем испепеляющем фанатизме…

Одним словом, коэффициенты (расстояния) у нас уже есть по обеим прямым.

Судя по рисунку, угол между векторами, это сумма углов наклона векторов к оси X. Ммм… не совсем так, на самом деле это разность.

По рисунку явно видно, что угол между векторам это γ = (β — α).

В предыдущем примере все правильно, просто знаки углов разные, т.к. находятся по разные стороны от оси X, а формула работает та же.

От теории к практике

Теперь в плане практического применения. Мне нужно точно знать, откуда, куда и в каком направлении этот угол. В теории, углом между прямыми считается наименьший из пары γ и (180-γ). Так вот, нам это не надо. Какой угол получится – такой нам и нужен.

Поэтому, под углом между векторами понимаем угол от вектора V(p1,p2) к вектору M(p3,p4). Если знак угла – отрицательный, понимаем, что он против часовой стрелки, иначе – по часовой стрелке.

Следует заметить, что, зная коэффициенты, для нахождения угла пересечения, координаты уже не нужны. Листинг таков:

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

Практика 2

В дополнение к функции нахождения точки пересечения, напишем «продвинутую» функцию, которая находит эту точку, определяет нахождение на каждом из отрезков, и определяет угол между направляющими векторами. Или же определяет, что прямые параллельны/совпадают.

Исходники

Небольшие комментарии по интерфейсу.

Скачать (219 Кб): Исходники (Delphi XE 7-10)

Скачать (1.14 Мб): Исполняемый файл

При запуске генерируется случайным образом 4 точки, по две на прямую. Точки и отрезки можно перетаскивать мышкой. Также, слева присутствует панель, на которой можно ввести координаты точек или коэффициенты уравнения прямой. При нажатии «Enter» или когда элемент ввода теряет фокус, происходит перерасчет и перерисовка.

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

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

По умолчанию, рабочее поле системы координат имеет размерность [-10..10], которую можно изменить ползунком в нижнем правом углу.

5.5.5. Пересекающиеся прямые в пространстве

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

Первая мысль – всеми силами навалиться на точку пересечения .

И тут сразу же подумалось, зачем себе отказывать в правильных желаниях?! Давайте навалимся на неё прямо сейчас!

Как найти точку пересечения пространственных прямых?

Собственно:

Задача 156

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

Решение: Перепишем уравнения прямых в параметрической форме:

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

прямых.

Точка пересечения прямых  принадлежит прямой , поэтому её координаты  удовлетворяют параметрическим уравнениям данной прямой, и им соответствует вполне конкретное значение

параметра :

Но эта же точка принадлежит и второй прямой, следовательно, существует значение , такое, что:

Приравниваем соответствующие уравнения и проводим упрощения:

Получена система трёх линейных уравнений с двумя неизвестными, которую опять же решим «школьным» способом. Из 1-го уравнения выразим  – подставим в два нижних уравнения:

В результате получилась совместная система, из которой следует, что . Тогда:

Подставим найденное значение параметра  в уравнения координат точки:
, и для проверки подставим значение  в уравнения:

Ответ:

Теперь рассмотрим особый случай пересечения прямых:

5.5.6. Как найти прямую, перпендикулярную данной?

5.5.4. Как найти расстояние между скрещивающимися прямыми?

| Оглавление |



Автор: Aлeксaндр Eмeлин

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

С помощю этого онлайн калькулятора можно найти точку пересечения прямых в пространстве. Дается подробное решение с пояснениями. Для нахождения координат точки пересечения прямых задайте вид уравнения прямых («канонический» или «параметрический» ), введите коэффициенты уравнений прямых в ячейки и нажимайте на кнопку «Решить». Теоретическую часть и численные примеры смотрите ниже.

Точка пересечения прямых в пространстве − теория, примеры и решения

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

Пусть задана декартова прямоугольная система координат Oxyz и пусть в этой системе координат заданы прямые L₁ и L₂:

,

(1)

,

(2)

где M₁(x₁, y₁, z₁) и M₂(x₂, y₂, z₂) − точки, лежащие на прямых L₁ и L₂, соответственно, а q₁={m₁, p₁, l₁} и q₂={m₂, p₂, l₂} − направляющие векторы прямых L₁ и L₂, соответственно.

Найти точку пересечения прямых L₁ и L₂ (Рис.1).

Запишем уравнение (1) в виде системы двух линейных уравнений:

Сделаем перекрестное умножение в уравнениях (3) и (4):

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Аналогичным образом преобразуем уравнение (2):

Запишем уравнение (2) в виде системы двух линейных уравнений:

Сделаем перекрестное умножение в уравнениях (7) и (8):

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Решим систему линейных уравнений (5), (6), (9), (10) с тремя неизвестными x, y, z. Для этого представим эту систему в матричном виде:

Как решить систему линейных уравнений (11)(или (5), (6), (9), (10)) посмотрите на странице Метод Гаусса онлайн. Если система линейных уравнениий (11) несовместна, то прямые L₁ и L₂ не пересекаются. Если система (11) имеет множество решений, то прямые L₁ и L₂ совпадают. Единственное решение системы линейных уравнений (11) указывает на то, что это решение определяет координаты точки пересечения прямых L₁ и L₂ .

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

Пусть задана декартова прямоугольная система координат Oxyz и пусть в этой системе координат заданы прямые L₁ и L₂ в параметрическом виде:

где M₁(x₁, y₁, z₁) и M₂(x₂, y₂, z₂) − точки, лежащие на прямых L₁ и L₂, соответственно, а q₁={m₁, p₁, l₁} и q₂={m₂, p₂, l₂} − направляющие векторы прямых L₁ и L₂, соответственно.

Задачу нахождения нахождения точки пересечения прямых L₁ и L₂ можно решить разными методами.

Метод 1. Приведем уравнения прямых L₁ и L₂ к каноническому виду.

Для приведения уравнения (12) к каноническому виду, выразим параметр t через остальные переменные:

Так как левые части уравнений (14) равны, то можем записать:

Аналогичным образом приведем уравнение прямой L₂ к каноническому виду:

Далее, для нахождения точки пересечения прямых, заданных в каноническом виде нужно воспользоваться параграфом 1.

Метод 2. Для нахождения точки пересечения прямых L₁ и L₂ решим совместно уравнения (12) и (13). Из уравнений (12) и (13) следует:

Из каждого уравнения (17),(18),(19) находим переменную t. Далее из полученных значений t выбираем те, которые удовлетворяют всем уравнениям (17)−(19). Если такое значение t не существует, то прямые не пересекаются. Если таких значений больше одного, то прямые совпадают. Если же такое значение t единственно, то подставляя это зачение t в (12) или в (13), получим координаты точки пересечения прямых (12) и (13).

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

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

4. Примеры нахождения точки пересечения прямых в пространстве.

Пример 1. Найти точку пересечения прямых L₁ и L₂:

Представим уравнение (20) в виде двух уравнений:

Сделаем перекрестное умножение в уравнениях (22) и (23):

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Упростим:

Аналогичным образом поступим и с уравнением (2).

Представим уравнение (2) в виде двух уравнений:

Сделаем перекрестное умножение в уравнениях (7) и (8)

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Упростим:

Решим систему линейных уравнений (24), (25), (28), (29) с тремя неизвестными x, y, z. Для этого представим эту систему в виде матричного уравнения:

Решим систему линейных уравнений (30) отностительно x, y, z. Для решения системы, построим расширенную матрицу:

Обозначим через a_ij элементы i-ой строки и j-ого столбца.

Первый этап. Прямой ход Гаусса.

Исключим элементы 1-го столбца матрицы ниже элемента a_{1 1}. Для этого сложим строку 3 со строкой 1, умноженной на −1:

Исключим элементы 2-го столбца матрицы ниже элемента a₂₂. Для этого сложим строку 4 со строкой 2, умноженной на −1/4:

Сделаем перестановку строк 3 и 4.

Второй этап. Обратный ход Гаусса.

Исключим элементы 3-го столбца матрицы выше элемента a₃₃. Для этого сложим строку 2 со строкой 3, умноженной на −4/3:

Исключим элементы 2-го столбца матрицы выше элемента a₂₂. Для этого сложим строку 1 со строкой 2, умноженной на 3/4:

Делим каждую строку матрицы на соответствующий ведущий элемент (если ведущий элемент существует):

Запишем решение:

Ответ. Точка пересечения прямых L₁ и L₂ имеет следующие координаты:

Пример 2. Найти точку пересечения прямых L₁ и L₂:

Приведем параметрическое уравнение прямой L₁ к каноническому виду. Выразим параметр t через остальные переменные:

Из равентсв выше получим каноническое уравнение прямой:

Представим уравнение (33) в виде двух уравнений:

Сделаем перекрестное умножение в уравнениях (34 и (35):

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Упростим:

Аналогичным образом поступим и с уравнением (2).

Представим уравнение (2) в виде двух уравнений:

Сделаем перекрестное умножение в уравнениях (38) и (39)

Откроем скобки и переведем переменные в левую часть уравнений а остальные элементы в правую часть:

Упростим:

Решим систему линейных уравнений (36), (37), (40), (41) с тремя неизвестными x, y, z. Для этого представим эту систему в виде матричного уравнения:

Решим систему линейных уравнений (42) отностительно x, y, z. Для решения системы, построим расширенную матрицу:

Обозначим через a_ij элементы i-ой строки и j-ого столбца.

Первый этап. Прямой ход Гаусса.

Исключим элементы 1-го столбца матрицы ниже элемента a_{1 1}. Для этого сложим строку 3 со строкой 1, умноженной на −1/6:

Исключим элементы 2-го столбца матрицы ниже элемента a₂₂. Для этого сложим строки 3 и 4 со строкой 2, умноженной на 8/21 и −1/7, соответственно:

Исключим элементы 3-го столбца матрицы ниже элементаa₃₃. Для этого сложим строку 4 со строкой 3, умноженной на -1/16:

Из расширенной матрицы восстановим последнюю систему линейных уравнений:

Уравнение (43) несовместна, так как несуществуют числа x, y, z удовлетворяющие уравнению (43). Следовательно система линейных уравнений (42) не имеет решения. Тогда прямые L₁ и L₂ не пересекаются. То есть они или параллельны, или скрещиваются.

Прямая L₁ имеет направляющий вектор q₁={2,6,7}, а прямая L₂ имеет направляющий вектор q₂={3,1,1}. Эти векторы не коллинеарны. Следовательно прямые L₁ и L₂ скрещиваются .

Ответ. Прямые L₁ и L₂ не пересекаются.

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

Введение

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

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

Возможно, многие вспомнят способ из школьной алгебры — составить уравнения двух прямых, приравнять их правые части, найти 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;
}

Послесловие

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