Пусть даны два отрезка. Первый задан точками P 1 (x 1 ;y 1) и P 2 (x 2 ;y 2) . Второй задан точками P 3 (x 3 ;y 3) и P 4 (x 4 ;y 4) .

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

Рассмотрим отрезок P 3 P 4 и точки P 1 и P 2 .

Точка P 1 лежит слева от прямой P 3 P 4 , для нее векторное произведение v 1 > 0 , так как векторы положительно ориентированы.
Точка P 2 расположена справа от прямой, для нее векторное произведение v 2 < 0 , так как векторы отрицательно ориентированы.

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

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

Итак, если v 1 v 2 < 0 и v 3 v 4 < 0 , то отрезки пересекаются.

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

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

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

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

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

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

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

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

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

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

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

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

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

Решение

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

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

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

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

Реализация

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() будет использоваться для реализации операции сравнения “<” (строго меньше) для вещественных чисел.

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

Решение
. Второй задан точками .

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

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

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

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

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

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

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

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

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

Program geometr4; {Пересекаются ли 2 отрезка?} Const _Eps: Real=1e-4; {точность вычслений} var x1,y1,x2,y2,x3,y3,x4,y4: real; var v1,v2,v3,v4: real;function RealLess(Const a, b: Real): Boolean; {Строго меньше} begin RealLess:= b-a> _Eps end; {RealLess}function VektorMulti(ax,ay,bx,by:real): real; {ax,ay — координаты a bx,by — координаты b } begin vektormulti:= ax*by-bx*ay; end;Function LinesCross(x1,y1,x2,y2,x3,y3,x4,y4:real): boolean; {Пересекаются ли отрезки?} begin v1:=vektormulti(x4-x3,y4-y3,x1-x3,y1-y3); v2:=vektormulti(x4-x3,y4-y3,x2-x3,y2-y3); v3:=vektormulti(x2-x1,y2-y1,x3-x1,y3-y1); v4:=vektormulti(x2-x1,y2-y1,x4-x1,y4-y1); if RealLess(v1*v2,0) and RealLess(v3*v4,0) {v1v2<0 и v3v4<0, отрезки пересекаются} then LinesCross:= true else LinesCross:= false end; {LinesCross}begin {main} writeln(‘Введите координаты отрезков: x1,y1,x2,y2,x3,y3,x4,y4’); readln(x1,y1,x2,y2,x3,y3,x4,y4); if LinesCross(x1,y1,x2,y2,x3,y3,x4,y4) then writeln (‘Да’) else writeln (‘Нет’) end.

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

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

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

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

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

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

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

Пусть даны два отрезка. Первый задан точками P 1 (x 1 ;y 1) и P 2 (x 2 ;y 2) . Второй задан точками P 3 (x 3 ;y 3) и P 4 (x 4 ;y 4) .

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

Рассмотрим отрезок P 3 P 4 и точки P 1 и P 2 .

Точка P 1 лежит слева от прямой P 3 P 4 , для нее векторное произведение v 1 > 0 , так как векторы положительно ориентированы.
Точка P 2 расположена справа от прямой, для нее векторное произведение v 2 < 0 , так как векторы отрицательно ориентированы.

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

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

Итак, если v 1 v 2 < 0 и v 3 v 4 < 0 , то отрезки пересекаются.

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

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

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

Пусть на прямой заданы две не совпадающие точки:P 1 с координатами (x 1 ;y 1) и P 2 с координатами (x 2 ; y 2) .

Пересечение прямых

Соответственно вектор с началом в точке P 1 и концом в точке P 2 имеет координаты (x 2 -x 1 , y 2 -y 1) . Если P(x, y) – произвольная точка на прямой, то координаты вектора P 1 P равны (x — x 1 , y – y 1).

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

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

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

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

ax 1 +by 1 =-c 1
ax 2 +by 2 =-c 2 (2)

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

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