C-Uebung

Binärbäume am Beispiel von kd-Trees

Listen |

Aufgabe “Binäre Bäume”:

Gegegen seien die folgenden Orte mit geografischen Koordinaten:

OrtKoordinate (Lat)Koordinate (Lon)
Nürnberg49.447811.0683
Fürth49.466710.9667
Erlangen49.589711.0039
Ansbach49.240210.4635
Forchheim49.723111.0669
Hersbruck49.512511.4339

a) Fügen Sie diese Orte als Punktkoordinaten in einen kd-Tree ein und suchen Sie den Ort, welcher der Koordinate Lat/Lon 49.59337889/11.09836936 am nächsten ist (nearest-neighbor search).

b) Benutzen Sie eine templatisierte Containerklasse, welche obige Funktionalität kapselt.

c) Suchen Sie alle Orte, die nicht mehr als 10km von Nürnberg entfernt sind. Dazu implementieren Sie eine entsprechende Suchmethode, welche alle Orte innerhalb eines bestimmen Suchradius um eine Suchkoordinate zurückliefert.

Hinweise:

  • Ein Punkt im 3D Raum mit den Koordinaten x,y,z wird durch die Vector3D Klasse repräsentiert.
  • Beim Einfügen der Orte in den Baum sind die ECEF Koordinaten der Orte der einzufügende 3D Punkt und die Ortsnamen das dazugehörige Datum.

Suchfunktionsparameter:

  • Als Suchparameter benötigen wir den Kreismittelpunkt (in ECEF Koordinaten) und den Suchradius (in Metern).
  • Die Such-Funktion gibt eine Liste der gefundenen Orte innerhalb des Suchradius zurück.
  • Für die Resultatsliste verwenden Sie den vorgefertigten vector Datentyp aus der Standard-Template-Library (STL).

Damit ergibt sich der Prototyp der Suchfunktion wie folgt:

std::vector<const Node *>
search(const Vector3D &center,
       double radius,
       const Node *node);

Suchalgorithmus:

  • Pseudocode
  • Befindet sich der Ort des aktuellen Knotens innerhalb des Suchkreises, so wird der Knoten dem Ergebnis-Vector mittels der push_back() Methode angehängt.
  • Die zwei Ergebnis-Vectoren des linken und rechten Abstiegs werden mittels der insert() Methode der STL kombiniert:
std::vector<T> a, b;
a.insert(a.end(), b.begin(), b.end());

Zusatzaufgabe:

Eine vollständige Liste aller Orte in Deutschland findet sich hier

Fügen Sie alle darin enthaltenen Orte in den Suchbaum ein (z.B. mittels fgets und strtok) und wiederholen Sie die vorherige Umkreissuche.

Graphische Zusatzaufgabe:

Visualieren Sie die Orte in Deutschland grafisch mit der Plot-Library oder Qt/QPainter und suchen Sie den jeweils nächsten Ort unter dem Mauszeiger (mouseMoveEvent):

NuernbergKDTree


Listen |

Options: