如何使用Spatial.kdTree树的point_id对象点的最近邻居

Question

帮助我。我卡住了。我有一个class的point。该类别的属性是lat,Long,point_id,name。有一些点有相同的Lat和Long。所以，我需要point_id作为点身份。其实，我想用kdTree的树来得到我的点的最近邻居。当我构造kdTree时，我没有问题，但是当我想知道我的最近邻点时，结果是最近邻居的列表(Lat,Long)，而我想point_id作为我的结果，因为有一些点具有相同的Lat和Long。

这是我的代码：

import numpy as np 
from scipy import spatial 
import psycopg2 
import math 
import psycopg2.extensions 

class Point: 
def __init__(self, id_point, name, Lat, Long): 
    self.id_point=id_point 
    self.name=name 
    self.Lat=Lat 
    self.Long=Long 

def Struktur_KdTree(points): 
    tree= spatial.KDTree(points) 
    return tree 

def getNearestPoint(tree,point,radius): 
    return tree.query_ball_point(point,radius) 

try: 
    conn = psycopg2.connect("dbname='Chicago_crime' user='postgres' host='localhost' password='1234'") 
except : 
    print "I'm unable to connect to the database" 

cur = conn.cursor() 
cur.execute("""SELECT id_objek, primary_descript, lat, long from data_crime""") 

data = [] 
Lat = [] 
Long = [] 
for id_jenis, jenis, lat, long in cur.fetchall(): 
    data.append(Point(id_point,name,Lat,Long)) 
    Lat.append(lat) 
    Long.append(long) 

dataPoints = zip (Lat,Long) 

tree = Struktur_KdTree(dataPoints) 
result=[] 
radius=2 
for point in dataPoint: 
    result.append(getNearestPoint(tree,point,radius)) 

请给我什么建议吗？

Answer 1

使用字典（或collections.defaultdict）记录从(lat, lng)元组到Points列表的映射。 用这个字典武装（我们称之为pointmap），给定一个(lat, lng)你将 能够查找在该位置的所有Points。

pointmap = collections.defaultdict(list) 
locations = set() 
for id_jenis, jenis, lat, lng in np.random.randint(10, size=(N, 4)): 
    point = Point(id_jenis, jenis, lat, lng) 
    pointmap[lat, lng].append(point) 

在pointmap字典中的键是(lat, lng)元组，我们可以组建成NumPy的阵列将被传递到spatial.KDTree：

locations = np.array(pointmap.keys()) 
tree = spatial.KDTree(locations) 

现在，我们可以通过每个位置迭代并找到 最近分：

for loc in locations: 
    indices = getNearestPoint(tree, loc, radius) 

请注意，query_ball_point返回一个索引列表（该索引到 locations）。实际位置由locations[indices]给出。这里我们是 利用NumPy花式索引 - 成为可能，因为locations是 一个NumPy数组。

对于location[indices]每个位置，我们可以用我们的字典，pointmap查找相关的点，现在获得的Points列表：

near_points = [point for near_loc in locations[indices] 
       for point in pointmap[tuple(near_loc)]] 

---

全部放在一起：

import numpy as np 
from scipy import spatial 
import collections 

class Point: 

    def __init__(self, id_point, name, Lat, Long): 
     self.id_point = id_point 
     self.name = name 
     self.Lat = Lat 
     self.Long = Long 

    def __repr__(self): 
     return 'Point({}, {}, {}, {})'.format(
      self.id_point, self.name, self.Lat, self.Long) 

def getNearestPoint(tree, point, radius): 
    return tree.query_ball_point(point, radius) 

pointmap = collections.defaultdict(list) 

N = 10 
for id_jenis, jenis, lat, lng in np.random.randint(10, size=(N, 4)): 
    point = Point(id_jenis, jenis, lat, lng) 
    pointmap[lat, lng].append(point) 

locations = np.array(pointmap.keys()) 
tree = spatial.KDTree(locations) 

result = [] 
radius = 2 

for loc in locations: 
    indices = getNearestPoint(tree, loc, radius) 
    near_points = [point for near_loc in locations[indices] 
        for point in pointmap[tuple(near_loc)]] 
    print('{} close to {}'.format(loc, near_points)) 

产量如：

[8 3] close to [Point(2, 9, 8, 3)] 
[7 1] close to [Point(8, 6, 7, 1), Point(2, 1, 6, 1)] 
[4 5] close to [Point(7, 1, 4, 5), Point(4, 9, 3, 6)] 
[6 1] close to [Point(8, 6, 7, 1), Point(2, 1, 6, 1)] 
[2 0] close to [Point(0, 1, 2, 0), Point(4, 3, 4, 0)] 
[3 6] close to [Point(7, 1, 4, 5), Point(4, 9, 3, 6)] 
[7 9] close to [Point(1, 9, 7, 9)] 
[9 6] close to [Point(8, 5, 9, 6)] 
[2 4] close to [Point(4, 4, 2, 4)] 
[4 0] close to [Point(0, 1, 2, 0), Point(4, 3, 4, 0)]