Ich möchte eine App erstellen, die Ihnen das nächstgelegene Restaurant abhängig von Ihrem Standort gibt. Wir haben eine Datenbank mit allen POIs, die dem Restaurant entsprechen, und wir erhalten Ihren Standort mit dem GPS Ihres Telefons ...Was ist ein guter Algorithmus für das Problem des nächsten Nachbarn in zwei Dimensionen?
Welcher Algorithmus wäre angemessen? Wo finde ich gute Dokumentation?
Dank
Hier ist eine informative Präsentation: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
würde ich entweder eine Quadtree oder eine Kd-tree verwenden.
Hier finden Sie einige Benchmarks: http://www.flegg.net/brett/pubs/spatial/index.html. Es hängt wirklich von Ihrer Datengröße und -reichweite ab.
Das Hauptproblem besteht darin, wie Sie die Daten speichern und durchsuchen. Wenn Sie eine SQL-Datenbank verwenden, die keine räumlichen Indizes unterstützt (sagen wir SQLite unter Android), sollten Sie die räumlichen Daten in eine lineare Z-order-Kurve konvertieren. Der Algorithmus ist einfach, ich weiß über (gut, schrieb) this Implementierung.
Das ist toll Code Thomas, Chapeau! –
Doing nearest neighbour Abfragen auf einer großen Datenbank scheint nicht eine gute Sache zu tun, direkt auf Android sowieso. Der Datenbankserver ist dafür da, um schwere Lasten zu heben. –
@Tim ich stimme zu Z-Auftrag ist nicht so toll für eine große Datenbank. Seit meiner Antwort im Jahr 2010 habe ich übrigens einen [R-Tree] (http://h2database.com/html/mvstore.html#r_tree) implementiert, der effiziente Nearest-Neighbor-Abfragen ermöglichen soll (sobald dies implementiert ist) und sollte auch auf Android funktionieren. Aber es verwendet nicht SQLite. –