Пересечение отрезков на плоскости c. Определение точки пересечения двух отрезков. Точка пересечения прямых
Точка пересечения прямых
Пусть нам даны две прямые, заданные своими коэффициентами и . Требуется найти их точку пересечения, или выяснить, что прямые параллельны.
Решение
Если две прямые не параллельны, то они пересекаются. Чтобы найти точку пересечения, достаточно составить из двух уравнений прямых систему и решить её:
Пользуясь формулой Крамера, сразу находим решение системы, которое и будет искомой точкой пересечения :
Если знаменатель нулевой, т.е.
то система решений не имеет (прямые параллельны и не совпадают) или имеет бесконечно много (прямые совпадают ). Если необходимо различить эти два случая, надо проверить, что коэффициенты прямых пропорциональны с тем же коэффициентом пропорциональности, что и коэффициенты и , для чего достаточно посчитать два определителя, если они оба равны нулю, то прямые совпадают:
Реализация
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 , которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
Пусть даны два отрезка. Первый задан точками 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 , которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.