Вычислить евклидово расстояние между массивом точек и отрезком в Python без цикла for - PullRequest
Новая
       35

Вычислить евклидово расстояние между массивом точек и отрезком в Python без цикла for

0 голосов
/ 30 января 2019

Я ищу функцию для вычисления евклидова расстояния между массивом точек с двумя координатами (x, y) и отрезком.Моя цель - получить результат менее 0,01 секунды для отрезка и 10 тыс. Точек.

Я уже нашел функцию для одной точки.Но запуск цикла for очень неэффективен.

Я также нашел эту функцию, которая вычисляет расстояние до бесконечной линии: 

def line_dists(points, start, end):
    if np.all(start == end):
        return np.linalg.norm(points - start, axis=1)

    vec = end - start
    cross = np.cross(vec, start - points)
    return np.divide(abs(cross), np.linalg.norm(vec))

Это очень эффективно, и я хотел бы иметь аналогичныйподход для ограниченной линии.

Спасибо за вашу помощь.

1 Ответ

0 голосов
/ 30 января 2019

Настройка - контрольная точка P, конечные точки A и B:

enter image description here

  • Взять точку-продукт P - A с normalize(A - B) для получения знакового компонента параллельного расстояния s из A.Аналогично с B и t.

  • Возьмите максимальное из этих двух чисел и ноль, чтобы получить фиксированную составляющую параллельного расстояния.Это будет ненулевое значение, только если точка находится за пределами "границы" ( Вороного региона ?) Отрезка.

  • Рассчитайте компоненту перпендикулярного расстояния, как и раньше, используя перекрестное произведение.

  • Используйте Pythagoras для вычисления необходимого ближайшего расстояния (серая линия от P до A).

Вышеуказанное не имеет разветвлений и поэтому легко векторизовать с помощью numpy: 

def lineseg_dists(p, a, b):

    # TODO for you: consider implementing @Eskapp's suggestions
    if np.all(a - b):
        return np.linalg.norm(p - a, axis=1)

    # normalized tangent vector
    d = np.divide(b - a, np.linalg.norm(b - a))

    # signed parallel distance components
    s = np.dot(a - p, d)
    t = np.dot(p - b, d)

    # clamped parallel distance
    h = np.maximum.reduce([s, t, np.zeros(len(p))])

    # perpendicular distance component, as before
    # note that for the 3D case these will be vectors
    c = np.cross(p - a, d)

    # use hypot for Pythagoras to improve accuracy
    return np.hypot(h, c)
...