Расстояния между точками

Где ближайший магазин? Какие два города дальше всего друг от друга? Какие покупатели похожи? Всё это — вопросы о расстояниях. Точку на карте удобно хранить как массив из двух координат, а много точек — как таблицу (n, 2): строка — точка.

Расстояние между двумя точками

Расстояние по прямой — теорема Пифагора из урока о векторизации: разности координат, квадраты, сумма, корень. Для этого есть готовая функция np.linalg.norm — норма, то есть длина вектора. Модуль np.linalg — линейная алгебра, раздел математики о векторах и матрицах. Расстояние между точками — длина их разности:

[ ]Длина вектора и расстояние

import numpy as np

v = np.array([3, 4])
print(np.sqrt((v ** 2).sum()))
print(np.linalg.norm(v))

a = np.array([1, 1])
b = np.array([4, 5])
print(np.linalg.norm(a - b))     # расстояние между точками a и b

Выводсохранённый · нажмите «Выполнить», чтобы получить свой

5.0
5.0
5.0

Вопрос

Что выведет print(np.linalg.norm(np.array([6, 8])))?

От одной точки до многих

Три кафе — таблица (3, 2), наша точка — массив (2,). Их разность — транслирование: точка вычитается из каждой строки таблицы, и получается таблица разностей (3, 2). А np.linalg.norm(…, axis=1) считает длину каждой строки — как агрегаты с axis, — то есть расстояние до каждого кафе:

[ ]Расстояния до трёх кафе

cafes = np.array([[0, 0], [2, 1], [5, 5]])
me = np.array([1, 1])
print(cafes - me)                            # разность с каждой строкой
print(np.linalg.norm(cafes - me, axis=1))    # длина каждой строки — три расстояния

Выводсохранённый · нажмите «Выполнить», чтобы получить свой

[[-1 -1]
 [ 1  0]
 [ 4  4]]
[1.41421356 1.         5.65685425]

[ ]Упражнение 1Ближайший магазин решено

В shops — координаты шести магазинов (км), в home — координаты дома. Сохраните в dists расстояние от дома до каждого магазина, а в nearest — номер строки ближайшего магазина.

shops = np.array([
    [1.0, 2.0],
    [4.0, 6.0],
    [-2.0, 3.0],
    [3.0, -1.0],
    [0.5, 5.0],
    [6.0, 2.0],
])
home = np.array([2.0, 3.0])
dists = ...
nearest = ...

Эталонное решение

shops = np.array([
    [1.0, 2.0],
    [4.0, 6.0],
    [-2.0, 3.0],
    [3.0, -1.0],
    [0.5, 5.0],
    [6.0, 2.0],
])
home = np.array([2.0, 3.0])
dists = np.linalg.norm(shops - home, axis=1)
nearest = dists.argmin()

Все попарные расстояния

Расстояния между всеми парами точек дают таблицу (n, n): в строке i, столбце j — расстояние от точки i до точки j. Её строят тем же приёмом, что таблицу всех пар в модуле о транслировании и все исходы трёх кубиков в мини-проекте о костях. Возьмём три точки pts формы (3, 2). pts[:, np.newaxis, :] имеет форму (3, 1, 2), pts[np.newaxis, :, :] — (1, 3, 2); их разность транслируется до трёхмерного (3, 3, 2): в diff[i, j] лежит pts[i] - pts[j] — две разности координат для пары точек i и j. Норма по последней оси — axis=2 — превращает каждую пару разностей в расстояние, и остаётся таблица (3, 3):

[ ]Таблица расстояний между тремя точками

pts = np.array([[0, 0], [3, 4], [6, 0]])
diff = pts[:, np.newaxis, :] - pts[np.newaxis, :, :]
print(diff.shape)
print(diff[1, 0])          # pts[1] - pts[0]
table = np.linalg.norm(diff, axis=2)
print(table)

Выводсохранённый · нажмите «Выполнить», чтобы получить свой

(3, 3, 2)
[3 4]
[[0. 5. 6.]
 [5. 0. 5.]
 [6. 5. 0.]]

pts[np.newaxis, :, :] можно и не писать: по первому правилу транслирования pts сам дополнится единицей слева до (1, 3, 2), так что pts[:, np.newaxis, :] - pts даёт то же самое.

На диагонали нули: расстояние от точки до самой себя. Таблица симметрична: от i до j столько же, сколько от j до i.

[ ]Упражнение 2Самые далёкие города решено

В towns — координаты пяти городов. Постройте для них таблицу попарных расстояний dist и сохраните в max_dist наибольшее расстояние между двумя городами.

towns = np.array([[0, 0], [3, 4], [6, 0], [7, 5], [2, 9]])
dist = ...
max_dist = ...

Эталонное решение

towns = np.array([[0, 0], [3, 4], [6, 0], [7, 5], [2, 9]])
dist = np.linalg.norm(towns[:, np.newaxis, :] - towns[np.newaxis, :, :], axis=2)
max_dist = dist.max()

Как найти для каждой точки ближайшую другую? argmin по строке найдёт ноль на диагонали — саму точку. Диагональ нужно исключить: заполним её бесконечностью np.inf — числом, которое больше любого другого. np.fill_diagonal(a, значение) записывает значение на диагональ таблицы — меняет её на месте:

[ ]Ближайший сосед каждой точки

demo = table.copy()
np.fill_diagonal(demo, np.inf)
print(demo)
print(demo.argmin(axis=1))

Выводсохранённый · нажмите «Выполнить», чтобы получить свой

[[inf  5.  6.]
 [ 5. inf  5.]
 [ 6.  5. inf]]
[1 0 1]

[ ]Упражнение 3Ближайший сосед решено

Сделайте копию dist в no_self, заполните её диагональ np.inf и сохраните в neighbor номер ближайшего другого города для каждого города, а в neighbor_dist — расстояние до него.

no_self = ...
neighbor = ...
neighbor_dist = ...

Эталонное решение

no_self = dist.copy()
np.fill_diagonal(no_self, np.inf)
neighbor = no_self.argmin(axis=1)
neighbor_dist = no_self.min(axis=1)

Итоги

np.linalg.norm(v) — длина вектора; расстояние между точками — np.linalg.norm(a - b).
До многих точек — np.linalg.norm(points - p, axis=1).
Попарные расстояния — разность (n, 1, 2) и (1, n, 2), норма по axis=2.
np.inf — бесконечность; np.fill_diagonal — записать значение на диагональ.

Вход

Расстояние между двумя точками

От одной точки до многих

Все попарные расстояния

Итоги

Подробнее в справочнике