добавлено: 11 Jun 2008 10:19
редактировано: 7 Jul 2009 17:57

Точка пересечения прямых

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

Решение

Если две прямые не параллельны, то они пересекаются. Чтобы найти точку пересечения, достаточно составить из двух уравнений прямых систему и решить её:

Пользуясь формулой Крамера, сразу находим решение системы, которое и будет искомой точкой пересечения:

Если знаменатель нулевой, т.е.

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

Реализация

struct pt {double x, y;};   struct line {double a, b, c;};   constdouble EPS =1e-9;   double det (double a, double b, double c, double d){return a * d — b * c;}   bool intersect (line m, line n, pt & res){double zn = det (m.a, m.b, n.a, n.b);if(abs(zn)< EPS)returnfalse; res.x=- det (m.c, m.b, n.c, n.b)/ zn; res.y=- det (m.a, m.c, n.a, n.c)/ zn;returntrue;}   bool parallel (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS;}   bool equivalent (line m, line n){returnabs(det (m.a, m.b, n.a, n.b))< EPS &&abs(det (m.a, m.c, n.a, n.c))< EPS &&abs(det (m.b, m.c, n.b, n.c))< EPS;}

Урок из серии «Геометрические алгоритмы»

Здравствуйте,  дорогой читатель.

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

Напишем еще три новые функции.

Функция LinesCross() будет определять, пересекаются ли два отрезка. В ней взаимное расположение отрезков определяется с помощью векторных произведений. Для вычисления векторных произведений напишем  функцию – VektorMulti().

Функция RealLess() будет использоваться для реализации операции сравнения  “<” (строго меньше) для вещественных чисел.

Решение
Пусть даны два отрезка. Первый задан точками . Второй задан точками .

Рассмотрим отрезок и точки и .

Точка расположена справа от прямой, для нее векторное произведение < 0, так как векторы отрицательно ориентированы.

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

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

Итак, если , то отрезки пересекаются.

Для проверки этого условия используется функцию LinesCross(), а для вычисления векторных произведений – функция VektorMulti().

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

где:

ax, ay – координаты первого вектора,

bx, by – координаты второго вектора.

Результаты выполнения программы:

Введите координаты отрезков: -1  1 2 2.52 2 1 -1 3
Да.

Мы написали программу, определяющую, пересекаются ли отрезки, заданные своими координатами.

На следующем уроке мы составим алгоритм, с помощью которого можно будет определить, лежит ли точка внутри треугольника.

Уважаемый читатель.

Вы уже познакомились с несколькими уроками из серии «Геометрические алгоритмы». Все ли доступно написано? Я буду Вам очень признательна, если Вы оставите отзыв об этих уроках. Возможно, что-то нужно еще доработать.

С уважением, Вера Господарец.

Пусть даны два отрезка. Первый задан точками 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₄.

Итак, если v₁v₂ < 0 и v₃v₄ < 0, то отрезки пересекаются.

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

где:
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₁).

С помощью векторного произведения условие коллинеарности векторов P₁P и P₁P₂ можно записать так:
|P₁P,P₁P₂|=0, т.е. (x-x₁)(y₂-y₁)-(y-y₁)(x₂-x₁)=0
или
(y₂-y₁)x + (x₁-x₂)y + x₁(y₁-y₂) + y₁(x₂-x₁) = 0

Последнее уравнение переписывается следующим образом:
ax + by + c = 0,     (1)
где
a = (y₂-y₁),
b = (x₁-x₂),
c = x₁(y₁-y₂) + y₁(x₂-x₁)

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

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

ax₁+by₁=-c₁
ax₂+by₂=-c₂     (2)

Ввести обозначения:

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