Как найти точку пересечения отрезков

Пересечение прямых, угол и координаты пересечения

IP76 > Пересечение прямых, угол и координаты пересечения

Не такая тривиальная задача, скажу я вам. Всякий раз, когда возникает необходимость посчитать координату пересечения пары прямых, каждая из которых задана парой точек, снова беру блокнот и вывожу пару формул. И всякий раз – блин, ну это уже когда-то было, опять надо что-то делать с параллельными прямыми, опять появляется пакостная строго вертикальна линия, когда на (x1-x2) никак не разделить и т.д.

Поэтому – в подборку теории и практики, пригодится, сэкономим блокнот, спасем дерево.

Коэффициенты А, B, C

Все помним со школы формулу:

Тоже самое, но с претензией на образование (некоторые индивидуумы утверждают, что существует такая, и только такая, и никакая другая, формулировка):

Те же фаберже, только сбоку.

В теории надо составить и решить систему уравнений для первой и второй линии, где переменными будут X и Y точки пересечения.

Загвоздка в том, что мы не знаем коэффициенты для обеих линий.

В нашем случае известны координаты двух точек, по которым проходит линия. Поэтому мне, как последователю геометрического агностицизма, более привлекательная следующая формула:

Путем несложных операций приходим к следующей записи:

Глядя на вариант в исполнении высшего образования, получаем следующие формулы для нахождения коэффициентов:

Пока все идет отлично, нигде вероятного деления на ноль не встретилось.

Итак, мы можем легко найти два набора коэффициентов для первой и второй прямых. Переходим к системе уравнений.

Система уравнений

Как правило, подобная система уравнений решается путем выражения одной переменной через другую, подстановкой во второе уравнение, получая таким образом уравнение одной переменной. Далее переменная находится, подставляется, решается. Или определяется, что система решения не имеет.

Но нас интересует метод Крамера. Потому что с помощью этого метода можно получить сразу значения для обеих переменных, без дополнительных телодвижений.

Сразу же запишем метод под нашу систему.

Имеем следующую систему:

Исходя из метода, решение выглядит так:

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

Практика 1

Частные случаи

  • Прямые параллельны: ∆ab = 0
    • (A1B2 – B1A2 = 0);
  • Прямые совпадают: ∆ab = ∆X = ∆Y = 0
    • (A1B2 – B1A2 = 0) И (A1C2 — A2C1 = 0) И (C1B2 -B1C2 = 0);
  • Прямые перпендикулярны:
    • (A1 A2 + B1 B2 = 0).

Рис.2. Пересечение перпендикулярных прямых Рис.3. Параллельные прямые не пересекаются

Принадлежность точки отрезку

В общем случае, чтобы определить принадлежность точки отрезку, надо установить две вещи:

  1. Точка принадлежит прямой, проходящей через конечные точки отрезка. Для этого достаточно подставить значение X и Y в уравнение прямой и проверить получившееся равенство. В нашем случае, этот пункт уже выполнен, т.к. точка пересечения априори принадлежит обеим прямым.
  2. Проверить факт нахождения точки между концами отрезка.

Займемся пунктом 2. Данный факт можно установить двумя способами:

  • Логически, т.е. (x1 = x >= x2). На случай «вертикальности» линии добавить проверку на Y:
    • (y1 = y >= y2).
  • Арифметически. Сумма отрезков |x-x1| + |x-x2| должна быть равна длине отрезка |x1-x2|. Аналогично, на случай «вертикальности» , добавить проверку:
    • |y-y1| + |y-y2| = |y1-y2|

Практика показывает, что арифметический способ быстрее примерно в 3 раза. Когда-то я считал, что операции сравнения самые быстрые. Это давно уже не так.

Угол пересечения прямых

Угол пересечения прямых — это угол пересечения направляющих векторов. Т.е., взяв уже знакомые ранее точки p1 и p2, получим направляющий вектор V(p1,p2), и аналогично второй вектор M(p3,p4). В теории мы должны вычислить достаточно «затратную» функцию, с корнями, квадратами, дробями и арккосинусом.

