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

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

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

Содержание скрыть

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

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

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

Практика 2

Исходники

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

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

$\displaystyle y = K x + B$

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

$\displaystyle A x + B y + C = 0$

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

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

$\displaystyle \begin{cases} A_{1} \times x + B_{1} \times y + C_{1} = 0\\ A_{2} \times x + B_{2} \times y + C_{2} = 0 \end{cases}$

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

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

$\displaystyle \frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$

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

$\displaystyle x(y_2-y_1) + y(x_1-x_2)-x_1 y_2+y_1 x_2 = 0$

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

$\displaystyle A = y_2-y_1\\ B = x_1-x_2\\ C = y_1 x_2-x_1 y_2\\$

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

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

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

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

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

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

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

$\displaystyle \begin{cases} A_{1} \times x + B_{1} \times y = -C_{1}\\ A_{2} \times x + B_{2} \times y = -C_{2} \end{cases}$

Определители будут такими:

$\displaystyle \Delta_{ab} = \begin{vmatrix} A_1 & B_1 \\ A_2 & B_2 \end{vmatrix} = A_1 B_2-B_1 A_2$

$\displaystyle \Delta_x = \begin{vmatrix} -C_1 & B_1 \\ -C_2 & B_2 \end{vmatrix} = -(C_1 B_2-B_1 C_2)$

$\displaystyle \Delta_y = \begin{vmatrix} A_1 & -C_1 \\ A_2 & -C_2 \end{vmatrix} = -(A_1 C_2-C_1 A_2)$

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

$\displaystyle x = \frac{\Delta_x}{\Delta_{ab}} = \frac{-(C_1 B_2-B_1 C_2)}{ A_1 B_2-B_1 A_2}\\$

$\displaystyle y = \frac{\Delta_y}{\Delta_{ab}} = \frac{-(A_1 C_2-C_1 A_2)}{ A_1 B_2-B_1 A_2}\\$

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

Практика 1

//*******************************************************
//  Нахождение точки пересечения прямых (p1,p2) и (p3,p4)
//  Результат - факт пересечения
//*******************************************************
function CrossLines(const p1,p2,p3,p4: TxPoint;
  var res: TxPoint): Boolean;
const
  Prec = 0.0001;
var
  a1, a2: Extended;
  b1, b2: Extended;
  c1, c2: Extended;
  v: Extended;
begin
  a1 := p2.y - p1.y;
  a2 := p4.y - p3.y;

  b1 := p1.x - p2.x;
  b2 := p3.x - p4.x;

  v := a1*b2 - a2*b1;
  Result := (abs(v) > Prec);

  if Result then
  begin
    c1 := p2.x*p1.y - p1.x*p2.y;
    c2 := p4.x*p3.y - p3.x*p4.y;

    res.X := -(c1*b2 - c2*b1)/v;
    res.Y := -(a1*c2 - a2*c1)/v;
  end;
end;

//*******************************************************

// Нахождение точки пересечения прямых (p1,p2) и (p3,p4)

// Результат - факт пересечения

//*******************************************************

function CrossLines(const p1,p2,p3,p4: TxPoint;

var res: TxPoint): Boolean;

const

Prec = 0.0001;

var

a1, a2: Extended;

b1, b2: Extended;

c1, c2: Extended;

v: Extended;

begin

a1 := p2.y - p1.y;

a2 := p4.y - p3.y;

b1 := p1.x - p2.x;

b2 := p3.x - p4.x;

v := a1*b2 - a2*b1;

Result := (abs(v) > Prec);

if Result then

begin

c1 := p2.x*p1.y - p1.x*p2.y;

c2 := p4.x*p3.y - p3.x*p4.y;

res.X := -(c1*b2 - c2*b1)/v;

res.Y := -(a1*c2 - a2*c1)/v;

end;

Пересечение прямых, построенных по двум точкам. Точка пересечения принадлежеит обоим отрезкам. — Рис.1. Пересечение прямых

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

Прямые параллельны: ∆_ab = 0
- (A₁B₂ – B₁A₂ = 0);
Прямые совпадают: ∆_ab = ∆_X = ∆_Y = 0
- (A₁B₂ – B₁A₂ = 0) И (A₁C₂ — A₂C₁ = 0) И (C₁B₂ -B₁C₂ = 0);
Прямые перпендикулярны:
- (A₁ A₂ + B₁ B₂ = 0).

