gần Neighbor Tìm kiếm: Python

Question

Tôi có một mảng 2 chiều:

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

Hai yếu tố đầu tiên MyArray[0] và MyArray[1] là tọa độ X và Y trong những điểm.

Đối với mỗi phần tử trong mảng, tôi muốn tìm các Cách nhanh nhất để trở lại hàng xóm gần nhất đơn của nó trong một bán kính X đơn vị. Chúng tôi giả định đây là không gian 2D.

cho phép nói ví dụ này X = 6.

Tôi đã giải quyết vấn đề bằng cách so sánh mọi phần tử với mọi phần tử khác, nhưng việc này mất 15 phút hoặc lâu hơn khi danh sách của bạn dài 22k. Chúng tôi hy vọng cuối cùng sẽ chạy trên danh sách khoảng 30 triệu điểm.

Tôi đã đọc về cây K-d và hiểu khái niệm cơ bản, nhưng đã gặp sự cố khi hiểu cách viết kịch bản.

Answer 1

Cảm ơn John Vinyard vì đã đề xuất scipy. Sau khi một số nghiên cứu tốt và thử nghiệm, đây là giải pháp cho câu hỏi này:

Điều kiện tiên quyết: Install NumPy và scipy

1. nhập các Modules scipy và NumPy

2. Tạo một bản sao của 5 mảng chiều bao gồm chỉ giá trị X và Y.

3. Tạo một thể hiện của một cKDTree như vậy:

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

4. Query các cKDTree cho hàng xóm gần trong vòng 6 đơn vị như vậy:

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

   cho mỗi mục trong YourArray, TheResult sẽ là một tuple của khoảng cách giữa hai điểm, và chỉ số của vị trí của điểm trong YourArray.

Hy vọng điều này sẽ giúp bất kỳ ai khác đã gặp phải sự nhầm lẫn với KD Trees!