Давайте не будем останавливаться на ней, она долгая, нудная и в нашем случае ненужная. Рассмотрим вектор:

Рис.4. Вектор V(p1,p2)

α — угол наклона вектора к оси X, который можно найти, как:

Что-то знакомое? Да это ни что иное, как коэффициенты в уравнении прямой от образованных фанатов. Может они и правы в своем испепеляющем фанатизме…

Одним словом, коэффициенты (расстояния) у нас уже есть по обеим прямым.

Рис.5. Пересекающиеся вектор V(p1,p2) и вектор M(p3,p4)

Судя по рисунку, угол между векторами, это сумма углов наклона векторов к оси X. Ммм… не совсем так, на самом деле это разность.

Рис.6. Пересекающиеся векторы в положительной Y

По рисунку явно видно, что угол между векторам это γ = (βα).

В предыдущем примере все правильно, просто знаки углов разные, т.к. находятся по разные стороны от оси X, а формула работает та же.

От теории к практике

Теперь в плане практического применения. Мне нужно точно знать, откуда, куда и в каком направлении этот угол. В теории, углом между прямыми считается наименьший из пары γ и (180-γ). Так вот, нам это не надо. Какой угол получится – такой нам и нужен.

Поэтому, под углом между векторами понимаем угол от вектора V(p1,p2) к вектору M(p3,p4). Если знак угла – отрицательный, понимаем, что он против часовой стрелки, иначе – по часовой стрелке.

Следует заметить, что, зная коэффициенты, для нахождения угла пересечения, координаты уже не нужны. Листинг таков:

Пересечение отрезков и поворот: определение, свойства, вычисление

Содержание

  • 1 Аффинное пространство
  • 2 Ориентация
    • 2.1 Ориентация векторов
    • 2.2 Ориентация точек
    • 2.3 Предикат левый поворот
  • 3 Пересечение отрезков
  • 4 Ссылки

Аффинное пространство [ править ]

Формальное определение есть, например, на википедии. Неформально: аффинное пространство — удобная геометрическая абстракция, рассматривающая точки (в отличие от векторов линейного пространства). Точки нельзя складывать между собой или умножать на число; к точке можно прибавить вектор, получив другую точку; можно получить вектор разности двух точек. Все приведенные операции обладают геометрически интуитивными и ожидаемыми свойствами.

Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства [math]A[/math] : [math]sum lambda_i a_i[/math] , где [math]lambda_i in mathbb, a_i in A[/math] . По определению считают [math]sum lambda_i a_i = b + sum lambda_i overrightarrow<(a_i - b)>, b in A, sum lambda_i = 1[/math]

Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы). Набор [math]_^[/math] точек называется аффинно (не-)зависимым, если линейно (не-)зависим набор векторов [math]>_^[/math] .

Ориентация [ править ]

Ориентация векторов [ править ]

Рассмотрим кососимметричную линейную форму от N N-мерных векторов, т.е. функцию [math]f: X rightarrow mathbb[/math] , обладающую свойством [math]f(x_1, x_2,hdots, x_, x_n) = -f(x_n, x_,hdots, x_2, x_1)[/math] .

Из курса линейной алгебры известно, что любые две такие формы отличаются друг от друга только на некоторый множитель. Зафиксируем одну из таких форм (например, считая, что форма равна 1 на наборе из векторов выделенного базиса). Назовем ориентацией набора из N N-мерных векторов знак значения этой формы на этом наборе векторов.

Читайте также  Крылья бабочки — прекрасная загадка природы

Отметим свойства ориентации:

  • Ориентация линейно зависимого набора векторов равна нулю
  • Ориентация меняет знак при перестановке двух векторов в наборе

