Предположим, я хочу найти «точку пересечения» двух произвольных многомерных линий.Две линии на самом деле не будут пересекаться , но я все же хочу найти самую точку пересечения (т. Е. Точку, максимально приближенную ко всем линиям).
Предположим, что эти линии имеют векторы направления A, B и начальные точки C, D. Я могу найти самую точку пересечения, просто установив линейную задачу наименьших квадратов: преобразование линииуравнение пересечения
Ax + C = By + D
в форму наименьших квадратов
[A, -B] @ [[x, y]] = D - C
, где @ стандарты для вектора времени матрицы, и затем я могу использовать, например, np.linalg.lstsq для его решения.
Но как мне найти «самую пересекающуюся точку» из 3 или более произвольных линий?Если я буду следовать тому же правилу, у меня теперь будет
Ax + D = By + E = Cz + F
Единственный способ, которым я могу думать, это разложить это на три уравнения:
Ax + D = By + E
Ax + D = Cz + F
By + E = Cz + F
и преобразовать их в форму наименьших квадратов
[A, -B, 0] [E - D]
[A, 0, -C] @ [[x, y, z]] = [F - D]
[0, B, -C] [F - E]
Проблема в том, что размер задачи наименьших квадратов увеличивается квадратично по отношению к числу строк.Мне интересно, есть ли более эффективный способ решения линейной задачи наименьших квадратов, равной n-путям ?
Я думал о необходимости By + E = Cz + F выше, предоставляя два других термина,Но поскольку эта проблема не имеет точного решения (то есть они фактически не пересекаются), я считаю, что это создаст больший «вес» для некоторой переменной?
Спасибо за вашу помощь!
РЕДАКТИРОВАТЬ
Я только что проверил соединение первого члена со всеми другими членами в n-way-равенства (и без других пар), используя следующий код
def lineIntersect(k, b):
"k, b: N-by-D matrices describing N D-dimensional lines: k[i] * x + b[i]"
# Convert the problem to least-square form `Ax = B`
# A is temporarily defined 3-dimensional for convenience
A = np.zeros((len(k)-1, k.shape[1], len(k)), k.dtype)
A[:,:,0] = k[0]
A[range(len(k)-1),:,range(1,len(k))] = -k[1:]
# Convert to 2-dimensional matrix by flattening first two dimensions
A = A.reshape(-1, len(k))
# B should be 1-dimensional vector
B = (b[1:] - b[0]).ravel()
x = np.linalg.lstsq(A, B, None)[0]
return (x[:,None] * k + b).mean(0)
Приведенный ниже результат показывает, что неверно , потому что первый член в n-way-равенства "взвешен по-другому".
Первый вывод - это разница между обычным результатом и результатом различного порядка ввода (порядок строк не имеет значения), где первый член не изменился .
второй вывод совпадает с первый член изменился .
k = np.random.rand(10, 100)
b = np.random.rand(10, 100)
print(np.linalg.norm(lineIntersect(k, b) - lineIntersect(np.r_[k[:1],k[:0:-1]], np.r_[b[:1],b[:0:-1]])))
print(np.linalg.norm(lineIntersect(k, b) - lineIntersect(k[::-1], b[::-1])))
приводит к
7.889616961715915e-16
0.10702479853076755