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

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

x1 t + x2 (1 — t) = a1 s + a2 (1 — s)
y1 t + y2 (1 — t) = b1 s + b2 (1 — s)

Пусть даны два отрезка. Первый задан точками P₁(x₁;y₁) и P₂(x₂;y₂). Второй задан точками P₃(x₃;y₃) и P₄(x₄;y₄).

Взаимное расположение отрезков можно проверить с помощью векторных произведений:

Рассмотрим отрезок P₃P₄ и точки P₁ и P₂.

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

где:
ax, ay — координаты первого вектора,
bx, by — координаты второго вектора.

Вычислительная геометрия

Напомним, что отрезок, для которого указано, какой из его концов считается началом, а какой — концом, называется вектором. Вектор на плоскости можно задать двумя числами — его координатами по горизонтали и вертикали.

vector

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

Скалярное произведение (англ. dot product) — произведение длин векторов на косинус угла между ними. Для него справедлива следующая формула:

\[ a \cdot b = x_a x_b + y_a y_b \]

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

Геометрически, она равна проекции вектора \(b\) на вектор \(a\) , помноженный на длину \(а\) :

dot

У него есть полезные свойства:

• Скалярное произведение симметрично ( \(a \cdot b = b \cdot a\) ).
• Перпендикулярные вектора должны иметь нулевое скалярное произведение.
• Если угол острый, то скалярное произведение положительное.
• Если угол тупой, то скалярное произведение отрицательное.

Векторное произведение (англ. cross product) — произведение длин векторов на синус угла между ними, причём знак этого синуса зависит от порядка операндов. Оно тоже удобно выражается в координатах:

\[ a \times b = x_a y_b — y_a x_b \]

Геометрически, это ориентированный объем параллелограмма, натянутого на вектора \(a\) и \(b\) :

cross

• Векторное произведение антисимметрично: \(a \times b = — (b \times a)\) .
• Коллинеарные вектора должны иметь нулевое векторное произведение.
• Если \(b\) «слева» от \(a\) , то векторное произведение положительное.
• Если \(b\) «справа» от \(a\) , то векторное произведение отрицательное.

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

Всякие проверки

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

Принадлежность точки треугольнику. Пусть у нас есть треугольник \(ABC\) (заданный против часовой стрелки) и точка \(P\) . Тогда она должна лежать слева от всех трёх векторов \(AB\) , \(BC\) и \(CA\) . Это условие задаст пересечение трёх полуплоскостей, которое и будет нужным треугольником.

\[ \text

\iff \begin (B-A) \times (P-A) \geq 0 \\ (C-B) \times (P-B) \geq 0 \\ (A-C) \times (P-C) \geq 0 \\ \end \]

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

Площадь произвольного многоугольника. Если многоугольник задан последовательностью вершин в каком-то порядке, то можно считать так: для каждого ребра добавим его ориентированную площадь от начала координат. Какие-то слагаемые будут положительными (которые на последнем слое, а какие-то — отрицательными).

any

Забудьте о формуле Герона и всегда считайте площади через векторное произведение.

Кстати, из формулы для площади треугольника следует, что площадь любой фигуры будет либо целым числом, либо рациональным с двойкой в знаменателе. Часто в в задачах входные данные целочисленные, и, чтобы оставаться в целых числах, когда мы считаем какую-нибудь площадь, иногда имеет смысл умножить все входные числа на \(2\) (см. «точность»).

Проверка на выпуклость. Можно пройтись по сторонам многоугольника и проверять векторным произведением, что мы поворачиваем всегда в одну сторону, то есть для всех последовательных точек \(a\) , \(b\) , \(c\) проверить, что \((b-a)\times(c-a) > 0\) .

Пересекаются ли отрезки.

segments

Уравнение прямой

Прямую можно задать уравнением вида \(Ax + By + C = 0\) . Полуплоскость можно задать таким же неравенством.

У прямой есть вектор нормали с координатами \((A, B)\) . Он перпендиуклярен прямой, а в случае с полуплоскостью \(Ax + By + C \geq 0\) будет указывать в сторону самой полуплоскости.

Чтобы найти расстояние от точки \((x_0, y_0)\) до прямой \(Ax + By + C = 0\) , можно воспользоваться следующей формулой:

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