Неформальное объяснение второго свойства: рассмотрим тройку векторов, таких, что если смотреть из конца первого вектора на второй, то он будет левее, чем третий. Перестановка второго и третьего векторов будет означать, что второй вектор будет виден правее третьего, что означает смену ориентации.

Заметим, что определитель является в точности кососимметричной линейной формой от N N-мерных векторов, а значит, подходит для вычисления ориентации набора векторов.

Ориентация точек [ править ]

Аналогичным образом можно определить ориентацию набора из N+1 N-мерных точек. Ориентацией точек [math]_^[/math] назовем ориентацию набора векторов [math]>_^[/math]

Нетрудно заметить, что ориентация набора точек обладает свойствами, похожими на ориентацию векторов:

  • Ориентация набора аффинно-зависимых точек равна нулю
  • Ориентация меняет знак при перестановке двух точек в наборе

Предикат левый поворот [ править ]

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

Предикат «левый поворот» по набору точек определяет, верно ли, что их ориентация — левая. Используется в большинстве алгоритмов вычислительной геометрии.

Вычислить ориентацию точек [math]_^[/math] (и, следовательно, предикат) можно через определитель набора векторов [math]>_^[/math] .

О точном вычислении ориентации см. раздел Ссылки.

Пересечение отрезков [ править ]

Определить, пересекаются ли два отрезка, можно с помощью предиката поворота. Ясно, что отрезки пересекаются тогда и только тогда, когда для каждого из отрезков его точки не лежат с одной стороны от второго отрезка. Пусть даны отрезки [math]a_0 a_1[/math] и [math]b_0 b_1[/math] . Отрезки пересекаются, если

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

Если предикат вычисления ориентации был абсолютно точным, то таким же будет описанный алгоритм.

Пересечение прямых. Точка пересечения двух прямых

Если точка M, является точкой пересечения двух прямых, то она должна принадлежать этим прямым, а ее координаты удовлетворять уравнения этих прямых.

Точка пересечения двух прямых на плоскости

Если система уравнений:

  • имеет единственное решение, то прямые пересекаются;
  • имеет бесконечное множество решений, то прямые совпадают;
  • не имеет решений, то прямые не пересекаются (прямые параллельны между собой)

Решение: Для вычисления координат точки пересечения прямых, решим систему уравнений:

y = 2 x — 1 y = -3 x + 1

Вычтем из первого уравнения второе

y — y = 2 x — 1 — (-3 x + 1) y = -3 x + 1 => 0 = 5 x — 2 y = -3 x + 1

Из первого уравнения найдем значение x

5 x = 2 y = -3 x + 1 => x = 2 5 = 0.4 y = -3 x + 1

Подставим значение x во второе уравнение и найдем значение y

x = 0.4 y = -3·(0.4) + 1 = -1.2 + 1 = -0.2

Ответ. Точка пересечения двух прямых имеет координаты (0.4, -0.2)

Решение: Для вычисления координат точки пересечения прямых, решим систему уравнений:

y = 2 x — 1 x = 2 t + 1 y = t

В первое уравнение подставим значения x и y из второго и третьего уравнений.

t = 2·(2 t + 1) — 1 x = 2 t + 1 y = t => t = 4 t + 1 x = 2 t + 1 y = t =>

-3 t = 1 x = 2 t + 1 y = t => t = — 1 3 x = 2 t + 1 y = t

Подставим значение t во второе и третье уравнение

t = — 1 3 x = 2·(- 1 3 ) + 1 = — 2 3 + 1 = 1 3 y = — 1 3

Ответ. Точка пересечения двух прямых имеет координаты ( 1 3 , — 1 3 )

Решение: Для вычисления координат точки пересечения прямых, решим систему уравнений:

2 x + 3 y = 0 x — 2 3 = y 4

Из второго уравнения выразим y через x

2 x + 3 y = 0 y = 4· x — 2 3

Подставим y в первое уравнение

2 x + 3·4· x — 2 3 = 0 y = 4· x — 2 3 => 2 x + 4·( x — 2) = 0 y = 4· x — 2 3 =>

