如何使用Python在二维网格中找到最近邻点坐标

Question

我想为第二个数据库中存储的每一个点找到在geoida数据库中最近的点。以下是我的方法，但速度非常慢。geoida.db里存储了超过55000个坐标。

import sqlite3
from kdtree import KDTree

database = sqlite3.connect('geoida.db')
cursor = database.cursor()
cursor.execute("select lat, lon  from coords")
geoid = cursor.fetchall()

database = sqlite3.connect('F.tsj')
cursor = database.cursor()
cursor.execute("select C1, C2 from tblSoPoints") 
results = cursor.fetchall()
for line in results:
    tree = KDTree.construct_from_data(geoid)
    nearest = tree.query(query_point=line, t=2)
    print nearest[0]

这两个数据库都包含了经纬度信息。

Answer 1

你为什么要一次又一次地构建KD树呢？我觉得你应该只构建一次，然后对每个点进行查询。构建这个树的复杂度是O(N log N)（或者根据算法不同，可能是O(N (log N)^2)），所以如果你做N次，就会让你的算法复杂度变成O(N^2 log N)。如果只构建一次树，然后进行查询，复杂度就能保持在O(N log N)了。

Answer 2

简单来说，就是在循环外面创建树：

tree = KDTree.construct_from_data(geoid)
for line in results:
  nearest = tree.query(query_point=line, t=2)