Рис.2. Пересечение перпендикулярных прямых

Рис.3. Параллельные прямые не пересекаются

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

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

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

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

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

//*****************************************************
//  Проверка факта нахождения точки res между 
//  концами отрезка (p1,p2).
//  Решение с помощью условных операторов и
//  коэффициентов A=(y2-y1) B=(x1-x2).
//  Выступают в качестве параметров, чтобы не тратить
//  время на их подсчет, т.к. в вызывающей стороне
//  они уже посчитаны
//*****************************************************
function CheckCrossPoint(const p1, p2, res: TxPoint;
  const A,B: Extended): Boolean;
begin
  Result :=
    (((B<0) and (p1.X < res.X) and (p2.X > res.X)) or
     ((B>0) and (p1.X > res.X) and (p2.X < res.X)) or
     ((A<0) and (p1.y > res.Y) and (p2.Y < res.Y)) or
     ((A>0) and (p1.y < res.Y) and (p2.Y > res.Y)));
end;

//*****************************************************
//  Проверить факт нахождения точки res между 
//  концами отрезка (p1,p2)
//  Арифметическое решение без коэффициентов
//*****************************************************
function CheckCrossPoint(const p1, p2, res: TxPoint): Boolean;
begin
  Result :=
    (abs(p2.x-p1.x)>= abs(p2.x-res.x) + abs(p1.x-res.x)) and
    (abs(p2.y-p1.y)>= abs(p2.y-res.y) + abs(p1.y-res.y));
end;

//*****************************************************

// Проверка факта нахождения точки res между

// концами отрезка (p1,p2).

// Решение с помощью условных операторов и

// коэффициентов A=(y2-y1) B=(x1-x2).

// Выступают в качестве параметров, чтобы не тратить

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

// они уже посчитаны

//*****************************************************

function CheckCrossPoint(const p1, p2, res: TxPoint;

const A,B: Extended): Boolean;

begin

Result :=

(((B<0) and (p1.X < res.X) and (p2.X > res.X)) or

((B>0) and (p1.X > res.X) and (p2.X < res.X)) or

((A<0) and (p1.y > res.Y) and (p2.Y < res.Y)) or

((A>0) and (p1.y < res.Y) and (p2.Y > res.Y)));

end;

//*****************************************************

// Проверить факт нахождения точки res между

// концами отрезка (p1,p2)

// Арифметическое решение без коэффициентов

//*****************************************************

function CheckCrossPoint(const p1, p2, res: TxPoint): Boolean;

begin

Result :=

(abs(p2.x-p1.x)>= abs(p2.x-res.x) + abs(p1.x-res.x)) and

(abs(p2.y-p1.y)>= abs(p2.y-res.y) + abs(p1.y-res.y));

end;

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

Задача нахождения принадлежности точки P(x,y) отрезку, заданного двумя точками с координатами P1(x1, y1) и P2(x2, y2) подробно рассмотрена в отдельной статье.

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

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

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

Вектор из точки p1 в точку p2 с указанием расстояний по Y и X — Рис.4. Вектор V(p₁,p₂)

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

α = arctan (A₁ / B₁)

Где расстояния:

A₁ = (y₁ — y₂)

B₁ = (x₂ — x₁)

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

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

Пересекающиеся векторы — Рис.5. Пересекающиеся вектор V(p₁,p₂) и вектор M(p₃,p₄)

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

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

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

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

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

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

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

//**********************************************************
// Посчитать угол пересечения векторов по коэфф-ам А и B
//**********************************************************
function CalcCrossAngle(const a1,b1: Extended;
  const a2,b2: Extended): Extended;
var
  c1, c2: Extended;
begin
  c1 := ArcTan2(a1,b1);
  c2 := ArcTan2(a2,b2);

  Result := c2-c1;

  if Result < -pi then
    Result := 2*pi + Result;

  if Result > pi then
    Result := Result - 2*pi;
end;

//**********************************************************

// Посчитать угол пересечения векторов по коэфф-ам А и B

