containerklasse für positionen
-
Hallo, irgendwie steh ich gerade total auf den schlauch.
Ich habe folgendes problem, ich möchte eine möglichst effektive weise daten über positionen speichern und diese wieder heraus suchen
eine position besteht aus einer x,y,z Koordinate.
Ich möchte nun sehr oft alle koordinaten innerhalb einer reichweite um einer anderen position ermittelnirgendwie fehlt mir gerade der zündelnde gedanke um diese idee um zu setzen. denn eine liste ist wohl auch nicht das effektivste. Ich hab gerade echt keine gute idee.
-
Ich glaube für solche Probleme sind R-Trees geeignet. Such mal danach, im Netz dürfte da einiges zu finden sein.
-
danke also ne grundidee ist es.... aber ich glaube hierfür nicht direkt verwendbar... denn die position die ich abprüfen möchte wird nicht in den Baum enthalten sein, ausserdem bräuchte ich ggf auch was um dynamische reichweiten zu ermitteln. Also mal 5 Felder, mal 20 Felder etc.
ich müsste die vielleicht irendwie gruppieren, ein wenig itererieren ist ja nicht das problem wenn ich wenigstens herausfinden könnte wenn ich nun zumindest in der gruppe bin bei der auf ajedenfall keins mehr innerhalb der reichweite dabei ist.
ich hätte es galt gerne im grunde so
positionsmap.insert( x,y,z );
gettAllInRange( x,y,z, area );
zur Zeit habe ich da schon etwas ähnliches, aber dort sind maximal 20 - 200 elemente drinnen da geht es noch über alles zu iterieren.
Aber hier könnten > 1000 elemente drinnen sein und dafür über alles zu itererieren ist zuviel. Ich glaube rtrees wären aber schon wieder zuviel overhead da ich ja nicht die entfernung von jeden zu jeden brauche sondern nur für einen übergebenen Wert abprüfen möchte.
-
Fedaykin schrieb:
danke also ne grundidee ist es.... aber ich glaube hierfür nicht direkt verwendbar... denn die position die ich abprüfen möchte wird nicht in den Baum enthalten sein, ausserdem bräuchte ich ggf auch was um dynamische reichweiten zu ermitteln. Also mal 5 Felder, mal 20 Felder etc.
Wenn Du die Sachen effizient abfragen willst wirste kaum um ne Baumstruktur rumkommen. Auch Dynamik ist bei R-Trees kein Problem. Das ist ein ziemlich mächtiges Konzept. Bei Wikipedia gibt's nen Link zu ner Seite die sich damit intensiv befasst. R-Trees können das was Du suchst alles und auch sehr effizient. Die wurden genau für solche Probleme konstruiert.
-
ich werde mir wohl mal in der bibliothek nen buch dazu ausleihen. Für mein problem komme ich wohl erstmal am besten die karte in gröbere Teilstücke zu rastern. Und dann über diese Teilmengen zu iterieren.
-
Fedaykin schrieb:
eine position besteht aus einer x,y,z Koordinate.
Ich möchte nun sehr oft alle koordinaten innerhalb einer reichweite um einer anderen position ermittelndafuer ist KD-tree optimal.
-
Vor allem ist der KD-Tree deutlich einfacher. Dafür kann er halt nicht so gut beliebige Anfragebereiche handlen. Für R-Trees gibt's übrigens im Netz diverse Implementierungen, auch für C++.
-
Jester schrieb:
...nicht so gut beliebige Anfragebereiche ...
naja, er wollte aus einer punktwolke reichweiten abhaengige queries machen, schneller als mit KD-trees geht es da nicht, wozu also unnoetig verkomplizieren...
-
Wikipedia zeigt nur nächstens Nachbarn und Achsenparallele Rechtecke als Anfragebereiche. Das scheint ja nicht das zu sein was er sucht. Hast Du ne ausführlichere Quelle zu KD-Trees?