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

Изменено: . Разместил: FadeDemon | Меню
Количество просмотров8`385 / FD1035-6-0

Изобразим двумерную декартову систему координат. На ней изобразим 4 произвольные точки, и соединим их так, чтобы проведённые линии пересеклись в некоторой точке. Вопрос: каким образом мы можем найти координаты этой точки пересечения?


Безусловно, если вы хоть немного знакомы с высшей математикой, вас не затруднит дать уверенный ответ, заключающийся в том, что нам нужно просто решить систему двух линейных уравнений. Однако, предположим, что мы этого не знаем, и с высшей математикой не знакомы. Что тогда?


Недавно я оказался в подобной ситуации, и тем не менее, альтернативное решение было найдено. В этой статье я как раз и поведаю о нём. Итак, начнём.


\definecolor{gridgray}{rgb}{0.25,0.25,0.25} \definecolor{axisgray}{rgb}{0.45,0.45,0.45} \[ \begin{tikzpicture} \draw[color=gridgray,very thin] (0,0) grid [step=0.5cm] (4,4); \draw[-stealth,color=axisgray] (0,2) -- (4,2) node [above left=2pt] {$x$}; \draw[-stealth,color=axisgray] (2,0) -- (2,4) node [below right=2pt] {$y$}; \draw[-stealth] (1.5,1) coordinate (A) node [left=2pt] {$A$} -- (3,3) coordinate (B) node [right=2pt] {$B$}; \draw[-stealth] (0.5,3) coordinate (C) node [left=2pt] {$C$} -- (3.5,1.5) coordinate (D) node [below=2pt] {$D$}; \fill[white] (intersection of A--B and C--D) circle (1.5pt) node [above=4pt] {$X$}; \end{tikzpicture} \]
С чего всё началось

На рисунке выше, задача изображена наглядно. Даны векторы AB и CD, необходимо найти точку их пересечения X. Рассуждение начнем с того, как мы вообще можем выразить X? К примеру, представив её как векторную сумму точки A и вектора AB умноженного на некоторое число α, и по аналогии, сумму C и CD умноженного на β:


 \[ \overline X = \overline A + \overline {AB} \cdot \alpha = \overline C + \overline {CD} \cdot \beta \Rightarrow \left \lbrace \begin{aligned} & x_A + \alpha x_{AB} = x_C + \beta x_{CD} \\ & y_A + \alpha y_{AB} = y_C + \beta y_{CD} \\ \end{aligned} \right . \]
1. Шаг первый

Из векторного уравнения, сразу же, получаем два числовых уравнения. Далее, нам надо по идеи как-то найти α и β, чтобы с помощью них найти векторы AB и/или CD. Найти мы их пока не можем, зато можем выразить один через другой, причём двумя способами (для удобства, обозначим векторы AB и CD буквам a и b, векторы AX и CX буквами z и w, числа xA и yA символами x1 и y1, и наконец xC и yC символами x2 и y2):


 \[ \begin{align} & x_1 + \alpha x_a = x_2 + \beta x_b & y_1 + \alpha y_a = y_2 + \beta y_b \\ & \alpha x_a = x_2 + \beta x_b - x_1 & \alpha y_a = y_2 + \beta y_b - y_1 \\ & \alpha = {x_2 + \beta x_b - x_1 \over x_a} & \alpha = {y_2 + \beta y_b - y_1 \over y_a} \end{align} \]
2. Выражаем альфу

После того как мы выразили α двумя способами, совсем нетрудно догадаться, что мы этим самым получили очень интересное уравнение, из которого… Правильно! Можно выразить β, но уже без участия α:


 \[ \begin{align} & {x_2 + \beta x_b - x_1 \over x_a} = {y_2 + \beta y_b - y_1 \over y_a} \\ & {\beta x_b \over x_a} - {\beta y_b \over y_a} = {y_2 - y_1 \over y_a} - {x_2 - x_1 \over x_a} \\ & {\beta x_b y_a} - {\beta y_b x_a} = x_a({y_2- y_1}) - y_a({x_2 - x_1}) \\ & \beta = \frac{x_a({y_2- y_1}) - y_a({x_2 - x_1})}{x_b y_a - y_b x_a} \\ \end{align} \]
3. Выражаем бету

Отлично! Похоже, что с задачей мы справились. Все составляющие правой части уравнения известны, соответственно найти β труда нам уже не составит. А как только мы её найдём, тут же перейдём к уравнению (1), подставим туда найденную β, и мгновенно получим ответ.


Дальше нужно отметить, что точку пересечения мы получаем абсолютно всегда, когда векторы AB и CD не параллельны, даже тогда, когда они в общем-то не пересекаются, как например на рисунке ниже:


\definecolor{gridgray}{rgb}{0.25,0.25,0.25} \definecolor{axisgray}{rgb}{0.45,0.45,0.45} \[ \begin{tikzpicture} \draw[color=gridgray,very thin] (0,0) grid [step=0.5cm] (4,4); \draw[-stealth,color=axisgray] (0,2) -- (4,2) node [above left=2pt] {$x$}; \draw[-stealth,color=axisgray] (2,0) -- (2,4) node [below right=2pt] {$y$}; \draw[-stealth] (1.5,1) coordinate (A) node [left=2pt] {$A$} -- (3,1.5) coordinate (B) node [right=2pt] {$B$}; \draw[-stealth] (0.5,3) coordinate (C) node [left=2pt] {$C$} -- (3.5,2.5) coordinate (D) node [above=4pt] {$D$}; \end{tikzpicture} \]
Эти векторы явно не пересекаются

Если нам требуется не только найти координаты пересечения прямых, задаваемых векторами, но и определить факт пересечения самих векторов, то нужно будет кроме коэффициента β аналогичным образом выразить и α, поскольку векторы физически пересекаются только тогда, когда α, β ∈ (0, 1), то-есть, оба коэффициента больше нуля и меньше единицы. На последок приведу небольшой пример кода на Delphi, в котором реализуется подобный алгоритм, но с одним коэффициентом.


Код: Delphi
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ExtCtrls;

type
  TForm1 = class(TForm)
    Image1: TImage;
    procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

  p0: TPoint;
  p1: TPoint;
  p2: TPoint;
  p3: TPoint;

implementation

{$R *.dfm}


procedure calc_interxzection();
var w1, z1, w2, z2, k2: Double;
px:TPoint;
begin
  z1 := p1.X - p0.X;
  z2 := p3.X - p2.X;

  w1 := p1.Y - p0.Y;
  w2 := p3.Y - p2.Y;

  k2 := (z1 * (p2.y - p0.y) + w1 * (p0.x - p2.x)) / (w1 * z2 - z1 * w2);

  px.X := round(p2.X + z2 * k2);
  px.Y := round(p2.Y + w2 * k2);

  Form1.Image1.Canvas.Brush.Color:=clBlack;
  Form1.Image1.Canvas.FillRect(Form1.Image1.ClientRect);

  Form1.Image1.Canvas.Pen.Color:=clRed;
  Form1.Image1.Canvas.MoveTo(p0.x, p0.y);
  Form1.Image1.Canvas.LineTo(p1.x, p1.y);

  Form1.Image1.Canvas.Pen.Color:=clGreen;
  Form1.Image1.Canvas.MoveTo(p2.x, p2.y);
  Form1.Image1.Canvas.LineTo(p3.x, p3.y);

  if((k2 > 0) and (k2 < 1))then begin

  Form1.Image1.Canvas.Pixels[px.x, px.y]:= clWhite;
  Form1.Image1.Canvas.Pixels[px.x, px.y + 1]:= clWhite;
  Form1.Image1.Canvas.Pixels[px.x + 1, px.y]:= clWhite;
  Form1.Image1.Canvas.Pixels[px.x - 1, px.y]:= clWhite;
  Form1.Image1.Canvas.Pixels[px.x, px.y - 1]:= clWhite;

  end;
end;


procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin

  if(Button = mbLeft)then begin
    p0.X:=x;
    p0.Y:=y;
  end;

  if(Button = mbRight)then begin
    p1.X:=x;
    p1.Y:=y;
  end;

  if(Button = mbMiddle)then begin
    p2.X:=x;
    p2.Y:=y;
  end;

  calc_interxzection;

end;

procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
  p3.X := x;
  p3.Y := y;

  calc_interxzection;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Set8087CW($133F);
end;

end.

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


Вообще говоря, пересечение двумерных векторов понадобилось мне при написании некоторого подобия физического движка для одной моей игры. Ранее я выводил еще один способ, с помощью определения угла между векторами, но, этот способ как мне показалось несколько лучше. Тогда я мало имел представления о высшей математике, поэтому приходилось импровизировать… Но сказать можно с уверенностью — подобные математические рассуждения не принесут вам ничего, кроме пользы, поскольку естественным образом развивают мышление, тренируют так сказать мозги. Поэтому, если вдруг какой-то формулы вы не знаете, не спешите кидаться её искать в учебнике. Подумайте, а вдруг вы сможете вывести её самостоятельно?

Ключевые слова математика, Программизм, векторы, уравнение, пересечение, формула
QR-код
Интересное
Исследуем множество Мандельброта В один прекрасный день, я проснулся утром с тяжелой головой, и внезапно ощутил потребность нарисовать красивый фрактал. Первое что пришло на ум, это конечно же знаменитое множество Мандельброта. Выпив чашечку чая, открыв Delphi 7, я приступил к делу.

Читать »»
Случайные фото