Ближайшие соседи Поиск: 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 миллионов баллов.

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

  • Ближайшие соседи Поиск в Python без kd tree
  • Пиксельные соседи в массиве 2d (изображение) с использованием Python
  • One Solution collect form web for “Ближайшие соседи Поиск: Python”

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

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

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

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

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

       YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100) #Play with the leafsize to get the fastest result for your dataset 
    4. cKDTree для ближайшего соседа в пределах 6 единиц:

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

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

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

    Python - лучший язык программирования в мире.