Ближайшие соседи Поиск: Python

У меня есть 2-мерный массив:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

Первые два элемента MyArray[0] и MyArray[1] являются координатами X и Y точек.

Для каждого элемента массива я хотел бы найти самый быстрый способ вернуть своего ближайшего соседа в радиус X единиц. Мы предполагаем, что это находится в 2D пространстве.

скажем в этом примере X = 6.

Я решил проблему, сравнивая каждый элемент с каждым другим элементом, но это занимает 15 минут или около того, когда ваш список имеет длину 22k. Мы надеемся, что в конечном итоге это запустит в списках около 30 миллионов баллов.

Я прочитал о деревьях K-d и понял основную концепцию, но мне было трудно понять, как script их.

Ответы

Ответ 1

Благодаря Джону Виняару за предложение scipy. После нескольких хороших исследований и испытаний, вот решение этого вопроса:

Предпосылки: Установите Numpy и SciPy

  • Импортируйте модули SciPy и Numpy

  • Сделайте копию 5-мерного массива, включая только значения X и Y.

  • Создайте экземпляр cKDTree как таковой:

    YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
#Play with the leafsize to get the fastest result for your dataset

  • Запросите cKDTree для ближайшего соседа в пределах 6 единиц:

    for item in YourArray:
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

    для каждого элемента в YourArray, TheResult будет кортежем расстояния между двумя точками и индексом местоположения точки в YourArray.

Надеюсь, что это поможет любому, кто испытал замешательство с деревьями KD!