Наименьшее расстояние между точкой и линией в трехмерном пространстве - PullRequest
Новая
       22

Наименьшее расстояние между точкой и линией в трехмерном пространстве

0 голосов
/ 06 июня 2018

Я пытаюсь найти минимальное расстояние от точки (x0, y0, z0) до линии, соединенной (x1, y1, z1) и (x2, y2, z2), используя numpy или что-либо еще в python.К сожалению, все, что я могу найти в сети, связано с 2D-пространствами, и я довольно плохо знаком с Python.Любая помощь будет оценена.Заранее спасибо!

Ответы [ 2 ]

0 голосов
/ 07 июня 2018

Это дублирует решение @Hans Musgrave, но представьте, что мы ничего не знаем о «стандартных трюках с исчислением», которые «отлично работают», а также очень плохо работают с линейной алгеброй.

Все, что мы знаем:

  1. как рассчитать расстояние между двумя точками
  2. точка на линии может быть представлена ​​как функция двух точек и параметра
  3. мы знаем, найти минимум функции

(списки не дружат с блоками кода) 

def distance(a, b):
    """Calculate a distance between two points."""
    return np.linalg.norm(a-b)

def line_to_point_distance(p, q, r):
    """Calculate a distance between point r and a line crossing p and q."""
    def foo(t: float):
        # x is point on line, depends on t 
        x = t * (p-q) + q
        # we return a distance, which also depends on t        
        return distance(x, r)
    # which t minimizes distance?
    t0 = sci.optimize.minimize(foo, 0.1).x[0]
    return foo(t0)

# in this example the distance is 5
p = np.array([0, 0, 0])
q = np.array([2, 0, 0])
r = np.array([1, 5, 0])

assert abs(line_to_point_distance(p, q, r) - 5) < 0.00001

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

0 голосов
/ 06 июня 2018

StackOverflow не поддерживает Latex, поэтому я собираюсь замять некоторые математические.Одно из решений заключается в том, что если ваша линия охватывает точки p и q, то каждая точка на этой линии может быть представлена ​​как t*(p-q)+q для некоторого действительного значения t.Затем вы хотите минимизировать расстояние между вашей заданной точкой r и любой точкой на этой линии, и расстояние обычно является функцией единственной переменной t, поэтому стандартные методы исчисления работают нормально.Рассмотрим следующий пример, который вычисляет минимальное расстояние между r и линией, охватываемой p и q.От руки мы знаем, что ответ должен быть 1. 

import numpy as np

p = np.array([0, 0, 0])
q = np.array([0, 0, 1])
r = np.array([0, 1, 1])

def t(p, q, r):
    x = p-q
    return np.dot(r-q, x)/np.dot(x, x)

def d(p, q, r):
    return np.linalg.norm(t(p, q, r)*(p-q)+q-r)

print(d(p, q, r))
# Prints 1.0

. Это прекрасно работает в любом количестве измерений, включая 2, 3 и миллиард.Единственным реальным ограничением является то, что p и q должны быть разными точками, чтобы между ними была уникальная линия.

Я разбил код в приведенном выше примере, чтобы показать два разныхшаги, вытекающие из того, как я об этом думал математически (нахождение t и затем вычисление расстояния).Это не обязательно самый эффективный подход, и, конечно, это не так, если вы хотите знать минимальное расстояние для множества точек и одной и той же линии - вдвойне, если число измерений мало.Для более эффективного подхода рассмотрим следующее: 

import numpy as np

p = np.array([0, 0, 0])  # p and q can have shape (n,) for any
q = np.array([0, 0, 1])  # n>0, and rs can have shape (m,n)
rs = np.array([          # for any m,n>0.
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
    [0, 2, 1],
])

def d(p, q, rs):
    x = p-q
    return np.linalg.norm(
        np.outer(np.dot(rs-q, x)/np.dot(x, x), x)+q-rs,
        axis=1)

print(d(p, q, rs))
# Prints array([1.        , 1.        , 1.41421356, 2.        ])

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

...