Java-Datenstruktur zum Speichern von Breiten- und Längengradpunkten und zum Abrufen nach Gebiet

Ich möchte geografische Punkte zum schnellen Abrufen speichern:

  1. Ich speichere ein paar {Breitengrad, Längengrad, Java-Objekt}
  2. Ich frage nach allen Objekten innerhalb von n Kilometern um einen bestimmten Breitengrad, Längengrad

Anforderungen:

  • Kostenlos, Open-Source
  • Reines Java
  • Die Abfrage innerhalb eines "Rechtecks" (definiert durch lat1,long1-lat2,long2) ist ebenfalls in Ordnung, aber Kreis bevorzugt
  • Annäherungen OK, insbesondere wird die App nicht in der Nähe der Pole verwendet
  • Beharrlichkeit nicht erforderlich
  • Leicht. Das JAR sollte nicht mehr als ein Megabyte groß sein, hoffentlich viel weniger.

Nichtlösungen:

  • GeoRedis ist nicht eingebettet und nicht in Java
  • Geo-Baum ist nicht in Java
  • GeoTools ist zu groß
  • JTS erlaubt es nicht, nach allen Punkten abzufragen, wie aus seiner Dokumentation hervorgeht.

Antworten (2)

Es ist mehrere Monate her, seit Sie Ihre Anfrage gepostet haben, aber wenn Sie immer noch Bedarf haben, ziehen Sie bitte FeSimpleGeoProx in Betracht

Ich denke, es erfüllt alle Ihre angegebenen Anforderungen: FeSimpleGeoProx ist eine leichtgewichtige Sammlung von vom Benutzer bereitgestellten geografischen Punkten, die eine schnelle Näherungssuche durch Suche innerhalb eines Radius oder eines Rechtecks ​​unterstützt.

  • Kostenlos, Open Source (Apache-Version 2.0-Lizenz)
  • Reines Java
  • Unterstützt Abfrage innerhalb eines Kreises (Startpunkt und Radius)
  • Unterstützt Abfragen innerhalb eines "Rechtecks" (definiert durch lat1,long1-lat2,long2)
  • Mehrere Objekte können ohne Problemumgehung auf demselben Breiten-/Längengrad gespeichert werden.
  • Leicht. Die Gläser (sowohl FeProxiMap als auch LatLng, von denen es abhängt) sind zusammen weniger als 100 KB groß.

Im Leistungs-/Gewichtsspektrum liegt es zwischen der linearen Suche (leicht, aber langsam: für eine vernünftige Suche ist dies zwischen 100 und 1000 Mal schneller) und GeoRedis (das blitzschnell, aber schwerer ist). Außerdem sagt die Dokumentation zu GeoRedis, dass seine Antworten ungefähr sind, während diese genau so genau sind, wie LatLng es geben wird.

Haftungsausschluss: Ich bin der Autor von FeSimpleGeoProx . Außerdem stützt es sich auf das ausgezeichnete (und auch FOSS) SimpleLatLng , das separat heruntergeladen werden muss.

Sieht großartig aus! Verhält es sich zufällig in Polnähe richtig?
Danke, und ich denke, die Antwort ist "ja". Ich verlasse mich auf SimpleLatLng, von dem ich glaube, dass es Punkte in der Nähe der Pole gut handhabt - mein Suchding ist ziemlich genau so korrekt wie SimpleLatLng. Meine Komponententests (die einen Datensatz in der Nähe der Pole enthalten) zeigen identische Ergebnisse wie die Brute-Force-Überprüfung jedes Punkts im Datensatz, nur viel schneller für "vernünftige" Suchen.
Kühl! Haben Sie versucht zu prüfen, ab wie vielen Punkten FeSimpleGeoProx performanter wird als Brute-Force?
In der Tat habe ich. Wenn Sie die enthaltenen Leistungsbenchmarks ausführen, werden Sie feststellen, dass es viel schneller (100- bis 1000-mal) schneller auf einer nicht-trivialen Menge von Punkten ist, wenn Ihre Suche relativ klein ist, das heißt, wenn die zurückgegebene Menge von Punkten klein ist Teil der Gesamtpunktzahl im vollständigen Datensatz. Mit zunehmender Größe des zurückgegebenen Datensatzes nimmt die Leistung ab, und wenn die Suche schließlich alle oder fast alle (~ 80 %) der Punkte in der Welt zurückgibt, ist die Leistung tatsächlich schlechter als die lineare Suche.
@NicolasRaoul Wenn Sie es am Ende verwenden, teilen Sie mir bitte Ihre Erfahrungen mit. Ich habe es gebaut, um nützlich zu sein.
Könnten Sie bitte einen Kommentar unter github.com/nicolas-raoul/apps-android-commons/issues/141 posten ? Vielen Dank!
@NicolasRaoul habe ich, aber ich weiß nicht, was du sagen willst. ;]

Quadtree ist verwendbar:

... aber es hat einige Nachteile:

  • Die Suche erfolgt nicht nach Radius, sondern nach Rechtecken.
  • Flache Karte, funktioniert nicht in der Nähe der Pole.
  • Zwei verschiedene Objekte können nicht auf demselben Breiten-/Längengrad gespeichert werden. Dies kann umgangen werden, indem jedes Objekt zu einer Liste von Objekten gemacht wird.
Java-Datenstruktur zum Speichern von Breiten- und Längengradpunkten und zum Abrufen nach Gebiet
AntwortenHierDatenschutz-Bestimmungen1y, 0v