Рассчитать расстояние до ближайшего объекта
Мне нужно составить карту расстояний до ближайшего объекта. У меня есть решение, в котором я просматриваю каждую точку карты и каждый объект, вычисляю расстояние до них всех, а затем оставляю только минимальное расстояние. Проблема здесь в том, что если я просыпаюсь с реальными данными, карта может легко содержать десятки миллионов точек, а объектов может быть более 100. Есть ли лучшая реализация кода для решения этой проблемы?
Загрузка пакетов
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
Создать синтетическую карту
coord_dict = {"X": [],
"Y": []}
for x_value in range(0, 10000, 50):
for y_value in range(0, 5000, 50):
coord_dict["X"].append(x_value)
coord_dict["Y"].append(y_value)
map_df = pd.DataFrame(coord_dict)
Сгенерируйте точки для расчета расстояния от
well_points_dict = {"X": [500, 1500, 4000, 5500, 6250, 7500, 8000, 9000],
"Y": [500, 4000, 2000, 1500, 500, 5000, 100, 2500]}
wells_df = pd.DataFrame(well_points_dict)
Рассчитать расстояния
calculations_count = 0
distance_map = np.zeros(map_df.shape)
for i in range(map_df.shape[0]):
d = []
for j in range(wells_df.shape[0]):
d.append(((map_df["X"].iloc[i]-wells_df["X"][j])**2 + (map_df["Y"].iloc[i]- wells_df["Y"][j])**2)**0.5)
calculations_count += 1
dd = min(d)
distance_map[i,1] = dd
# print(calculations_count)
Распечатать полученную карту
plt.figure(figsize=(10,10))
plt.scatter(x=map_df["X"],y=map_df["Y"],c=distance_map[:,1],s=1,cmap='terrain')
for i in range(len(wells_df)):
plt.plot(wells_df["X"][i],wells_df["Y"][i], color='black', marker='o',markersize=3)
plt.title('Calculated map')
plt.xlabel('X')
plt.ylabel('Y')
plt.axis('scaled')
plt.tight_layout()
plt.colorbar(shrink=0.25)
Пример карты результатов:
@TimRoberts, это неправда. В одном измерении вы можете отсортировать массив. В более высоких измерениях что-то вроде k-дерева дает грубый аналог, и существует множество приближений.
Только бегло просмотрел, возможно, вы уже это делаете, просто убедитесь, что вы не вычисляете x->y и y->x.
Ответы 2
(Приблизительный) поиск ближайших соседей — обычная задача для множества библиотек. Удобное место для проверки — https://ann-benchmarks.com/ — лучший выбор зависит от ваших потребностей, но если у вас действительно есть 2D-данные с множеством точек, простое k-d дерево, скорее всего, ускорится. резко задавать вопросы, но при этом давать точные ответы. В более высоких измерениях вам, вероятно, придется отказаться от гарантированных точных ответов, но небольшое расслабление может дать вам огромный выигрыш в скорости.
KDTree - это то, что вы ищете, его реализация есть в scipy.spatial.
import numpy as np
import matplotlib.pyplot as plt
from scipy import spatial
Учитывая ваши пробные баллы:
x_value = np.arange(0, 10000, 50)
y_value = np.arange(0, 5000, 50)
X, Y = np.meshgrid(x_value, y_value)
points = np.stack([X.ravel(), Y.ravel()]).T
И хорошие моменты:
x_well = np.array([500, 1500, 4000, 5500, 6250, 7500, 8000, 9000])
y_well = np.array([500, 4000, 2000, 1500, 500, 5000, 100, 2500])
wells = np.stack([x_well, y_well]).T
Мы можем создать KDTree:
interpolator = spatial.KDTree(wells)
И эффективно запросите дерево, чтобы получить расстояния, а также индексы того, какая точка ближе:
distances, indices = interpolator.query(points)
# 7.12 ms ± 711 µs per loop (mean ± std. dev. of 30 runs, 100 loops each)
Построение графика результатов приводит к:
fig, axe = plt.subplots()
axe.scatter(*points.T, marker = ".", c=distances)
axe.scatter(*wells.T, color = "black")
axe.grid()
Мы видим диаграмму Вороного, появляющуюся на цветовой карте, которая является хорошим подтверждением правильности интерпретации расстояний относительно контрольных точек (скважин):
voronoi = spatial.Voronoi(wells)
# ...
spatial.voronoi_plot_2d(voronoi, ax=axe)
Где объект Вороного - это диаграмма Вороного, основанная на ваших опорных точках (колодцах) и voronoi_plot_2d помощник для ее рисования по осям.
Спасибо! Это сработало отлично! Не знал про KDTree=)
«Оставляя только минимальное расстояние» -- Расстояние чего? Если вам нужно минимальное расстояние от каждой точки до каждой другой точки, то у вас нет другого выбора, кроме как попробовать их все, что вы и делаете.