Pythonのgeoindexライブラリで近くの緯度経度の点を取得する

このように、緯度経度を表す数値のtupleが入ったリストから、指定した緯度経度で最も近い点を判定したいとします。

geo_pts = [
    (35.60, 139.71),
    (35.58, 139.82),
    # 以下略
]

ナイーブな実装

リストの中身をすべて計算するナイーブな実装です。

import math

def find(geo_pts, target):
    return max(geo_pts, key=lambda p: dist(p, target))

def dist(p1, p2):
    return math.sqrt(sum((x1 - x2) ** 2 for x1, x2 in zip(p1, p2)))

こんな挙動です。AWSのEC2 t2.mediumインスタンスで、15000個程度の点を探すのに20ms程度かかってしまいました。

print(find(geo_pts, (35.6, 139.7)))
# => (35.60, 139.71)

ちなみに、n個取得したい場合は、 heapq.nlargest が使えます。

geoindexライブラリでの実装

def main():
    geo_pts = [
      # 配列で読み込み
    ]
    index = GeoGridIndex(precision=4)
    for x in geo_pts:
        index.add_point(GeoPoint(x[0], x[1]))

    prev = time.time()
    print(find(index, (35.6, 139.7)))
    # => (Point(35.687659999999994, 139.71178), 9.80482739300054)
    print(time.time() - prev)



def find(index, target):
    return next(index.get_nearest_points(GeoPoint(*target), 10, 'km'))

AWSのEC2 t2.mediumインスタンスで、こちらの実装では4ms程度で値が返ってきました。

ちなみに、 GeoGridIndex の引数のCell Sizeの単位はkmで、 precision=4 を指定した場合は半径40/2=20kmの範囲以内で検索できます。私の要件では半径20kmでちょうどよかったため、これ以上の検証は行っていません。

Precision	Cell size
1	5000
2	1260
3	156
4	40
5	4.8
6	1.22
7	0.152
8	0.038