Holen Sie sich mit der Geoindex-Bibliothek von Python nahegelegene Längen- und Breitengrade

Angenommen, Sie möchten auf diese Weise den nächstgelegenen Punkt bei einem bestimmten Breiten- und Längengrad aus einer Liste ermitteln, die ein Tupel von Zahlen enthält, die Breiten- und Längengrade darstellen.

geo_pts = [
    (35.60, 139.71),
    (35.58, 139.82),
    #Folgendes wird weggelassen
]

Naive Umsetzung

Eine naive Implementierung, die alles in der Liste berechnet.

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)))

Das ist das Verhalten. Es dauerte ungefähr 20 ms, um ungefähr 15.000 Punkte auf der EC2 t2.medium-Instanz von AWS zu finden.

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

Übrigens, wenn Sie n Teile erhalten möchten, können Sie heapq.nlargest verwenden.

Implementierung in der Geoindex-Bibliothek

https://pypi.org/project/geoindex/

def main():
    geo_pts = [
      #Als Array lesen
    ]
    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'))

In der EC2 t2.medium-Instanz von AWS wurde der Wert in dieser Implementierung in ca. 4 ms zurückgegeben.

Übrigens ist die Einheit der Zellengröße des Arguments von "GeoGridIndex" km, und wenn "Genauigkeit = 4" angegeben ist, kann es im Bereich des Radius 40/2 = 20 km gesucht werden. Ich habe keine weitere Überprüfung durchgeführt, da meine Anforderungen mit einem Radius von 20 km genau richtig waren.