У меня есть набор координат x и y, и я хочу построить самый большой набор, для которого dist(x_i, x_j) >= limit для каждой пары точек. Поскольку набор довольно большой, лучше было бы лучше, чем квадратичное c масштабирование.
В качестве первого приближения к этому набору я использовал процедуру поиска по диапазону структуры Kdtree, с помощью которой точки удаляются последовательно из исходного набора.
import numpy as np
from scipy.special import cKDTree
def remove_pairs(xarr, yarr, max_sep):
"""
Removes points which have neighbours closer than some distance.
"""
npoints = len(xarr)
tree = cKDTree(np.c_[xarr.ravel(), yarr.ravel()])
tokeep = [True]*npoints
for point in range(npoints):
too_close = np.asarray(tree.query_ball_point([xarr[point], yarr[point]], max_sep))
# Distance of two points symmetric --> remove points with lower indices
if len(too_close[too_close>point]) > 0:
tokeep[point] = False
return np.asarray(tokeep)
Хотя эта функция дает правильный результат (то есть, что все точки будут разделены некоторым минимальным расстоянием) довольно быстро, она не дает наибольшего из таких возможных наборов. Причиной в моей реализации этого сбоя является то, что по умолчанию всегда удаляются точки, когда есть другие точки в пределах диапазона исключения.
Вам известен способ получить (или, по крайней мере, приблизиться) к наибольшему набору, пока не увеличивает время выполнения на много?