Разделы сайта
Выбор редакции:
- Попасть в переплет: значение фразеологизма, толкование Всякие ли трудные обстоятельства можно обозначить как «переплет»?
- Деление группы на микрогруппы
- 22 июня 1812 сражение. Можайское благочиние. Российская императорская армия
- Повесть временных лет читательский дневник
- О русском языке (сказка) Написать сказку о русском языке со смыслом
- История русской материальной культуры(3)
- Английские идиомы Как запомнить английские идиомы
- Клайв Льюис - Хроники Нарнии: Лев, Колдунья и платяной шкаф К льюис нарния читать краткое содержание
- График функции y = sin x «Йошкар-Олинский техникум сервисных технологий»
- Объём и площадь поверхности правильной четырёхугольной призмы
Реклама
Какие отрезки пересекаются а какие нет. Пересекаются ли прямые: пересечение отрезков на плоскости. Точка пересечения прямых |
Пусть даны два отрезка. Первый задан точками 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 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 , то отрезки пересекаются. Векторное произведение двух векторов вычисляется по формуле: Уравнение прямой, проходящей через две различные точки, заданные своими координатами. Пусть на прямой заданы две не совпадающие точки: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
можно записать так: Последнее уравнение переписывается следующим образом: Итак, прямую можно задать уравнением вида (1). Как найти точку пересечения прямых? ax 1 +by 1 =-c 1 Ввести обозначения: Здесь 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 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 , то отрезки пересекаются. Векторное произведение двух векторов вычисляется по формуле: Уравнение прямой, проходящей через две различные точки, заданные своими координатами. Пусть на прямой заданы две не совпадающие точки: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
можно записать так: Последнее уравнение переписывается следующим образом: Итак, прямую можно задать уравнением вида (1). Как найти точку пересечения прямых? ax 1 +by 1 =-c 1 Ввести обозначения: Здесь D – определитель системы, а D x ,D y — определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если D ≠ 0 , то система (2) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: x 1 =D x /D, y 1 =D y /D , которые называются формулами Крамера. Небольшое напоминание, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали. |
Популярное:
Новое
- Деление группы на микрогруппы
- 22 июня 1812 сражение. Можайское благочиние. Российская императорская армия
- Повесть временных лет читательский дневник
- О русском языке (сказка) Написать сказку о русском языке со смыслом
- История русской материальной культуры(3)
- Английские идиомы Как запомнить английские идиомы
- Клайв Льюис - Хроники Нарнии: Лев, Колдунья и платяной шкаф К льюис нарния читать краткое содержание
- График функции y = sin x «Йошкар-Олинский техникум сервисных технологий»
- Объём и площадь поверхности правильной четырёхугольной призмы
- Русские флотоводцы Главком ВМФ России адмирал Владимир Королёв принял участие в церемонии открытия выставки «Легендарный флотоводец»