Нахождение точки пересечения двух линий по углам и двум известным точкам (биангуляция). Как вычислить точку пересечения двух прямых
Одна из таких задач попалась мне в 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
Комментариев 11
Задача
Найти точку пересечения двух прямых отложенных от двух точек с известными координатами и азимутов от этих точек.
Применение
Для изучения поведения животных часто используют радиотелеметрический метод: исследуемый объект помечается радиопередатчиком, который испускает радиосигнал определенной частоты и далее исследователь при помощи приемника и принимающей антенны следит за перемещениями этого объекта. Одним из возможных способов определения точного местоположения объекта является метод биангуляции. Для этого исследователю требуется взять 2 азимута на исследуемый объект с точек с известными координатами. Местоположение объекта будет соответствовать точке пересечения этих двух азимутов. Координаты точек, с которых засекаются азимуты можно снять с помощью спутникового навигатора (GPS), либо азимуты снимаются с реперных точек, координаты которых известны заранее. Азимут в этом случае – направление на источник наиболее сильного сигнала, исходящего от меченного передатчиком объекта, измеряемое обычно в градусах.
Перед расчетами необходимо точки полученные с помощью GPS перевести в спроецированную систему координат, например соответствующую зону UTM, это можно сделать с помощью DNRGarmin .
Для того чтобы рассчитанное местоположение исследуемого объекта наиболее точно соответствовало реальному положению нужно учитывать следующее:
1) необходимо стараться дождаться момента, чтобы ошибка определения координат в навигаторе была как можно меньше.
2) чтобы угол между азимутами стремился к 90 градусам (по крайней мере, был больше 30 и меньше 150 градусов).
Расстояние, с которого следует снимать азимут, зависит от дальности действия передатчика, при этом применяется эмпирическое правило, что погрешность в определении азимута увеличивается на 1 метр с удалением от исследуемого объекта на каждые 10 м. Т.о. при снятии азимута с расстоянием до объекта 100 м погрешность составит 10 м. Однако, это правило применимо на ровной открытой местности. Следует учитывать, что неровности рельефа и древесно-кустарниковая растительность экранируют и отражают сигнал. Следует избегать нахождения в непосредственной близости от исследуемого объекта, т.к. во-первых, слишком сильный сигнал затруднит определение точного азимута, а, во-вторых, в некоторых случаях будет невозможно рассчитать точку пересечения из-за того, что второй азимут будет проходить за точкой снятия первого азимута. Временной интервал между снятием пары азимутов должен быть минимизирован, но, конечно, зависит от подвижности исследуемого животного.
Решение
Задача решается с помощью простейшей геометрии и решения
системы уравнений.
Для начала из точки и азимута получаем уравнение прямой, для этого:
Из уравнения общего вида:
ax + by + c = 0
при условии, что b<>0 получаем
y = kx + d , где k=-(a/b) , d=-(c/b)
таким образом, получаем
k=tan(a)
d=y-tan(a)*x
b=1
k1x + d1 = y
k2x + d2 = y
Получаем координаты X и Y общей точки двух прямых (точки пересечения).
В уравнении необходимо предусмотреть два особых случая, когда прямые параллельны (k1=k2).
Так как мы имеем дело не с векторами и не с лучами, то есть у линий нет начала и конца, то так же необходимо предусмотреть случай пересечения прямых вне области интереса, т.н. ложное пересечение. Решение этой задачи достигается измерением азимута из ложной точки a3 на точку 2, если азимут a3 = a2, то пересечение ложное, обратный азимут от полученной точки обратно на исходные 2 не должен быть равен одному из исходных азимутов.
Необходимая процедура на языке Avenue выглядит так:
a1rad = (90-a1)*pi/180a2rad = (90-a2)*pi/180 "в случае если линия параллельна оси абсцисс
if ((a1 = 0) or (a1 = 180)) then
l1a = 1
l1b = 0
l1c = x1
else
l1a = -(a1rad.tan)
l1b = 1
l1c = y1 - (a1rad.tan*x1)
end
if ((a2 = 0) or (a2 = 180)) then
l2a = 1
l2b = 0
l2c = x2
else
l2a = -(a2rad.tan)
l2b = 1
l2c = y2 - (a2rad.tan*x2)
end
D1 = l1a*l2b
D2 = l2a*l1b
D3 = D1 - D2
"Если линии параллельны, в поле результата записываются несуществующие значения
if (D3 = 0) then
resX = 9999
resY = 9999
else resX = ((l1c*l2b) - (l2c*l1b))/D3
resY = ((l1a*l2c) - (l2a*l1c))/D3 end
Урок из серии «Геометрические алгоритмы»
Здравствуйте, дорогой читатель!
Продолжим знакомиться с геометрическими алгоритмами. На прошлом уроке мы нашли уравнение прямой линии по координатам двух точек. У нас получилось уравнение вида:
Сегодня мы напишем функцию, которая по уравнениям двух прямых линий будет находить координаты их точки пересечения (если такая имеется). Для проверки равенства вещественных чисел, будем использовать специальную функцию 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.
Мы составили программу, с помощью которой можно, зная уравнения линий, найти координаты их точки пересечения.
В двумерном пространстве две прямые пересекаются только в одной точке, задаваемой координатами (х,y). Так как обе прямые проходят через точку их пересечения, то координаты (х,y) должны удовлетворять обоим уравнениям, которые описывают эти прямые. Воспользовавшись некоторыми дополнительными навыками вы сможете находить точки пересечения парабол и других квадратичных кривых.
Шаги
Точка пересечения двух прямых
- Если уравнения прямых вам не даны, на основе известной вам информации.
- Пример . Даны прямые, описываемые уравнениями и y − 12 = − 2 x {\displaystyle y-12=-2x} . Чтобы во втором уравнении обособить «у», прибавьте к обеим сторонам уравнения число 12:
-
Вы ищете точку пересечения обеих прямых, то есть точку, координаты (х,у) которой удовлетворяют обоим уравнениям. Так как на левой стороне каждого уравнения находится переменная «у», то выражения, расположенные с правой стороны каждого уравнения, можно приравнять. Запишите новое уравнение.
- Пример . Так как y = x + 3 {\displaystyle y=x+3} и y = 12 − 2 x {\displaystyle y=12-2x} , то можно записать такое равенство: .
-
Найдите значение переменной «х». Новое уравнение содержит только одну переменную «х». Для нахождения «х» обособьте эту переменную на левой стороне уравнения, выполнив соответствующие математические операции на обеих сторонах уравнения. Вы должны получить уравнение вида х = __ (если вы не можете это сделать, этого раздела).
- Пример . x + 3 = 12 − 2 x {\displaystyle x+3=12-2x}
- Прибавьте 2 x {\displaystyle 2x} к каждой стороне уравнения:
- 3 x + 3 = 12 {\displaystyle 3x+3=12}
- Вычтите 3 из каждой стороны уравнения:
- 3 x = 9 {\displaystyle 3x=9}
- Разделите каждую сторону уравнения на 3:
- x = 3 {\displaystyle x=3} .
-
Используйте найденное значение переменной «х» для вычисления значения переменной «у». Для этого подставьте найденное значение «х» в уравнение (любое) прямой.
- Пример . x = 3 {\displaystyle x=3} и y = x + 3 {\displaystyle y=x+3}
- y = 3 + 3 {\displaystyle y=3+3}
- y = 6 {\displaystyle y=6}
-
Проверьте ответ. Для этого подставьте значение «х» в другое уравнение прямой и найдите значение «у». Если вы получите разные значение «у», проверьте правильность ваших вычислений.
- Пример: x = 3 {\displaystyle x=3} и y = 12 − 2 x {\displaystyle y=12-2x}
- y = 12 − 2 (3) {\displaystyle y=12-2(3)}
- y = 12 − 6 {\displaystyle y=12-6}
- y = 6 {\displaystyle y=6}
- Вы получили такое же значение «у», поэтому в ваших вычислениях ошибок нет.
-
Запишите координаты (х,у). Вычислив значения «х» и «у», вы нашли координаты точки пересечения двух прямых. Запишите координаты точки пересечения в виде (х,у).
- Пример . x = 3 {\displaystyle x=3} и y = 6 {\displaystyle y=6}
- Таким образом, две прямые пересекаются в точке с координатами (3,6).
-
Вычисления в особых случаях. В некоторых случаях значение переменной «х» найти нельзя. Но это не значит, что вы допустили ошибку. Особый случай имеет место при выполнении одного из следующих условий:
- Если две прямые параллельны, они не пересекаются. При этом переменная «х» просто сократится, а ваше уравнение превратится в бессмысленное равенство (например, 0 = 1 {\displaystyle 0=1} ). В этом случае в ответе запишите, что прямые не пересекаются или решения нет.
- Если оба уравнения описывают одну прямую, то точек пересечения будет бесконечное множество. При этом переменная «х» просто сократится, а ваше уравнение превратится в строгое равенство (например, 3 = 3 {\displaystyle 3=3} ). В этом случае в ответе запишите, что две прямые совпадают.
Задачи с квадратичными функциями
-
Определение квадратичной функции. В квадратичной функции одна или несколько переменных имеют вторую степень (но не выше), например, x 2 {\displaystyle x^{2}} или y 2 {\displaystyle y^{2}} . Графиками квадратичных функций являются кривые, которые могут не пересекаться или пересекаться в одной или двух точках. В этом разделе мы расскажем вам, как найти точку или точки пересечения квадратичных кривых.
-
Перепишите каждое уравнение, обособив переменную «у» на левой стороне уравнения. Другие члены уравнения должны размещаться на правой стороне уравнения.
- Пример . Найдите точку (точки) пересечения графиков x 2 + 2 x − y = − 1 {\displaystyle x^{2}+2x-y=-1} и
- Обособьте переменную «у» на левой стороне уравнения:
- и y = x + 7 {\displaystyle y=x+7} .
- В этом примере вам дана одна квадратичная функция и одна линейная функция. Помните, что если вам даны две квадратичные функции, вычисления аналогичны шагам, изложенным далее.
-
Приравняйте выражения, расположенные с правой стороны каждого уравнения. Так как на левой стороне каждого уравнения находится переменная «у», то выражения, расположенные с правой стороны каждого уравнения, можно приравнять.
- Пример . y = x 2 + 2 x + 1 {\displaystyle y=x^{2}+2x+1} и y = x + 7 {\displaystyle y=x+7}
-
Перенесите все члены полученного уравнения на его левую сторону, а на правой стороне запишите 0. Для этого выполните базовые математические операции. Это позволит вам решить полученное уравнение.
- Пример . x 2 + 2 x + 1 = x + 7 {\displaystyle x^{2}+2x+1=x+7}
- Вычтите «x» из обеих сторон уравнения:
- x 2 + x + 1 = 7 {\displaystyle x^{2}+x+1=7}
- Вычтите 7 из обеих сторон уравнения:
-
Решите квадратное уравнение. Перенеся все члены уравнения на его левую сторону, вы получили квадратное уравнение. Его можно решить тремя способами: при помощи специальной формулы, и .
- Пример . x 2 + x − 6 = 0 {\displaystyle x^{2}+x-6=0}
- При разложении уравнения на множители вы получите два двучлена, при перемножении которых получается исходное уравнение. В нашем примере первый член x 2 {\displaystyle x^{2}} можно разложить на х*х. Сделайте следующую запись: (x)(x) = 0
- В нашем примере свободный член -6 можно разложить на следующие множители: − 6 ∗ 1 {\displaystyle -6*1} , − 3 ∗ 2 {\displaystyle -3*2} , − 2 ∗ 3 {\displaystyle -2*3} , − 1 ∗ 6 {\displaystyle -1*6} .
- В нашем примере второй член – это х (или 1x). Сложите каждую пару множителей свободного члена (в нашем примере -6), пока не получите 1. В нашем примере подходящей парой множителей свободного члена являются числа -2 и 3 ( − 2 ∗ 3 = − 6 {\displaystyle -2*3=-6} ), так как − 2 + 3 = 1 {\displaystyle -2+3=1} .
- Заполните пробелы найденной парой чисел: .
-
Не забудьте про вторую точку пересечения двух графиков. Если вы решаете задачу быстро и не очень внимательно, вы можете забыть про вторую точку пересечения. Вот как найти координаты «х» двух точек пересечения:
- Пример (разложение на множители) . Если в уравнении (x − 2) (x + 3) = 0 {\displaystyle (x-2)(x+3)=0} одно из выражений в скобках будет равно 0, то все уравнение будет равно 0. Поэтому можно записать так: x − 2 = 0 {\displaystyle x-2=0} → x = 2 {\displaystyle x=2} и x + 3 = 0 {\displaystyle x+3=0} → x = − 3 {\displaystyle x=-3} (то есть вы нашли два корня уравнения).
- Пример (использование формулы или дополнение до полного квадрата) . При использовании одного из этих методов в процессе решения появится квадратный корень. Например, уравнение из нашего примера примет вид x = (− 1 + 25) / 2 {\displaystyle x=(-1+{\sqrt {25}})/2} . Помните, что при извлечении квадратного корня вы получите два решения. В нашем случае: 25 = 5 ∗ 5 {\displaystyle {\sqrt {25}}=5*5} , и 25 = (− 5) ∗ (− 5) {\displaystyle {\sqrt {25}}=(-5)*(-5)} . Поэтому запишите два уравнения и найдите два значения «х».
-
Графики пересекаются в одной точке или вообще не пересекаются. Такие ситуации имеют место при соблюдении следующих условий:
- Если графики пересекаются в одной точке, то квадратное уравнение раскладывается на одинаковые множители, например, (х-1) (х-1) = 0, а в формуле появляется квадратный корень из 0 ( 0 {\displaystyle {\sqrt {0}}} ). В этом случае уравнение имеет только одно решение.
- Если графики вообще не пересекаются, то уравнение на множители не раскладывается, а в формуле появляется квадратный корень из отрицательного числа (например, − 2 {\displaystyle {\sqrt {-2}}} ). В этом случае в ответе напишите, что решения нет.
Запишите уравнение каждой прямой, обособив переменную «у» на левой стороне уравнения. Другие члены уравнения должны размещаться на правой стороне уравнения. Возможно, данное вам уравнение вместо «у» будет содержать переменную f(x) или g(x); в этом случае обособьте такую переменную. Для обособления переменной выполните соответствующие математические операции на обеих сторонах уравнения.