Matlab - Найти точку пересечения между двумя векторами

Ответ 1

Одним из решений является использование уравнений, полученных в этот учебник для поиска точки пересечения двух строк в 2-D ( update: это ссылка на интернет-архив, поскольку сайт больше не существует). Вы можете сначала создать две матрицы: одну, чтобы удерживать координаты x конечных точек линии, и одну, чтобы удерживать координаты y.

x = [0 0; 6 6];  %# Starting points in first row, ending points in second row
y = [0 6; 6 0];

Уравнения из вышеупомянутого источника затем могут быть закодированы следующим образом:

dx = diff(x);  %# Take the differences down each column
dy = diff(y);
den = dx(1)*dy(2)-dy(1)*dx(2);  %# Precompute the denominator
ua = (dx(2)*(y(1)-y(3))-dy(2)*(x(1)-x(3)))/den;
ub = (dx(1)*(y(1)-y(3))-dy(1)*(x(1)-x(3)))/den;

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

xi = x(1)+ua*dx(1);
yi = y(1)+ua*dy(1);

Для примера в вопросе приведенный код дает xi = 3 и yi = 3, как и ожидалось. Если вы хотите проверить, что точка пересечения находится между конечными точками линий (т.е. Это конечные сегменты линии), вам просто нужно проверить, что значения ua и ub лежат между 0 и 1:

isInSegment = all(([ua ub] >= 0) & ([ua ub] <= 1));

Еще несколько пунктов из учебника, связанного с выше:

• Если знаменатель den равен 0, то две строки параллельны.
• Если знаменатель и числитель для уравнений для ua и ub равны 0, то две линии совпадают.

Ответ 2

Хорошо, что у вас действительно есть 2 точки на 2 разных строках, и вы хотите найти пересечение. Самый простой способ - найти уравнения двух линий, а затем вычислить пересечение.

Уравнение прямой задается формулой y = mx + b, где m - наклон, а b - y-перехват. Для одной линии у вас есть две точки, которые дают два уравнения. Итак, вы можете решить для констант m и b. Это дает следующие два уравнения:

 0=0*m+1*b  % using the first point x=y=0 into y=m*x+b
 6=6*m+1*b  % using the second point x=y=6

или в матричной форме

 [ 0 ] = [ 0 1 ]* [ m ]
 [ 6 ]   [ 6 1 ]  [ b ] 

