Ich habe eine Memory-Mapped-Datei von vielen Millionen von 3D-Punkten als ein STL-Vektor mit CGAL. Bei einer beliebigen Ebene, die den Datensatz in ungefähr gleiche Teile aufteilt, möchte ich den Datensatz so sortieren, dass alle inneren Punkte im Vektor und die äußeren Punkte zusammenhängen. Dieser Prozess muss dann auf eine beliebige Tiefe wiederholt werden, wodurch ein nicht achsvereinigter BSP-Baum entsteht.Teilen eines Vektors von Punkten in zwei Räume
Aufgrund der Größe des Datensatzes möchte ich dies wenn möglich tun. Ich habe einen Prädikat-Funktor, mit dem ich einen filtered_iterator erstelle, aber natürlich sortiert er die Punkte nicht, sondern überspringt nur nicht übereinstimmende. So kann ich einen zweiten Vektor erstellen und die sortierten Punkte in das kopieren, und den ursprünglichen Vektor Round-Robin-Stil wiederverwenden, aber ich möchte das möglichst vermeiden, wenn ich nur die Iteratoren behalte, die den Start markieren und Ende jedes Raumes.
Beachten Sie, dass es in CGAL bereits eine kd-Baum-Datenstruktur gibt, die vielleicht Ihren Anforderungen entspricht ... –
Wahr, obwohl kd-Bäume Achsen-ausgerichtete Ebenen verwenden, und meins muss beliebig ausgerichtet sein. Auch (und ich habe das aus meiner Frage weggelassen, mein Schlechter), speichern kd-Bäume Punkte nur in den Blattknoten und ich brauche einige Punkte in Verzweigungsknoten. Aber danke, dass du es erwähnt hast! – MerseyViking