admin / 22.06.2018

Пересекаются ли прямые

.

3.3 Прямая в пространстве

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

Задача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
Да.

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

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

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

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

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

 

Поделиться с друзьями

Пусть даны два отрезка. Первый задан точками P1(x1;y1) и P2(x2;y2). Второй задан точками P3(x3;y3) и P4(x4;y4).

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

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

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

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

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

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

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

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

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

Пусть на прямой заданы две не совпадающие точки:P1 с координатами (x1;y1) и P2 с координатами (x2; y2).

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

Соответственно вектор с началом в точке P1 и концом в точке P2 имеет координаты (x2-x1, y2-y1). Если P(x, y) – произвольная точка на прямой, то координаты вектора P1P равны (x — x1, y – y1).

С помощью векторного произведения условие коллинеарности векторов P1P и P1P2 можно записать так:
|P1P,P1P2|=0, т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1)=0
или
(y2-y1)x + (x1-x2)y + x1(y1-y2) + y1(x2-x1) = 0

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

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

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

ax1+by1=-c1
ax2+by2=-c2
    (2)

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

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

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*

Open

Close