2 x + 4 x — 8 = 0 y = 4· x — 2 3 => 6 x = 8 y = 4· x — 2 3 =>

x = 8 6 = 4 3 y = 4· x — 2 3 => x = 8 6 = 4 3 y = 4· 4/3 — 2 3 = 4· -2/3 3 = — 8 9

Ответ. Точка пересечения двух прямых имеет координаты ( 4 3 , — 8 9 )

Решение: Обе прямые заданы уравнениями с угловым коэффициентом. Так как k 1 = k 2 = 2, то прямые параллельны. Так как эти прямые не совпадают то точек пересечения нет.

Решим также эту задачу используя систему уравнений:

y = 2 x — 1 y = 2 x + 1

Вычтем из первого уравнения второе

y — y = 2 x — 1 — (2 x + 1) y = -3 x + 1 => 0 = -2 y = -3 x + 1

В первом уравнении получили противоречие (0 ≠ -2), значит система не имеет решений — отсутствуют точки пересечения прямых (прямые параллельны).

Ответ. Прямые не пересекаются (прямые параллельны).

Решение: Подставим координаты точки N в уравнения прямых.

Ответ. Так как оба уравнения превратились в тождества, то точка N — точка пересечения этих прямых.

Точка пересечения двух прямых в пространстве

Если система уравнений:

  • имеет единственное решение, то прямые пересекаются;
  • имеет бесконечное множество решений, то прямые совпадают;
  • не имеет решений, то прямые не пересекаются (прямые параллельны или скрещиваются между собой)

Решение: Составим систему уравнений

x — 1 = a y — 1 = a z — 1 = a x — 3 -2 = b 2 — y = b z = b => x = a + 1 y = a + 1 z = a + 1 x — 3 -2 = b 2 — y = b z = b =>

Подставим значения x , y , z из 1, 2, 3 уравнений в 4, 5, 6 уравнения

x = a + 1 y = a + 1 z = a + 1 a + 1 — 3 -2 = b 2 — ( a + 1) = b a + 1 = b => x = a + 1 y = a + 1 z = a + 1 a — 2 -2 = b 1 — a = b a + 1 = b

К шестому уравнению добавим пятое уравнение

x = a + 1 y = a + 1 z = a + 1 a — 2 -2 = b 1 — a = b a + 1 + (1 — a ) = b + b => x = a + 1 y = a + 1 z = a + 1 a — 2 -2 = b 1 — a = b b = 1

Подставим значение b в четвертое и пятое уравнения

x = a + 1 y = a + 1 z = a + 1 a — 2 -2 = 1 1 — a = 1 b = 1 => x = a + 1 y = a + 1 z = a + 1 a — 2 = -2 a = 0 b = 1 =>

x = a + 1 y = a + 1 z = a + 1 a = 0 a = 0 b = 1 => x = 0 + 1 = 1 y = 0 + 1 = 1 z = 0 + 1 = 1 a = 0 a = 0 b = 1

Ответ. Прямые пересекаются в точке с координатами (1, 1, 1).

Решение: Составим систему уравнений заменив во втором уравнении параметр t на a

x = 2 t — 3 y = t z = — t + 2 x = a + 1 y = 3 a — 2 z = 3

Подставим значения x , y , z из 1, 2, 3 уравнений в 4, 5, 6 уравнения

x = 2 t — 3 y = t z = — t + 2 2 t — 3 = a + 1 t = 3 a — 2 — t + 2 = 3 => x = 2 t — 3 y = t z = — t + 2 2 t = a + 4 t = 3 a — 2 t = -1 =>

Подставим значение t из шестого уравнения в остальные уравнения

x = 2·(-1) — 3 y = (-1) z = -(-1) + 2 2·(-1) = a + 4 -1 = 3 a — 2 t = -1 => x = -5 y = -1 z = 3 a = -6 a = 1 3 t = -1

Ответ. Так как -6 ≠ 1 3 , то прямые не пересекаются.

