kd treeは k dimensional treeで, k次元領域の点探索などに用いられるデータ構造です。 kd treeを取り扱うモジュールがscipyにあります。
import scipy.spatial as ss from random import random # データ数 N = 10000 # (x座標, y座標)のデータリスト data = [(random()*100, random()*100) for _ in range(N)] # kd tree の作成 (leafsizeは展開をしない節内点数上限) tree = ss.KDTree(data, leafsize=10)
xの最近傍の点を探索(d: distance, i: index)
x = (10, 10) d, i = tree.query(x) print('most nearest node:', data[i])
xの距離r近傍の点を探索
x = (10, 10); r = 1 res = tree.query_ball_point(x, r) print('r =', r, 'near nodes', [data[i] for i in res])
距離がr以下のペアを全て探索
r = 1 res = tree.query_pairs(r) print('r =', r, 'pairs', res)
以上は2次元で考えていますが, より高次元でもkd treeを実行することができます。