//**********************************************************

function CalcCrossAngle(const a1,b1: Extended;

const a2,b2: Extended): Extended;

var

c1, c2: Extended;

begin

c1 := ArcTan2(a1,b1);

c2 := ArcTan2(a2,b2);

Result := c2-c1;

if Result < -pi then

Result := 2*pi + Result;

if Result > pi then

Result := Result - 2*pi;

end;

Тут ситуация с вертикальной прямой, т.е. когда теоретически происходит деление на ноль, явно не обрабатывается. Она корректно обрабатывается функцией ArcTan2, которая вернет в этом случае и знак, и 90 градусов.

Пересечение перпендикулярных векторов с верным подсчетом особого "вертикального" случая. — Рис.7. Пересечение перпендикулярных векторов

Практика 2

В дополнение к функции нахождения точки пересечения, напишем «продвинутую» функцию, которая находит эту точку, определяет нахождение на каждом из отрезков, и определяет угол между направляющими векторами. Или же определяет, что прямые параллельны/совпадают.

//**********************************************************
//  Тип пересечения прямых (p1,p2) и (p3,p4)
//**********************************************************
type
  TxCrossLineResult = (
    xclrEqual    = -32// эквивалентны
   ,xclrParallel = -16// параллельны
   ,xclrOk       = 0  // как минимум пересечение есть
   ,xclrFirst    = 1  // попадает в первый отрезок
   ,xclrSecond   = 2  // попадает во второй отрезок
   ,xclrBoth     = 3  // попадает в оба
   ,xclrPerpend  = 4  // перпендикулярны
   // можно найти по маске через AND, но для полноты картины
   ,xclrFirstP   = 5  // перпендикулярны и попадает в первый
   ,xclrSecondP  = 6  // перпендикулярны и попадает в второй
   ,xclrBothP    = 7  // перпендикулярны и попадает в оба
   );

//**********************************************************
//  Нахождение точки пересечения прямых (p1,p2) и (p3,p4)
//  Определяет параллельность, совпадение,
//  перпендикулярность, пересечение.
//  Определяет, каким отрезкам принадлежит.
//  Находит угол(рад.) от (p1,p2) к (p3,p4):
//    отрицательное значение - против часовой
//    положительное - по часовой
//**********************************************************
function CrossLines(const p1,p2,p3,p4: TxPoint;
  var res: TxPoint; var Angle: Extended): TxCrossLineResult;
const
  Prec = 0.0001;
var
  a1, a2: Extended;
  b1, b2: Extended;
  c1, c2: Extended;
  v: Extended;
begin
  Angle := 0;

  a1 := p2.y - p1.y;
  a2 := p4.y - p3.y;

  b1 := p1.x - p2.x;
  b2 := p3.x - p4.x;

  c1 := p2.x*p1.y - p1.x*p2.y;
  c2 := p4.x*p3.y - p3.x*p4.y;

  v := a1*b2 - a2*b1;

  if abs(v) > Prec then
  begin
    Result := xclrOk;

    res.X := -(c1*b2 - c2*b1)/v;
    res.Y := -(a1*c2 - a2*c1)/v;

    if CheckCrossPoint(p1,p2,res) then
      Result := TxCrossLineResult(Integer(Result) +
        Integer(xclrFirst));

    if CheckCrossPoint(p3,p4,res) then
      Result := TxCrossLineResult(Integer(Result) +
        Integer(xclrSecond));

    if (abs(a1*a2 + b1*b2) < Prec) then
      Result := TxCrossLineResult(Integer(Result) +
        Integer(xclrPerpend));

    Angle := CalcCrossAngle(a1,b1,a2,b2);
  end else
  begin
    Result := xclrParallel;
    if ((abs(c1*b2 - c2*b1) < Prec) and 
       (abs(a1*c2 - a2*c1) < Prec))
    then
      Result := xclrEqual;
  end;
end;

//**********************************************************

// Тип пересечения прямых (p1,p2) и (p3,p4)

//**********************************************************

type