Простой алгоритм определения пересечения двух отрезков

Введение
Задача™

Даны два отрезка, каждый™ из которых задан двумя точками: (v11, v12), (v21, v22). Необходимо определить, пересекаются ли они, и если пересекаются, найти точку их пересечения.

Решение

Для начала™ необходимо определить, пересекаются ли отрезки. Необходимое и достаточное условие пересечения, которое должно™ быть соблюдено для обоих отрезков следующее: конечные точки одного™ из отрезков должны™ лежать™ в разных™ полуплоскостях, если разделить плоскость линией™, на которой лежит второй™ из отрезков. Продемонстрируем это рисунком.

На левом рисунке (1) показаны два отрезка, для обоих из которых условие соблюдено, и отрезки пересекаются. На правом™ (2) рисунке условие соблюдено для отрезка b, но для отрезка a оно не соблюдается, соответственно отрезки не пересекаются.
Может показаться, что определить, с какой стороны от линии лежит точка — нетривиальная задача™, но у страха™ глаза велики™, и всё не так сложно™. Мы знаем, что векторное умножение двух векторов даёт нам третий™ вектор™, направление которого зависит от того, положительный или отрицательный угол между первым™ и вторым™ вектором, соответственно такая операция антикоммутативна. А так как все вектора лежат на плоскости X-Y, то их векторное произведение (которое обязано быть перпендикулярным перемножаемым векторам) будет иметь ненулевой только™ компоненту Z, соответственно и отличие произведений векторов будет только™ в этой компоненте. Причем™ при изменении порядка перемножения векторов (читай: угла между перемножаемыми векторами) состоять оно будет исключительно в изменении знака этой компоненты.
Поэтому мы можем умножить попарно-векторно вектор™ разделяющего отрезка на векторы направленные от начала™ разделяющего отрезка к обеим точкам™ проверяемого отрезка.

Если компоненты Z обоих произведений будет иметь различный знак, значит™ один из углов меньше™ 0 но больше™ -180, а второй™ больше™ 0 и меньше™ 180, соответственно точки лежат по разные™ стороны от прямой™. Если компоненты Z обоих произведений имеют одинаковый знак, следовательно и лежат они по одну сторону от прямой™.
Если один из компонент Z является нулём, значит™ мы имеем пограничный случай™, когда точка лежит аккурат на проверяемой прямой™. Оставим пользователю определять, хочет ли он считать это пересечением.
Затем нам необходимо повторить операцию для другого отрезка и прямой™, и убедиться в том, что расположение его конечных точек также удовлетворяет условию.
Итак, если всё хорошо™ и оба отрезка удовлетворяют условию, значит™ пересечение существует. Давайте найдём™ его, и в этом нам также поможет векторное произведение.
Так как в векторном произведении мы имеем ненулевой лишь компоненту Z, то его модуль™ (длина вектора) будет численно равен именно™ этой компоненте. Давайте посмотрим, как найти точку пересечения.

Длина векторного произведения векторов a и b (как мы выяснили, численно равная™ его компоненте Z) равна произведению модулей этих векторов на синус угла между ними (|a| |b| sin(ab)). Соответственно, для конфигурации на рисунке мы имеем следующее: |AB x AC| = |AB||AC|sin(α), и |AB x AD| = |AB||AD| sin(β). |AC|sin(α) является перпендикуляром, опущенным из точки C на отрезок AB, а |AD|sin(β) является перпендикуляром, опущенным из точки D на отрезок AB (катетом ADD’). Так как углы γ и δ — вертикальные углы, то они равны, а значит™ треугольники PCC’ и PDD’ подобны, а соответственно и длины всех их сторон™ пропорциональны в равном™ отношении.
Имея Z1 (AB x AC, а значит™ |AB||AC|sin(α) ) и Z2 (AB x AD, а значит™ |AB||AD|sin(β) ), мы можем рассчитать CC’/DD’ (которая будет равна Z1/Z2), а также зная что CC’/DD’ = CP/DP легко можно высчитать местоположение точки P. Лично я делаю это следующим образом:

