yakın komşu Arama: Python

Question

bir 2 boyutlu dizi vardır:

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

ilk iki eleman MyArray[0] ve MyArray[1] noktaları x ve Y'nin koordinatlarıdır.

dizideki her eleman için, ben X birimlerinin bir yarıçap içindeki tek en yakın komşusu dönmek için hızlı yol bulmak istiyoruz. Bunun 2D uzayda olduğunu varsayıyoruz.

bu örnek için söyleyelim X = 6.

Her öğeyi diğer öğelere göre karşılaştırarak sorunu çözdüm, ancak listeniz 22k nokta uzunluğundaysa bu 15 dakika kadar sürüyor. Sonunda yaklaşık 30 milyon puanlık bir liste üzerinde çalışmayı umuyoruz.

K-d ağaçları hakkında okudum ve temel kavramları anladım, ancak bunları nasıl betimleyeceğinizi anlamakta sorun yaşadım.

Answer 1

John Vinyard'a scipy'yi önerdiği için teşekkürler.

Önkoşullar: Numpy ve scipy

1. İthalat scipy ve Numpy Modülleri

2. 5 bir kopyasını oluşturun yükleme bazı iyi araştırma ve testten sonra, burada bu soruya çözüm X ve Y değerleri dahil olmak üzere boyutsal dizi sadece.

3. gibi bir cKDTree bir örneğini oluşturmak:

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

4. sorgu yakın Komşu için cKDTree 6 birimleri içinde örneğin,

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

   her madde için YourArray olarak, TheResult olacak iki nokta arasındaki mesafenin bir tuple ve YourArray içinde noktasının konumu indeksi.

Bu, KD Ağaçları ile karışıklık yaşayan başkalarına yardım eder!