Um die nächstgelegenen Orte zu berechnen, die durch den Breiten- / Längengrad repräsentiert werden, habe ich darüber nachgedacht, die Karte in kleine Gitter mit etwa 100x100 Metern zu unterteilen. Im Wesentlichen würde jeder Punkt einem Raster zugewiesen werden.
Ich verstehe, dass ich stattdessen auch räumliche Indizes mit MySQL usw. verwenden könnte, aber ich plane, eine nicht-relationale Datenbank wie Cassandra zu verwenden, wo es schwierig wäre, auf räumlichen Objekten zu indizieren, und so eine Art von Approximationstechnik sei nett.
Was wäre der beste Weg, ein solches Grid-System zu erstellen und die zweidimensionalen räumlichen Positionen darauf abzubilden?
Edit1: Es könnte in Ordnung sein, wenn die Gitter nicht perfekt einheitlich sind, mehr um die Pole.
Die Abbildung von den zweidimensionalen räumlichen Koordinaten auf Ihren räumlichen Index / Geohash ist ein interessantes Problem. Sie können sich diesen Artikel über Quadtrees, Geohashes anschauen und Hilbert-Kurven . Die Hilbert-Kurve ist eine raumfüllende Kurve, die einen Ort liefert; Für Ihre Zwecke bedeutet dies, dass nahegelegene Objekte im eindimensionalen räumlichen Index in einem zweidimensionalen Raum in der Nähe liegen.
Das Ziel (wie von anderen Respondern beschrieben) besteht darin, die Anzahl der Abfragen zu minimieren, die erforderlich sind, um den fraglichen Speicherplatz abzudecken, ohne dass Tonnen unnötiger Daten vom Server angefordert werden. Wie Sie das Mapping vom 2-d-Raum auf einen 1-d-Index vornehmen, beeinflusst dieses Ziel.
Ohne die genauen Anwendungsanforderungen zu kennen, ist Geohashing möglicherweise eine geeignete Technik: Ссылка
"Es handelt sich um eine hierarchische räumliche Datenstruktur, die den Raum in Eimer mit Gitterform unterteilt. Geohashes bieten Eigenschaften wie beliebige Genauigkeit und die Möglichkeit, Zeichen am Ende des Codes schrittweise zu entfernen, um seine Größe zu reduzieren (und allmählich die Genauigkeit zu verlieren). "
Sie können kein rechteckiges Gitter erstellen, das einheitlich einen Globus abbildet. Wenn das Raster einheitlich sein muss, müssen Sie stattdessen Dreiecke verwenden. Aber im Allgemeinen bezweifle ich, dass dies Ihr Problem lösen wird. Was Sie brauchen, ist ein 2D Octree (dies ist ein Google-Suchlink; sehen Sie sich die Bilder an, um einen einfachen Hinweis darauf zu erhalten.) funktioniert): Sie müssen Ihre Koordinaten in Hierarchien aufteilen (zum Beispiel Norden / Süden / Osten / Westen des Ursprungs für die erste Ebene und dann zwischen 90 Grad usw.).
Dann können Sie ein paar Selects machen, die schnell das kleinste Rechteck ergeben, das vorhandene Koordinaten enthält. Jetzt können Sie die Größe des Rechtecks überprüfen. Wenn es & lt; 100m, dann hast du eine Lösung gefunden. Andernfalls haben Sie nur ein paar Positionen zu überprüfen (normalerweise eine).
Google für "Octree SQL-Datenbank" für Implementierungen.
Tags und Links geolocation geospatial spatial grid maps