Как найти координаты ближайшей соседней точки в двумерной сетке, используя python

Question

Я пытаюсь найти ближайшую точку в базе данных геоида для каждой точки, сохраненной во второй базе данных. Вот может подойти, что очень медленно. 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).

Answer 2

Просто создайте дерево вне цикла:

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