Nearest Neighbor Search: Python
Mam dwuwymiarową tablicę:
MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
[6588253.79, 1933602.89, 212.66, 0, 0],
etc...)
Pierwsze dwa elementyMyArray[0]
iMyArray[1]
sąX iY współrzędne punktów.
Dla każdego elementu tablicy chciałbym znaleźćnajszybszy sposób na zwrócenie pojedynczego najbliższego sąsiada w promieniuX jednostki. Zakładamy, że jest to przestrzeń 2D.
powiedzmy na ten przykładX = 6
.
Rozwiązałem problem, porównując każdy element z każdym innym elementem, ale zajmuje to około 15 minut, gdy twoja lista ma 22 tysiące punktów. Mamy nadzieję, że w końcu uruchomimy to na listach około 30 milionów punktów.
Przeczytałem o drzewach K-d i zrozumiałem podstawową koncepcję, ale miałem problem ze zrozumieniem, jak je napisać.