Найти точку пересечения прямых. Геометрические алгоритмы. Как вычислить точку пересечения двух прямых
В былые времена я увлекался компьютерной графикой, как 2х так и 3х мерной, в том числе математическими визуализациями. Что называется just for fun, будучи студентом, написал программу визуализирующую N-мерные фигуры, вращающиеся в любых измерениях, хотя практически меня хватило только на определение точек для 4-D гиперкуба. Но это только присказка. Любовь к геометрии осталась у меня с тех пор и по сей день, и я до сих пор люблю решать интересные задачи интересными способами.Одна из таких задач попалась мне в 2010 году. Сама задача достаточно тривиальна: необходимо найти, пересекаются ли два 2-D отрезка, и если пересекаются - найти точку их пересечения. Более интересно решение, которое, я считаю, получилось достаточно элегантным, и которое я хочу предложить на суд читателя. На оригинальность алгоритма не претендую (хотя и хотелось бы), но в сети подобных решений я найти не смог.
Задача
Даны два отрезка, каждый из которых задан двумя точками: (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
1 template
Если две прямые не параллельны, то они неукоснительно пересекутся в одной точке. Обнаружить координаты точки пересечения 2-х прямых дозволено как графическим, так и арифметическим методом, в зависимости от того, какие данные предоставляет задача.
Вам понадобится
- – две прямые на чертеже;
- – уравнения 2-х прямых.
Инструкция
1. Если прямые теснее начерчены на графике, обнаружьте решение графическим методом. Для этого продолжите обе либо одну из прямых так, дабы они пересеклись. После этого подметьте точку пересечения и опустите из нее перпендикуляр на ось абсцисс (как водится, ох).
2. При помощи шкалы делений, подмеченных на оси, обнаружьте значение х для этой точки. Если она находится на позитивном направлении оси (справа от нулевой отметки), то ее значение будет правильным, в отвратном случае – негативным.
3. Верно также обнаружьте ординату точки пересечения. Если проекция точки расположена выше нулевой отметки – она правильная, если ниже – негативная. Запишите координаты точки в виде (х, у) – это и есть решение задачи.
4. Если прямые заданы в виде формул у=kх+b, вы можете также решить задачу графическим методом: начертите прямые на координатной сетке и обнаружьте решение описанным выше методом.
5. Испробуйте обнаружить решение задачи, применяя данные формулы. Для этого составьте из этих уравнений систему и решите ее. Если уравнения даны в виде у=kх+b, примитивно приравняйте обе части с х и обнаружьте х. После этого подставьте значение х в одно из уравнений и обнаружьте у.
6. Дозволено обнаружить решение методом Крамера. В таком случае приведите уравнения к виду А1х+В1у+С1=0 и А2х+В2у+С2=0. Согласно формуле Крамера х=-(С1В2-С2В1)/(А1В2-А2В1), а у=-(А1C2-А2С1)/(А1В2-А2В1). Обратите внимание, если знаменатель равен нулю, то прямые параллельны либо совпадают и, соответственно, не пересекаются.
7. Если вам даны прямые в пространстве в каноническом виде, перед тем, как начать поиск решения, проверьте, не параллельны ли прямые. Для этого оцените показатели перед t, если они пропорциональны, скажем, x=-1+3t, y=7+2t, z=2+t и x=-1+6t, y=-1+4t, z=-5+2t, то прямые параллельны. Помимо того, прямые могут скрещиваться, в этом случае система не будет иметь решения.
8. Если вы узнали, что прямые пересекаются, обнаружьте точку их пересечения. Вначале приравняйте переменные из различных прямых, условно заменив t на u для первой прямой и на v для 2-й прямой. Скажем, если вам даны прямые x=t-1, y=2t+1, z=t+2 и x=t+1, y=t+1, z=2t+8 вы получите выражения типа u-1=v+1, 2u+1=v+1, u+2=2v+8.
9. Выразите из одного уравнения u, подставьте в другое и обнаружьте v (в данной задаче u=-2,v=-4). Сейчас, дабы обнаружить точку пересечения, подставьте полученные значения взамен t (без разницы, в первое либо второе уравнение) и получите координаты точки x=-3, y=-3, z=0.
Для рассмотрения 2-х пересекающихся прямых довольно рассмотрения их в плоскости, так как две пересекающиеся прямые лежат в одной плоскости. Зная уравнения этих прямых , дозволено обнаружить координату их точки пересечения .
Вам понадобится
- уравнения прямых
Инструкция
1. В декартовых координатах всеобщее уравнение прямой выглидит так: Ax+By+C = 0. Пускай две прямые пересекаются. Уравнение первой прямой имеет вид Ax+By+C = 0, 2-й прямой – Dx+Ey+F = 0. Все показатели (A, B, C, D, E, F) обязаны быть заданы.Дабы обнаружить точку пересечения этих прямых надобно решить систему этих 2-х линейных уравнений.
2. Для решения первое уравнение комфортно умножить на E, а второе – на B. В итоге уравнения будут иметь вид: AEx+BEy+CE = 0, DBx+EBy+FB = 0. Позже вычитания второго уравнения из первого, получится: (AE-DB)x = FB-CE. Отсель, x = (FB-CE)/(AE-DB).По аналогии первое уравнение начальной системы дозволено умножить на D, второе – на A, после этого вновь из первого вычесть второго. В итоге, y = (CD-FA)/(AE-DB).Полученные значения x и y и будут координатами точки пересечения прямых .
3. Уравнения прямых также могут записываться через угловой показатель k, равный тангенсу угла наклона прямой. В этом случае уравнение прямой имеет вид y = kx+b. Пускай сейчас уравнение первой прямой – y = k1*x+b1, а 2-й прямой – y = k2*x+b2.
4. Если приравнять правые части этих 2-х уравнений, то получится: k1*x+b1 = k2*x+b2. Отсель легко получить, что x = (b1-b2)/(k2-k1). Позже подстановки этого значения x в всякое из уравнений, получится: y = (k2*b1-k1*b2)/(k2-k1). Значения x и y будут задавать координаты точки пересечения прямых .В случае, если две прямые параллельны либо сопадают, то они не имеют всеобщих точек либо имеют безмерно много всеобщих точек соответственно. В этих случаях k1 = k2, знаменатели для координат точек пересечения будут обращаться в нуль, следственно, система не будет иметь классического решения.Система может иметь только одно классическое решение, что безусловно, потому что две несовпадающие и не параллельные друг другу прямые могут иметь только одну точку пересечения .
Видео по теме
Пусть даны две прямые и требуется найти их точку пересечения. Так как эта точка принадлежит каждой из двух данных прямых, то ее координаты должны удовлетворять как уравнению первой прямой, так и уравнению второй прямой.
Таким образом, для того чтобы найти координаты точки пересечения двух прямых, следует решить систему уравнений
Пример 1. Найти точку пересечения прямых и
Решение. Координаты искомой точки пересечения мы найдем, решив систему уравнений
Точка пересечения М имеет координаты
Покажем, как построить прямую по ее уравнению. Для построения прямой достаточно знать две ее точки. Чтобы построить каждую из этих точек, мы задаемся произвольным значением одной из ее координат, а затем из уравнения находим соответствующее значение другой координаты.
Если в общем уравнении прямой оба коэффициента при текущих координатах не равны нулю , то для построения этой прямой лучше всего находить точки ее пересечения с осями координат.
Пример 2. Построить прямую .
Решение. Находим точку пересечения данной прямой с осью абсцисс. Для этого решаем совместно их уравнения:
и получаем . Таким образом, найдена точка М (3; 0) пересечения данной прямой с осью абсцисс (рис. 40).
Решая затем совместно уравнение данной прямой и уравнение оси ординат
мы находим точку пересечения прямой с осью ординат. Наконец, строим прямую по ее двум точкам М и
Урок из серии «Геометрические алгоритмы»
Здравствуйте, дорогой читатель!
Продолжим знакомиться с геометрическими алгоритмами. На прошлом уроке мы нашли уравнение прямой линии по координатам двух точек. У нас получилось уравнение вида:
Сегодня мы напишем функцию, которая по уравнениям двух прямых линий будет находить координаты их точки пересечения (если такая имеется). Для проверки равенства вещественных чисел, будем использовать специальную функцию RealEq().
Точки на плоскости описываются парой вещественных чисел. При использовании вещественного типа операции сравнения лучше оформить специальными функциями.
Причина известна: на типе Real в системе программирования Паскаль нет отношения порядка, поэтому записи вида a = b, где a и b вещественные числа, лучше не использовать.
Сегодня мы введем в употребление функцию RealEq() для реализации операции “=” (строго равно) :
Function RealEq(Const a, b:Real):Boolean; {строго равно} begin RealEq:=Abs(a-b)<=_Eps End; {RealEq}
Задача. Заданы уравнения двух прямых: и . Найти точку их пересечения.
Решение. Очевидное решение состоит в том, чтобы решить систему уравнений прямых: 
Давайте перепишем эту системе несколько иначе:
(1)
 |
Введем обозначения: , 
, 
. Здесь D – определитель системы, а - определители, получающиеся в результате замены столбца коэффициентов при соответствующем неизвестном столбцом свободных членов. Если , то система (1) является определенной, то есть имеет единственное решение. Это решение можно найти по следующим формулам: , , которые называются формулами Крамера
. Напомню, как вычисляется определитель второго порядка. В определителе различают две диагонали: главную и побочную. Главная диагональ состоит из элементов, взятых по направлению от верхнего левого угла определителя в нижний правый угол. Побочная диагональ – из правого верхнего в нижний левый. Определитель второго порядка равен произведению элементов главной диагонали минус произведение элементов побочной диагонали.
В программном коде для проверки проверка равенства используется функция RealEq(). Вычисления над вещественными числами производятся с точностью до _Eps=1e-7.
Program geom2; Const _Eps: Real=1e-7;{точность вычислений} var a1,b1,c1,a2,b2,c2,x,y,d,dx,dy:Real; Function RealEq(Const a, b:Real):Boolean; {строго равно} begin RealEq:=Abs(a-b)<=_Eps End; {RealEq} Function LineToPoint(a1,b1,c1,a2,b2,c2: real; var x,y:real):Boolean; {Определение координат точки пересечения двух линий. Значение функции равно true, если точка пересечения есть, и false, если прямые параллельны. } var d:real; begin d:=a1*b2-b1*a2; if Not(RealEq(d,0)) then begin LineToPoint:=True; dx:=-c1*b2+b1*c2; dy:=-a1*c2+c1*a2; x:=dx/d; y:=dy/d; end else LineToPoint:=False End;{LineToPoint} begin {main} writeln("Введите коэффициенты уравнений: a1,b1,c1,a2,b2,c2 "); readln(a1,b1,c1,a2,b2,c2); if LineToPoint(a1,b1,c1,a2,b2,c2,x,y) then writeln(x:5:1,y:5:1) else writeln("Прямые параллельны."); end.
Мы составили программу, с помощью которой можно, зная уравнения линий, найти координаты их точки пересечения.
