R Baum 50.000 Fuß Überblick?

Question

Ich arbeite an einem Schulprojekt, bei dem es darum geht, einen Breiten-/Längengrad zu ziehen und die fünf wichtigsten Punkte in einer bekannten Liste von Orten zu finden. Die Liste soll im Speicher gespeichert werden, mit dem Vorbehalt, dass wir eine "geeignete Datenstruktur" wählen müssen - das heißt, wir können nicht einfach alle Orte in einem Array speichern und Abstände einzeln nacheinander vergleichen. Der Lehrer schlug vor, die Ortsdaten nach US-Bundesstaat zu gruppieren, um zu verhindern, dass die Entfernung für Orte berechnet wird, die offensichtlich zu weit entfernt sind. Ich denke, ich kann es besser machen.

Aus meiner Forschung online scheint es, als ob ein R-Baum oder eine seiner Varianten eine saubere Lösung sein könnte. Leider ist dieser Satz so weit, wie ich mit dem Verständnis der tatsächlichen Technik verstanden habe, da die Literatur für meinen nicht-akademischen Kopf einfach zu dicht ist.

• Kann jemand geben Sie mir einen wirklich hohen Überblick darüber, was der Prozess ist ein R-Baum mit lat/long Daten zum Bestücken und durchquert dann den Baum diese fünf nächsten Nachbarn von einem bestimmten Punkt zu finden?

• Außerdem ist das Projekt in C, und ich muss das Rad nicht neu erfinden. Wenn Sie also eine vorhandene Open-Source-C-Implementierung eines R-Baums verwendet haben, wäre ich an Ihren Erfahrungen interessiert.

UPDATE:This blog post beschreibt einen einfachen Suchalgorithmus für einen regional abgeteilten Raum (wie eine PR Quadtree). Hoffnung, die einem zukünftigen Leser hilft.

Answer 1

Haben Sie alternative Datenstrukturen in Betracht gezogen? Ich glaube, anstelle von R-Baum wäre ein Point Quadtree effektiver für Ihre Bedürfnisse. Spatial Index Demos bietet einige Demos für eine Liste möglicher Datenstrukturen einschließlich R-Baum und Punkt-Quadtree. Hoffe es gibt einen Einblick.

Answer 2

Quad Trees

A quad tree nimmt einen Platz von Raum und teilt es in vier Kinder mit der Hälfte der Dimensionen entlang der X- und Y-Achse.

+---+---+ 
| | | Each square is a child 
| | | of the parent; when you 
+---+---+ get to leaves a node has 
| | | a single point or a list 
| | | of points. 
+---+---+ 

Diese Datenstruktur ist rekursiv und Sie für die Punkte suchen, indem geprüft, welches Kind den Punkt hält, bis Sie auf dem Blatt zu bekommen. Ein Blatt hat entweder ein einzelnes Mitglied (Punkt mit X, Y-Koordinaten) oder eine Liste von Mitgliedern, abhängig von der Implementierung. Wenn Sie einen Knoten füllen, teilen Sie ihn in 4 und verteilen die Kinder. Im Wesentlichen ist die Datenstruktur eine Verallgemeinerung eines binären Baums, so dass sie nicht notwendigerweise ausgeglichen ist.

ein Quad-Balancing Baum nicht für Ihre Zwecke erforderlich sein kann, und ist für den Leser als Übung - versuchen Sie auf dem Web-Suche nach ‚ausgewogenen Quadtree‘

Beachten Sie, dass diese Datenstruktur kann nicht Artikel-Index, können überlappen, aber wenn Sie nur Punkte speichern, wird dies kein Problem sein.

Finding nächste Nachbarn in einem Quadtree

Aus der Spitze von meinem Kopf, hier ist ein schneller und schmutziger Algorithmus für die Suche nach dem ‚n‘ nächste Nachbarn zu Ihrem Punkt. Es ist nicht notwendigerweise optimal effizient, aber es wird ziemlich einfach zu implementieren sein. Wenn jemand einen Link zu einem besseren hat, können Sie ihn gerne in einem Kommentar oder in einer Antwort posten.

• Suchen Sie den Quad-Baumknoten Ihren Punkt enthält, eine Liste seiner Eltern zu halten.

• Drücken alle Punkte in dem Knoten in eine Prioritätswarteschlange basierend auf ihre Entfernung von der Basispunkt (d.h. durch die Länge der Hypotenuse pro Pythagoras' Theorem). Abhängig von bei der Implementierung kann es einen oder mehrere pro Knoten geben. Für eine einfache Implementierung einer Prioritätswarteschlange Datenstruktur, nachschlagen 'binäre Heap'.

• Wenn einer der 'n' Punkte weiter entfernt ist als die Kanten der Bounding Box, fügen Sie den Inhalt seiner Nachbarn hinzu. Wenn sich der Basispunkt nahe am Rand der Begrenzungsbox befindet, ist es möglich, dass benachbarte Baumknoten Punkte enthalten, die näher als die in der Begrenzungsbox gefundenen Punkte sind. Sie müssen dazu den Baum sichern, deshalb müssen Sie Ihre übergeordneten Knoten im Auge behalten.

• Wenn alle "n" nächstgelegenen Punkte näher als die Ränder Ihrer Bounding Box sind, wissen Sie, dass es keine Nachbarn geben kann, die Sie verpasst haben. Daher müssen die "n" nächsten Punkte in diesem Feld Ihre "n" nächsten Nachbarn sein.