TxCrossLineResult = (

xclrEqual = -32// эквивалентны

,xclrParallel = -16// параллельны

,xclrOk = 0 // как минимум пересечение есть

,xclrFirst = 1 // попадает в первый отрезок

,xclrSecond = 2 // попадает во второй отрезок

,xclrBoth = 3 // попадает в оба

,xclrPerpend = 4 // перпендикулярны

// можно найти по маске через AND, но для полноты картины

,xclrFirstP = 5 // перпендикулярны и попадает в первый

,xclrSecondP = 6 // перпендикулярны и попадает в второй

,xclrBothP = 7 // перпендикулярны и попадает в оба

);

//**********************************************************

// Нахождение точки пересечения прямых (p1,p2) и (p3,p4)

// Определяет параллельность, совпадение,

// перпендикулярность, пересечение.

// Определяет, каким отрезкам принадлежит.

// Находит угол(рад.) от (p1,p2) к (p3,p4):

// отрицательное значение - против часовой

// положительное - по часовой

//**********************************************************

function CrossLines(const p1,p2,p3,p4: TxPoint;

var res: TxPoint; var Angle: Extended): TxCrossLineResult;

const

Prec = 0.0001;

var

a1, a2: Extended;

b1, b2: Extended;

c1, c2: Extended;

v: Extended;

begin

Angle := 0;

a1 := p2.y - p1.y;

a2 := p4.y - p3.y;

b1 := p1.x - p2.x;

b2 := p3.x - p4.x;

c1 := p2.x*p1.y - p1.x*p2.y;

c2 := p4.x*p3.y - p3.x*p4.y;

v := a1*b2 - a2*b1;

if abs(v) > Prec then

begin

Result := xclrOk;

res.X := -(c1*b2 - c2*b1)/v;

res.Y := -(a1*c2 - a2*c1)/v;

if CheckCrossPoint(p1,p2,res) then

Result := TxCrossLineResult(Integer(Result) +

Integer(xclrFirst));

if CheckCrossPoint(p3,p4,res) then

Result := TxCrossLineResult(Integer(Result) +

Integer(xclrSecond));

if (abs(a1*a2 + b1*b2) < Prec) then

Result := TxCrossLineResult(Integer(Result) +

Integer(xclrPerpend));

Angle := CalcCrossAngle(a1,b1,a2,b2);

end else

begin

Result := xclrParallel;

if ((abs(c1*b2 - c2*b1) < Prec) and

(abs(a1*c2 - a2*c1) < Prec))

then

Result := xclrEqual;

end;

Исходники

Небольшие комментарии по интерфейсу.

Скачать (219 Кб): Исходники (Delphi XE 7-10)

Скачать (1.14 Мб): Исполняемый файл

При запуске генерируется случайным образом 4 точки, по две на прямую. Точки и отрезки можно перетаскивать мышкой. Также, слева присутствует панель, на которой можно ввести координаты точек или коэффициенты уравнения прямой. При нажатии «Enter» или когда элемент ввода теряет фокус, происходит перерасчет и перерисовка.

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

Если точка пересечений попадает в какой-либо из отрезков, соответствующий заголовок линии отрезка станет жирным. На рисунке это зеленая линия 2.

По умолчанию, рабочее поле системы координат имеет размерность [-10..10], которую можно изменить ползунком в нижнем правом углу.

5 17 голоса

Рейтинг статьи

2 комментариев

Старые

Новые Популярные

Межтекстовые Отзывы

Посмотреть все комментарии

pavlen

1 год назад

Отличная статья.
А если у меня прямые заданы, с помощью координаты и угла.
То мне по идее надо найти ещё одну точку на этой прямой и уже по ним получить A, B, C параметры?
Или есть более простые способы?

Ответить

Roman

Автор

Ответить на pavlen

1 год назад

Спасибо!
Могу предположить следующее:
Уравнение для прямой, проходящей через точку(X0,Y0) под углом A:
tgA — тангенс A
Y = tgA * (X-X0) + Y0
Y = tgA*X — tgA*X0 + Y0
tgA — это k
Y = kX + (Y0 — kX0)
b = Y0 — kX0
Получаем вполне себе привычное уравнение:
Y = kX + b
Таким образом, у нас есть уравнения для обеих прямых.
Далее идём сюда и пробуем.
Расскажите потом о результатах )))

Ответить