Px = Cx + (Dx-Cx)*|Z1|/|Z2-Z1|;
Py = Cy + (Dy-Cy)*|Z1|/|Z2-Z1|;

Вот и все. Мне кажется что это действительно очень просто™, и элегантно. В заключение хочу привести код функции, реализующий данный™ алгоритм. В функции использован самодельный шаблон™ vector™ , который является шаблоном вектора размерностью int с компонентами типа typename. Желающие легко могут подогнать функцию к своим типам векторов.

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

С помощю этого онлайн калькулятора можно найти точку пересечения прямых на плоскости. Дается подробное решение с пояснениями. Для нахождения координат точки пересечения прямых задайте вид уравнения прямых («канонический», «параметрический» или «общий»), введите коэффициенты уравнений прямых в ячейки и нажимайте на кнопку «Решить». Теоретическую часть и численные примеры смотрите ниже.

Предупреждение

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Точка пересечения прямых на плоскости − теория, примеры и решения

  • Содержание
  • 1. Точка пересечения прямых, заданных в общем виде.
  • 2. Точка пересечения прямых, заданных в каноническом виде.
  • 3. Точка пересечения прямых, заданных в параметрическом виде.
  • 4. Точка пересечения прямых, заданных в разных видах.
  • 5. Примеры нахождения точки пересечения прямых на плоскости.

1. Точка пересечения прямых, заданных в общем виде.

Пусть задана декартова прямоугольная система координат Oxy и пусть в этой системе координат заданы прямые L1 и L2:

L1: A1x+B1y+C1=0, (1)
L2: A2x+B2y+C2=0 (2)

Для нахождения точки пересечения прямых (1) и (2) нужно решить систему линейных уравнений (1) и (2) относительно переменных x,y. Для этого запишем систему (1),(2) в матричном виде:

(3)

Построим расширенную матрицу:

(4)

Приведем (4) к верхнему диагональному виду. Пусть A1≠0 . Тогда сложим строку 2 со строкой 1, умноженной на −A2/A1:

(5)

Если B’2=0 и С’2=0, то система линейных уравнений имеет множество решений. Следовательно прямые L1 и L2 совпадают. Если B’2=0 и С’2≠0, то система несовместна и, следовательно прямые параллельны и не имеют общей точки. Если же B’2≠0, то система линейных уравнений имеет единственное решение. Из второго уравнения находим y: y=С’2/B’2 и подставляя полученное значение в первое уравнение находим x: x=(−С1B1y)/A1. Получили точку пересечения прямых L1 и L2: M(x, y).

Подробнее о решении систем линейных уравнений посмотрите на странице метод Гаусса онлайн.

2. Точка пересечения прямых, заданных в каноническом виде.

Пусть задана декартова прямоугольная система координат Oxy и пусть в этой системе координат заданы прямые L1 и L2:

(6)
(7)

где M1(x1, y1) и M2(x2, y2) − точки, лежащие на прямых L1 и L2, соответственно, а q1=<m1, p1> и q2=<m2, p2> − направляющие векторы прямых L1 и L2, соответственно.

Приведем уравнение L1 к общему виду. Сделаем перекрестное умножение в уравнении (6):

p1(xx1)=m1(yy1)

Откроем скобки и сделаем преобразования:

p1xm1yp1x1+m1y1=0
A1x+B1y+C1=0 (8)

Аналогичным методом получим общее уравнение прямой (7):

A2x+B2y+C2=0 (9)

Терерь можно найти точку пересечения прямых L1 и L2 методом, описанным в параграфе 1.

3. Точка пересечения прямых, заданных в параметрическом виде.

Пусть задана декартова прямоугольная система координат Oxy и пусть в этой системе координат заданы прямые L1 и L2 в параметрическом виде:

(10)
(11)

