QuadTree oder Octree templatized Implementierung in C++

Ich werde eine Template-Implementierung eines KDTree schreiben, die für jetzt nur als Quadtree oder Octree für eine BarnesHut-Implementierung funktionieren sollte.QuadTree oder Octree templatized Implementierung in C++

Der entscheidende Punkt hier ist das Design, ich möchte die Nummer der Dimension angeben, wo der Baum als Vorlage Parameter definiert ist und dann einfach einige gebräuchliche Methoden deklarieren, die automatisch den richtigen Weg (ich denke, einige Template-Spezialisierung ist benötigt dann).

Ich möchte die Vorlage spezialisieren, um 2^2 (Quadtree) oder 2^3 (Octree) Knoten zu haben.

Hat jemand Design-Ideen? Ich möchte Vererbung vermeiden, weil es mich dazu zwingt, dynamische Speicherzuteilung statt statische Zuordnungen vorzunehmen.

Hier kann N sein, 2 oder 3

template<int N> 
class NTree 
{ 
public: 
    NTree<N>(const std::vector<Mass *> &); 
    ~NTree<N>() 
    { 
     for (int i=0; i<pow(2,N); i++) 
      delete nodes[i]; 
    } 
private: 
    void insert<N>(Mass *m); 
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way? 
};

Ein weiteres Problem ist, dass Quadtree hat 4 Knoten, aber 2 Dimension Octree hat 8 Knoten, aber 3 Dimension, d.h. Anzahl der Knoten ist 2^dimension. Kann ich dies über Template-Metaprogrammierung angeben? Ich möchte die Nummer 4 und 8 behalten, damit der Loop-Abroller schneller sein kann.

Vielen Dank!

Quelle

2012-05-15 linello

Sie verwenden den Begriff "Blatt" falsch, der richtige Begriff ist "Knoten". Ein "Blatt" ist ein Knoten ohne Kinder. –

Sie mischen auch kdtrees und quad/octree falsch, sie sind nicht die gleichen (dh ein 2D-Baum ist nicht gleich einem Quadtree). – KillianDS

Richtig, ich möchte einfach einen n-ary Baum, der sich wie Quadtree in 2D verhält und Octree in 3D, ich bearbeite die Frage. – linello

Sie können 1 << N anstelle von pow(2, N) verwenden. Dies funktioniert, weil 1 << N eine Kompilierzeitkonstante ist, während pow(2, N) keine Kompilierzeitkonstante ist (obwohl sie trotzdem zur Kompilierzeit ausgewertet wird).

Quelle

2012-05-15 11:17:05

Schöne Idee! Danke! Denken Sie auch, dass eine solche templatisierte Implementierung machbar oder gut ist? – linello

Nein. Ich denke, der Template-Code wird schwieriger zu schreiben und zu lesen sein als zwei separate Implementierungen: ein Quadtree und ein Octree. Es ist unwahrscheinlich, dass Sie N = 2 treffen werden, da wir bessere Datenstrukturen haben, die auf eindimensionale Daten spezialisiert sind, und N> 3 ist aufgrund des exponentiellen Wachstums der Größe jedes Knotens unwahrscheinlich. –

Sie haben recht, aber ich verwende auch eine templatisierte lineare Algebra-Bibliothek für Vektor- und Matrixoperationen (Eigen), es scheint, es geht darum zu überprüfen, ob N == 2 oder N == 3, und schreibe den Code dann . Ich wollte die beiden Implementierungen für Wartungszwecke verbinden. ich werde dich auf dem Laufenden halten – linello

Wenn Sie einen C++ 11-Compiler verwenden, der constexpr unterstützt, könnten Sie sich eine constexpr -Version von pow schreiben, um die Berechnung zur Laufzeit durchzuführen.

Quelle

2012-05-15 11:14:52

Leider kann ich keinen solchen Compiler haben, und einige Features von C++ 11 sind mir noch unbekannt: P – linello

Das können Sie auch in C++ 03 tun. Eine einfache rekursive Vorlage Meta-Funktion für integrale Befugnisse ist wirklich einfach zu machen. Knospe, wenn die Basis immer 2 ist, bist du weit besser dran mit Bitverschiebung, wie Dietrich Epp vorschlägt. – Fiktik

QuadTree oder Octree templatized Implementierung in C++

Antwort

Verwandte Themen