Ideale Datenstruktur zum Speichern von Kartendaten?

12

Das wurde ich in einem Interviewtest gefragt. Ich war beim Test in Ordnung, wusste aber nicht genug, um diese Frage zu beantworten. Ich bin gespannt, mit welchen Datenstrukturen ich die Daten schnell abfragen kann.

Grundsätzlich besteht die Idee darin, dass Straßenabschnitte (Linien, die aus Punkten bestehen) in einer Art Datenstruktur gespeichert werden. Es sollte schnell abgefragt werden können, welche Straßenabschnitte (oder Punkte) sich in einem bestimmten Abstand von einem Punkt (Radius) befinden.

algorithms data-structures Keyo
quelle
Um wirklich mehr zu erfahren, würde ich mich unter folgender Adresse informieren : cgal.org , dann diese Projekte anschauen : cgal.org/projects.html#gis , dasjenige finden, das Ihren Wünschen ähnelt, und dann die Verwendung der API und schließlich die studieren Zusammensetzung der API.
Job

Antworten:

16

Die typische Methode zum Speichern von geografischen Daten ist eine räumliche Datenstruktur wie ein R-Baum (oder eine Variante wie ein R + -Baum, ein R * -Baum usw.). So werden geografische Datentypen normalerweise in GIS-fähig implementiert RDBMS. (Ich weiß, dass sowohl Microsoft SQL Server 2008 als auch PostGIS R-Bäume für die geografischen Typen verwenden.) Sie erfüllen alle von Ihnen beschriebenen grundlegenden Anforderungen und unterstützen trivial Schnittpunkte, Positionen, Entfernungen und andere Abfragetypen.

Abhängig von der Art der Daten finden Sie möglicherweise auch häufig verwendete Dinge wie kD-Bäume, Quad-Bäume, Oktrees, Begrenzungsvolumenhierarchien (einschließlich achsenausgerichteter Begrenzungsrahmenbäume) usw. Dies ist in 3D-Spielen weitaus häufiger der Fall, da Größe und Form eines Objekts für Schnittpunktabfragen relevanter sind. Sie werden seltener für GIS verwendet als R-Bäume.

grau verblassen
quelle
0

Verschiedene Arten von Operationen an Kartendaten erfordern unterschiedliche Speicherformate für optimale Ergebnisse. Betrachten Sie beispielsweise die folgenden drei Aufgaben:

  1. Suchen Sie anhand eines bestimmten Punkts die Straße, die diesem Punkt am nächsten liegt
  2. Suchen Sie in einem bestimmten geografischen Gebiet einer bestimmten Größe alle Straßen, die sich in diesem Gebiet befinden.
  3. Finden Sie auf zwei Straßen den kürzesten Weg zwischen ihnen.

Die Unterschiede in den Anforderungen sind so groß, dass es wahrscheinlich besser ist, drei separate Kopien der Daten zu speichern, die jeweils für eine der oben genannten Aufgaben optimiert sind, als zu versuchen, es sei denn, man muss "Live" -Änderungen an der Karte berücksichtigen ein Format zu entwickeln, das alle drei Aufgaben gut bewältigen kann.

Superkatze
quelle