python - 如何使用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

为什么要一遍又一遍地构建 KDTree？在我看来，您应该构建一次并针对每个点进行查询。构建树的时间复杂度为 O(N log N)(或 O(N (log N)^2)，具体取决于算法)，因此执行 N 次会使您的算法复杂度为 O(N^2 log N)。构建一次树并查询它将使复杂度保持在 O(N log N)。