Для первой строки константы могут быть вычислены в MATLAB на

 C1 = inv([0 1;6 1]*[1;0]; % m=C1(1) and b=C(2)

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

 m_1*x-y = -b_1
 m_2*x-y = -b_2

Все, что осталось, это написать указанную выше систему уравнений в матричной форме и решить

 [x] = inv [m_1 -1] * [-b_1]
 [y]       [m_2 -1]   [-b_2]

или в синтаксисе MATLAB

 I = inv([m_1 -1; m_2 -1])*[-b_1;-b_2]; % I is the intersection.

Примечания

• В соответствии с комментарием gnovice, если строки на самом деле являются отрезками линии, вам нужно проверить, находится ли пересечение между конечными точками сегментов линии

• Если два наклона равны, m_1 = m_2, то либо пересечения, либо бесконечно много пересечений не будет.

Ответ 3

Для общего многомерного решения вы решаете серию линейных систем.

Сначала вам нужно свести уравнения к линейной форме: Ax+By=C (при необходимости разверните размеры)

Для двух точек:

y - y1 = (y2 - y1) / (x2 - x1) * (x - x1)
y - y1 = (y2 - y1) / (x2 - x1) * x - (y2 - y1) / (x2 - x1) * x1
(y1 - y2) / (x2 - x1) * x + y - y1 = (y1 - y2) / (x2 - x1) * x1
(y1 - y2) / (x2 - x1) * x + y = (y1 - y2) / (x2 - x1) * x1 + y1
(y1 - y2) * x + (x2 - x1) * y = (y1 - y2) * x1 + (x2 - x1) * y1

A = (y1 - y2)
B = (x2 - x1)
C = (y1 - y2) * x1 + (x2 - x1) * y1 = A * x1 + B * y1

В вашем примере:

x1 = 0, x2 = 6, y1 = 0, y2 = 6
A1 = (0 - 6) = -6
B1 = (6 - 0) = 6
C1 = A1 * 0 + B1 * 0 = 0

x1 = 0, x2 = 6, y1 = 6, y2 = 0
A2 = (6 - 0) = 6
B2 = (6 - 0) = 6
C2 = A2 * 0 + B2 * 6 = 6 * 6 = 36

Затем сформируем матрицу с A B и C в строках:

[A1 B1 C1]
[A2 B2 C2]

[-6 6 0]
[ 6 6 36]

Теперь сведем к уменьшенной форме эшелона с помощью функции Matlab rref(matrix):

[ 1 0 3]
[ 0 1 3]

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

dim = 2;

% Do other stuff, ending with rref(matrix)

if (matrix(:,1:dim) == eye(dim))
    % Matrix has unique solution.
    solution = (matrix(:,dim+1))'
else
    % No unique solution.
end

В двух измерениях вариации:

[ 1 B C]
[ 0 0 0]

[ 1 B C1]
[ 0 0 C2]

Ответ 4

Другие результаты сбивают с толку, подробные и неполные, imo. Итак, мои 2центы - также потенциально запутывающие и многословные.

Если вы уверены, что ваши линии не параллельны или параллельны, вам потребуется следующее:

% Let each point be def as a 3x1 array
% Let points defining first line be  : p1, q1
% Let points defining second line be : p2, q2

L=p1-p2;
M=p1-q1;
N=p2-q2;
A=[M N];
T=pinv(A)*L;
h=p1-T(1)*(p1-q1); % h is a 3x1 array representing the actual pt of intersection

Да, псевдо-обратная связь Мура-Пенроуза является мощным. Объяснение подхода: вы хотите найти веса или коэффициенты масштабирования "векторов направления" (M и N - векторы направления), которые линейно объединяют M и N, чтобы дать L.

Полное описание представлено ниже. В нем представлена ​​простая схема обнаружения исключений, их обработка предоставляется пользователю. (Минимальное расстояние между двумя строчными алгоритмами - от wikipedia, сравнение косинусов направления (DCS) для проверки векторных отношений общеизвестно)

% Let each point be def as a 3x1 array
% Let points defining first line be  : p1, q1
% Let points defining second line be : p2, q2

% There are two conditions that prevent intersection of line segments/lines
% in L3 space. 1. parallel 2. skew-parallel (two lines on parallel planes do not intersect)
% Both conditions need to be identified and handled in a general algo.

% First check that lines are not parallel, this is done by comparing DCS of
% the line vectors
% L, M, N ARE DIRECTION VECTORS.
L=p1-p2;
M=p1-q1;
N=p2-q2;


% Calculate normalized DCS for comparison. If equal, it means lines are parallel.
MVectorMagnitude=sqrt(sum(M.*M,2)); % The rowsum is just a generalization for N-D vectors
NVectorMagnitude=sqrt(sum(N.*N,2)); % The rowsum is just a generalization for N-D vectors

if isequal(M/MVectorMagnitude,N/NVectorMagnitude) % compare the DCS for equality
     fprintf('%s\n','lines are parallel. End routine')
end;

% Now check that lines do not exist on parallel planes
% This is done by checking the minimum distance between the two lines. If there a minimum distance, then the lines are skew.

a1 = dot(M,L); b1 = dot(M,M); c1 = dot(M,N);
a2 = dot(N,L); b2 = dot(N,M); c2 = dot(N,N);

s1 = -(a1*c2 - a2*c1)/(b1*c2-b2*c1);
s2 = -(a1*b2 - a2*b1)/(b1*c2-b2*c1);

Sm=(L + s1*M - s2*N);
s=sqrt(sum(Sm.*Sm,2));

if ~isequal(s,0) % If the minimum distance between two lines is not zero, then the lines do not intersect
    fprintf('%s\n','lines are skew. End routine')
end;

% Here the actual calculation of the point of intersection of two lines.
A=[M N];
T=pinv(A)*L;
h=p1-T(1)*(p1-q1); % h is a 3x1 array representing the actual pt of intersection

Таким образом, подход pinv даст вам результаты, даже если ваши M и N векторы искажены (но не параллельны, потому что требуется inv (A'.A)). Вы можете использовать это для определения минимального расстояния между двумя параллельными линиями или между двумя параллельными плоскостями. Для этого определите k = p2 + T (2) * (p2-q2), а затем требуемое расстояние h-k. Также обратите внимание, что h и k - точки на линиях, которые ближе всего друг к другу.

Таким образом, использование псевдоинверсивного и проекционного пространств дает нам краткий алгоритм для 1. Определение точки пересечения двух линий (не параллельной, а не перекошенной) 2. Определение минимального расстояния между двумя линиями (не параллельными) 3. Определение точек, наиболее близких друг к другу на двух линиях перекоса.

Краткий - это не то же самое, что с точки зрения времени. Многое зависит от вашей точной реализации функции pinv. Matlab использует svd, который решает допуск. Кроме того, некоторые результаты будут приблизительно точными в более высоких измерениях и определениях более высокого порядка метрики измерения (или векторных норм). Помимо очевидной независимой от размерности реализации, это можно использовать в статистическом регрессионном анализе и алгебраически максимизировать вероятность точечных оценок.

Enjoy.

-ssh