\[ \begin A_1 x + B_1 y + C_1 = 0 \\ A_2 x + B_2 y + C_2 = 0 \end \implies \begin -x = \frac \\ -x = \frac \end \implies \frac = \frac \implies y = — \frac \]

Аналогично, \(x = \frac\) (обратите внимание на знаки).

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

Как это кодить в C++

Небольшой ликбез по объектно-ориентированному программированию в C++. Создадим класс, который будет отвечать за все операции с точками. В C++ есть два способа это сделать: через struct и через class . Их основное отличие в том, что по умолчанию в class все поля приватные — к ним нет прямого доступа снаружи. Это нужно для дополнительной защиты, чтобы в крупных промышленных проектах никто случайно ничего не поломал, но на олимпиадах это не очень актуально.

Точка \(\simeq\) вектор. Будем считать точка и вектор это один и тот же объект, так как они оба — это просто пара чисел. Будем сопоставлять точке её радиус-вектор — вектор из начала координат, ведущий в эту точку. По принятой в математике и физике нотации, будем обозночать вектора как r . Вы можете обозвать их как point , pt , vec — как угодно.

Функция r внутри класса вызывается при инциализации объекта. Её называют конструктором, и её можно указывать разную для разных параметров. Здесь r() вернёт точку с неопределенными (какие оказались в памяти в тот момент) координатами, а r(x, y) вернет точку с координатами \((x, y)\) .

Операции над векторами

Давайте напишем функцию, которая принимает вектора и что-то с ними делает. Например, считает длину:

Операторы

В C++ можно перегружать почти все стандартные операторы, например, + , — , << и т. д.

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

Пусть даны два отрезка. Первый задан точками P₁(x₁;y₁) и P₂(x₂;y₂). Второй задан точками P₃(x₃;y₃) и P₄(x₄;y₄).

Взаимное расположение отрезков можно проверить с помощью векторных произведений:

Рассмотрим отрезок P₃P₄ и точки P₁ и P₂.

Точка P₁ лежит слева от прямой P₃P₄, для нее векторное произведение v₁ > 0, так как векторы положительно ориентированы.
Точка P₂ расположена справа от прямой, для нее векторное произведение v₂ < 0, так как векторы отрицательно ориентированы.

Для того чтобы точки P₁ и P₂ лежали по разные стороны от прямой P₃P₄, достаточно, чтобы выполнялось условие v₁v₂ < 0 (векторные произведения имели противоположные знаки).

Аналогичные рассуждения можно провести для отрезка P₁P₂ и точек P₃ и P₄.

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

где:
ax, ay — координаты первого вектора,
bx, by — координаты второго вектора.

Уравнение прямой, проходящей через две различные точки, заданные своими координатами.

Пусть на прямой заданы две не совпадающие точки:P₁ с координатами (x₁;y₁) и P₂ с координатами (x₂; y₂). Соответственно вектор с началом в точке P₁ и концом в точке P₂ имеет координаты (x₂-x₁, y₂-y₁). Если P(x, y) – произвольная точка на прямой, то координаты вектора P₁P равны (x — x₁, y – y₁).

Итак, прямую можно задать уравнением вида (1).

Как найти точку пересечения прямых?
Очевидное решение состоит в том, чтобы решить систему уравнений прямых:

Здесь D – определитель системы, а D_x,D_y — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0, то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x₁=D_x/D, y₁=D_y/D, которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.

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

Вектор — это, грубо говоря, направление. Потому вопрос бессмысленный.

Можно говорить о пересечении отрезков или прямых. Но не векторов.

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

Если так угодно, то с натяжкой можно написать универсальный ответ, что все векторы пересекаются в точке (0, 0).

• Facebook
• Вконтакте
• Twitter

Griboks, тогда почему у вас ответ про прямые, а не вектора?
Замечу, что вектор — это отрезок, имеющий направление, что в данном случае совершенно не важно. Но вектор — это никак не прямая.

Где в вашем ответе ответ на первую часть вопроса — «Как узнать существует ли точка пересечения»?

Developer, вы, видимо, не читали мой ответ, если не увидели достаточного условия пересечения.