Such benachbarte Punkte kd Bäume unter Verwendung

Question

Ich habe eine Reihe von Koordinaten in drei numpy Arrays enthalten: xarr, yarr und zarr (Positionen in jedem Array entsprechend gehören zu dem gleichen Punkt - also der erste Punkt ist, an xarr[0], yarr[0], zarr[0]) . Bei einem anderen Punkt im Raum unter P(x,y,z) würde ich gerne alle Punkte finden, die innerhalb einer Entfernung r von P(x,y,z) sind.

Meine aktuelle (und sehr ineffizient) Methode, dies zu tun, ist einfach durchlaufen und den Abstand zu jedem Punkt zu berechnen und sehen, ob es innerhalb r von P(x,y,z) ist.

Allerdings würde ich gerne SciPy k-d-Baum-Algorithmus, um dies zu tun, aber ich bin nicht wirklich sicher, wie man es zu implementieren (ich bin sehr neu in Python). Ich würde es wirklich schätzen, wenn jemand kurz einen Code umreißen könnte, der zeigt , wie man eine k-d Baum gegebene Daten in dem Format einstellt, das ich habe.

Ich kenne SciPy documentation of its k-d tree implementation, Ich habe darüber aussehen, aber ich bin immer noch verwirrt, wie der Baum erstellen die Daten in dem Format gegeben Ich habe (np.mgrid und ravel() genannt wurden, und ich verstehe nicht ganz, warum).

Danke!

Answer 1

die Importe Weglassen ... Ich weiß nicht Ihre Daten haben, so habe ich zu fälschen einige ...

In [40]: x = np.random.random(100) 
In [41]: y = np.random.random(100)  
In [42]: z = np.random.random(100)  
In [43]: p = np.random.random(3)  
In [44]: p 
Out[44]: array([ 0.60515083, 0.39263392, 0.36129813]) 

nämlich drei Anordnungen von Koordinaten und einen Punkt für die ich die Nachbarn suchen.

Als nächstes, wie kann ich ein Array mit so vielen Zeilen wie die verschiedenen Datenpunkte und drei Spalten erstellen ...

In [45]: np.vstack((x,y,z)).T.shape 
Out[45]: (100, 3) 

Nun, es ist richtig.

---

Wir bauen den kd Baum KDTree von scipy.spatial

In [46]: tree = KDTree(np.vstack((x,y,z)).T) 

verwenden und dann verwenden wir eine der Methoden des Baumes, die .query_ball_point() treffend bezeichnete, die Indizes der Punkte zu finden, in der Nähe von p

In [47]: indices = tree.query_ball_point(p, 0.33) 

wo ich verwendet habe, gleich 1/3 eines Radius willkürlich.

---

Schließlich wollen wir diese Nachbarn sehen, so dass ich das .data Attribut des Baumes und die Indizes verwenden, die ich wie diese nur

In [48]: tree.data[indices] 
Out[48]: 
array([[ 0.4117843 , 0.21440852, 0.3352732 ], 
     [ 0.48921727, 0.13855976, 0.43331816], 
     [ 0.71598133, 0.32270361, 0.20292187], 
     [ 0.71761991, 0.27309708, 0.12670474], 
     [ 0.6282775 , 0.13752325, 0.4143872 ], 
     [ 0.55995847, 0.31302848, 0.2780926 ], 
     [ 0.75896359, 0.16043536, 0.33530071], 
     [ 0.81138529, 0.64635994, 0.33819097], 
     [ 0.43537193, 0.5353203 , 0.52095431], 
     [ 0.66996807, 0.48346547, 0.52761835], 
     [ 0.69426851, 0.24725511, 0.57650329], 
     [ 0.5350322 , 0.23155768, 0.62545958], 
     [ 0.51228139, 0.38078056, 0.61246054]]) 

berechnet haben, und das ist alles ...

Answer 2

Hier ist eine Erklärung des Beispiels in der scipy docs zur Verfügung gestellt:

from scipy import spatial 
x, y = np.mgrid[0:4, 0:4] 

np.mgrid ein x Maschengitter erzeugt, y von 0 bis 4. Da Sie bereits Ihre x, y, z-Koordinaten haben, sind Sie werde diesen Schritt überspringen.

points = zip(x.ravel(), y.ravel()) 
points = zip(xarr.ravel(), yarr.ravel(), zarr.ravel()) #in your case 
points = zip(xarr, yarr, zarr) # if x,y,z are already 1-d 

zip erstellt eine Liste von Tupeln jede x, y Punktepaar (Associate zusammen die Koordinaten für jeden Punkt) enthält. ravel flacht das x, y-Gitter ab (konvertiert ein n-d-Array in 1-d), sodass zip verwendet werden kann. In Ihrem Fall werden Sie nur ravel verwenden, wenn xarr, yarr, zarr nicht bereits 1-d sind.

tree = spatial.KDTree(points) 

Erstellen Index die Punkte, um schnelle Nachbarn nachschlagen.

tree.query_ball_point([2, 0], 1) 

nachschlagen Punkte innerhalb r=1 des Punktes [2,0]

Hoffnung, das hilft.