где M1(x1, y1) и M2(x2, y2) − точки, лежащие на прямых L1 и L2, соответственно, а q1=<m1, p1> и q2=<m2, p2> − направляющие векторы прямых L1 и L2, соответственно.

Приведем уравнение прямой L1 к каноническому виду. Для этого из уравнений (10) найдем параметр t:

(12)

Из уравнений (12) следует:

Аналогичным образом можно найти каноническое уравнение прямой L2:

Как найти точку пересечения прямых, заданных в каноническом виде описано выше.

4. Точка пересечения прямых, заданных в разных видах.

Пусть задана декартова прямоугольная система координат Oxy и пусть в этой системе координат заданы прямые L1 и L2:

L1: A1x+B1y+C1=0, (13)
(14)

где n=<A1, B1> нормальный вектор прямой L1, q=<m, p> − направляющий вектор прямой L2 .

Найдем точку пересечения прямых L1 и L2. Для этого подставим x=x2+mt, y=y2+pt в (13):

A1(x2+mt)+B1(y2+pt)+C1=0, (15)
A1x2+A1mt+B1y2+B1pt+C1=0,
(16)

Если числитель и знаменатель в (16) одновременно равны нулю, то любое значение t удовлетворяет уравнению (15), следовательно прямые L1 и L2 совпадают. Если знаменатель равен нулю а числитель отличен от нуля, то прямые L1 и L2 не пересекаются, т.е. они параллельны.

Пусть знаменатель не равен нулю. Подставляя полученное значение t в (14), получим координаты точки пересечения прямых L1 и L2.

5. Примеры нахождения точки пересечения прямых на плоскости.

Пример 1. Найти точку пересечения прямых L1 и L2:

L1: 2x+y+4=0, (17)
L2: x−3y+2=0. (18)

Для нахождения точки пересечения прямых L1 и L2 нужно решить систему линейных уравнений (17) и (18). Представим уравнения в матричном виде:

(19)

Решим систему линейных уравнений отностительно x, y. Для этого воспользуемся методом Гаусса. Получим:

Ответ. Точка пересечения прямых L1 и L2 имеет следующие координаты:

M (−2, 0).

Пример 2. Найти точку пересечения прямых L1 и L2:

L1: 2x+3y+4=0, (20)
(21)

Для нахождения точки пересечения прямых L1 и L2 нужно решить систему линейных уравнений (20) и (21). Представим уравнения в матричном виде:

(22)

Для решения (22) воспользуемся методом Гаусса. Получим:

где λ− произвольное действительное число.

Имеем больше одного решения. Это означает, что прямые L1 и L2 совпадают.

Ответ. Прямые L1 и L2 совпадают.

Пример 3. Найти точку пересечения прямых L1 и L2:

L1: −5x+y+9=0, (23)
L2: −10x+2y−3=0, (24)

Для нахождения точки пересечения прямых L1 и L2 нужно решить систему линейных уравнений (23) и (24). Представим уравнения в матричном виде:

(25)

Применив метод Гаусса получим, что система (25) несовместна. Следовательно эти прямые не пересекаются, т.е. они параллельны.

Ответ. Прямые L1 и L2 не имеют общую точку, т.е. они параллельны.

Пример 4. Найти точку пересечения прямых L1 и L2:

(26)
L2: x+2y−9=0, (27)

Приведем, сначала, уравнение прямой (26) к общему виду:

2(x−3)=y+5
2xy−11=0 (28)

Для нахождения точки пересечения прямых L1 и L2 нужно решить систему линейных уравнений (28) и (27). Представим уравнения в матричном виде:

(29)

Решим систему линейных уравнений отностительно x, y:

Ответ. Точка пересечения прямых L1 и L2 имеет следующие координаты:

Урок 32. Пересекаются ли два отрезка?

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

Здравствуйте, дорогой читатель. Напишем еще три новые функции.

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

Функция RealLess() будет использоваться для реализации операции сравнения «

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: