Implementación de plantillas QuadTree u Octree en C++

Voy a escribir una implementación de plantillas de KDTree, que por ahora solo debería funcionar como Quadtree u Octree para una implementación de BarnesHut.Implementación de plantillas QuadTree u Octree en C++

El punto crucial aquí es el diseño, me gustaría especificar el número de dimensión donde se define el árbol como parámetro de plantilla y luego simplemente declarar algunos métodos comunes, que se comportan automáticamente de la manera correcta (creo que es especialización de plantilla necesario entonces).

Me gustaría especializar la plantilla para tener 2^2 (quadtree) o 2^3 (octree) nodos.

¿Alguien tiene algunas ideas de diseño? Me gustaría evitar la herencia porque me obliga a hacer una asignación de memoria dinámica en lugar de asignaciones estáticas.

Aquí N puede ser 2 o 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? 
};

Otro problema es que quadtree tiene 4 nodos pero 2 dimensión, octree tiene 8 nodos, pero 3 dimensión, es decir, número de nodos es 2^dimension. ¿Puedo especificar esto a través de metaprogramación de plantillas? Me gustaría mantener el número 4 y 8 para que el desenrollador de bucle pueda ser más rápido.

¡Gracias!

Fuente

2012-05-15 linello

Está utilizando el término "hoja" incorrectamente, el término correcto es "nodo". Una "hoja" es un nodo sin hijos. –

También está mezclando kdtrees y quad/octree incorrectamente, no son lo mismo (es decir, un árbol 2D no es igual a un árbol cuádruple) .. – KillianDS

Correcto, simplemente quiero un árbol n-ary que se comporte como un árbol cuádruple en 2D y octree en 3D, estoy editando la pregunta. – linello

Puede usar 1 << N en lugar de pow(2, N). Esto funciona porque 1 << N es una constante de tiempo de compilación, mientras que pow(2, N) no es una constante de tiempo de compilación (aunque se evaluará en tiempo de compilación de todos modos).

Fuente

2012-05-15 11:17:05

¡Buena idea! ¡gracias! ¿También crees que una implementación de este tipo es factible o buena? – linello

No. Creo que el código de la plantilla será más difícil de escribir y leer que dos implementaciones separadas: un quadtree y un octree. Es poco probable que encuentre N = 2 ya que tenemos mejores estructuras de datos especializadas para datos unidimensionales, y N> 3 es improbable debido al crecimiento exponencial del tamaño de cada nodo. –

Tiene razón, pero también estoy usando una biblioteca de álgebra lineal templada para operaciones vectoriales y de matriz (eigen), parece que es cuestión de verificar si N == 2 o N == 3, y luego escribir el código en consecuencia . Quise unirme a las dos implementaciones para fines de mantenimiento. Le mantendré informado – linello

Si está utilizando un compilador de C++ 11 que admite constexpr, puede escribir usted mismo un constexpr -version de pow para hacer el cálculo en tiempo de ejecución.

Fuente

2012-05-15 11:14:52

Lamentablemente no puedo tener ese compilador, y algunas características de C++ 11 todavía son oscuras para mí: P – linello

También puede hacerlo en C++ 03. Una meta-función de plantilla recursiva simple para poderes integrales es realmente fácil de hacer. Bud, si la base siempre es 2, estarás mucho mejor con cambios de bit, como sugiere Dietrich Epp. – Fiktik

Implementación de plantillas QuadTree u Octree en C++

Respuesta

Cuestiones relacionadas