Datenstruktur für Gebietssuchen
-
Hoi.
Ich habe ein Programm das viele Objekte mit x/y Koordinaten verwaltet. Jetzt möchte ich öfters mal alle Objekte suchen, die sich innerhalb eines gewissen X/Y Intervalls befinden.
Was die effizienteste Datenstruktur um solche Suchen performant durchführen zu können? Im Moment wird mit einem vector und linearer Suche konkurriert.Danke und Grüße,
Ethon
-
Algemeine Frage, allgemeine Antwort: http://en.wikipedia.org/wiki/Quadtree
-
Ah genau, super, danke.
-
Was die effizienteste Datenstruktur um solche Suchen performant durchführen zu können?
Kommt drauf an:
1.) Was fuer Objekte?
2.) Wofuer die Abfragen?
3.) Was fuer Intervalle/Bereiche?
4.) Effizienz im Sinne von Laufzeit/Speicherbedarf oder ein TradeoffAnsonsten: Trapezoidal Map.