Implementación de Quadtree -- ++ campo con c++11 campo con tree campo con coordinate-system camp codereview Relacionados El problema

Quadtree implementation


29
vote

problema

Español

He implementado una quadtree en C ++. Ignora cualquier similitud aparente con el pseudocódigo en Wikipedia, todo está en tu cabeza, lo juro.

¿Cómo puedo mejorarlo? Algoritmo Velocidad / Mejoras en el espacio, cualquier función adicional que pueda querer ... así como la práctica general.

  #ifndef _QUADTREE_H_ #define _QUADTREE_H_  #include <vector> #include <iostream>  struct Point {     float x, y;     Point(float x = 0, float y = 0):x(x), y(y){}; };  struct AABB {     Point centre;     Point halfSize;      AABB(Point centre = Point(), Point halfSize = Point()): centre(centre), halfSize(halfSize){};      bool contains(Point a)     {         if(a.x < centre.x + halfSize.x && a.x > centre.x - halfSize.x)         {             if(a.y < centre.y + halfSize.y && a.y > centre.y - halfSize.y)             {                 return true;             }         }         return false;     }      bool intersects(AABB other)     {         //this right > that left                                          this left <s that right         if(centre.x + halfSize.x > other.centre.x - other.halfSize.x || centre.x - halfSize.x < other.centre.x + other.halfSize.x)         {         // This bottom > that top             if(centre.y + halfSize.y > other.centre.y - other.halfSize.y || centre.y - halfSize.y < other.centre.y + other.halfSize.y)             {                 return true;             }         }         return false;     } };  template <typename T> struct Data {     Point pos;     T* load;      Data(Point pos = Point(), T* data = NULL): pos(pos), load(data){}; };   template <class T> class Quadtree {     private:         //4 children         Quadtree* nw;         Quadtree* ne;         Quadtree* sw;         Quadtree* se;          AABB boundary;          std::vector< Data<T> > objects;          int CAPACITY;            public:         Quadtree<T>();         Quadtree<T>(AABB boundary);          ~Quadtree();          bool insert(Data<T> d);         void subdivide();         std::vector< Data<T> > queryRange(AABB range); };  template <class T> Quadtree<T>::Quadtree() {     CAPACITY = 4;     nw = NULL;     ne = NULL;     sw = NULL;     se = NULL;     boundary = AABB();     objects = std::vector< Data<T> >(); }  template <class T> Quadtree<T>::Quadtree(AABB boundary) {     objects = std::vector< Data<T> >();     CAPACITY = 4;     nw = NULL;     ne = NULL;     sw = NULL;     se = NULL;     this->boundary = boundary; }  template <class T> Quadtree<T>::~Quadtree() {     delete nw;     delete sw;     delete ne;     delete se; }  template <class T> void Quadtree<T>::subdivide() {     Point qSize = Point(boundary.halfSize.x, boundary.halfSize.y);     Point qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y - qSize.y);     nw = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y - qSize.y);     ne = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y + qSize.y);     sw = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y + qSize.y);     se = new Quadtree(AABB(qCentre, qSize)); }  template <class T> bool Quadtree<T>::insert(Data<T> d) {     if(!boundary.contains(d.pos))     {         return false;     }      if(objects.size() < CAPACITY)     {         objects.push_back(d);         return true;     }      if(nw == NULL)     {         subdivide();     }      if(nw->insert(d))     {         return true;     }     if(ne->insert(d))     {         return true;     }     if(sw->insert(d))     {         return true;     }     if(se->insert(d))     {         return true;     }      return false;    }  template <class T> std::vector< Data<T> > Quadtree<T>::queryRange(AABB range) {     std::vector< Data<T> > pInRange = std::vector< Data<T> >();      if(!boundary.intersects(range))     {         return pInRange;     }      for(int i = 0; i < objects.size(); i++)     {         if(range.contains(objects.at(i).pos))         {             pInRange.push_back(objects.at(i));         }     }      if(nw == NULL)     {         return pInRange;    }      std::vector< Data<T> > temp = nw->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = ne->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = sw->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = se->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      return pInRange; } #endif   

No estoy particularmente feliz de definir CAPACITY como yo, Poner const int CAPACITY = 4; en el encabezado sería mucho mejor que tenerlo dos veces, pero la inicialización en las declaraciones de clase es C ++ 14, ¿verdad?

Original en ingles

I've implemented a quadtree in C++. Ignore any apparent similarity to the pseudocode on Wikipedia, it's all in your head, I swear.

How can I improve it? Algorithm speed/space improvements, any extra functions that I'm likely to want... as well as general practice.

#ifndef _QUADTREE_H_ #define _QUADTREE_H_  #include <vector> #include <iostream>  struct Point {     float x, y;     Point(float x = 0, float y = 0):x(x), y(y){}; };  struct AABB {     Point centre;     Point halfSize;      AABB(Point centre = Point(), Point halfSize = Point()): centre(centre), halfSize(halfSize){};      bool contains(Point a)     {         if(a.x < centre.x + halfSize.x && a.x > centre.x - halfSize.x)         {             if(a.y < centre.y + halfSize.y && a.y > centre.y - halfSize.y)             {                 return true;             }         }         return false;     }      bool intersects(AABB other)     {         //this right > that left                                          this left <s that right         if(centre.x + halfSize.x > other.centre.x - other.halfSize.x || centre.x - halfSize.x < other.centre.x + other.halfSize.x)         {         // This bottom > that top             if(centre.y + halfSize.y > other.centre.y - other.halfSize.y || centre.y - halfSize.y < other.centre.y + other.halfSize.y)             {                 return true;             }         }         return false;     } };  template <typename T> struct Data {     Point pos;     T* load;      Data(Point pos = Point(), T* data = NULL): pos(pos), load(data){}; };   template <class T> class Quadtree {     private:         //4 children         Quadtree* nw;         Quadtree* ne;         Quadtree* sw;         Quadtree* se;          AABB boundary;          std::vector< Data<T> > objects;          int CAPACITY;            public:         Quadtree<T>();         Quadtree<T>(AABB boundary);          ~Quadtree();          bool insert(Data<T> d);         void subdivide();         std::vector< Data<T> > queryRange(AABB range); };  template <class T> Quadtree<T>::Quadtree() {     CAPACITY = 4;     nw = NULL;     ne = NULL;     sw = NULL;     se = NULL;     boundary = AABB();     objects = std::vector< Data<T> >(); }  template <class T> Quadtree<T>::Quadtree(AABB boundary) {     objects = std::vector< Data<T> >();     CAPACITY = 4;     nw = NULL;     ne = NULL;     sw = NULL;     se = NULL;     this->boundary = boundary; }  template <class T> Quadtree<T>::~Quadtree() {     delete nw;     delete sw;     delete ne;     delete se; }  template <class T> void Quadtree<T>::subdivide() {     Point qSize = Point(boundary.halfSize.x, boundary.halfSize.y);     Point qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y - qSize.y);     nw = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y - qSize.y);     ne = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y + qSize.y);     sw = new Quadtree(AABB(qCentre, qSize));      qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y + qSize.y);     se = new Quadtree(AABB(qCentre, qSize)); }  template <class T> bool Quadtree<T>::insert(Data<T> d) {     if(!boundary.contains(d.pos))     {         return false;     }      if(objects.size() < CAPACITY)     {         objects.push_back(d);         return true;     }      if(nw == NULL)     {         subdivide();     }      if(nw->insert(d))     {         return true;     }     if(ne->insert(d))     {         return true;     }     if(sw->insert(d))     {         return true;     }     if(se->insert(d))     {         return true;     }      return false;    }  template <class T> std::vector< Data<T> > Quadtree<T>::queryRange(AABB range) {     std::vector< Data<T> > pInRange = std::vector< Data<T> >();      if(!boundary.intersects(range))     {         return pInRange;     }      for(int i = 0; i < objects.size(); i++)     {         if(range.contains(objects.at(i).pos))         {             pInRange.push_back(objects.at(i));         }     }      if(nw == NULL)     {         return pInRange;    }      std::vector< Data<T> > temp = nw->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = ne->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = sw->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      temp = se->queryRange(range);     pInRange.insert(pInRange.end(), temp.begin(), temp.end());      return pInRange; } #endif 

I'm not particularly happy about defining CAPACITY like I do, putting const int CAPACITY = 4; in the header would be much nicer than having it twice, but initialising in class declarations is C++14, right?

           
         
         

Lista de respuestas

20
 
vote
vote
La mejor respuesta
 

OK, así que aquí vamos por algunos consejos:

  • Varios métodos como AABB::contains y AABB::intersects1 No modifique la instancia AABB en el que se llaman. Por lo tanto, debe const3 : Califique estos métodos para asegurarse de que también puedan llamarse en un contexto 99887766655444334 .

      bool intersects(AABB other) const { /* ... */ }                             ^^^^^   
  • Como lo señaló @Glampert en los comentarios, un 99887776655544336 WHEISTAS CUATRO float S, por lo que se está volviendo bastante pesado en comparación con un tipo incorporado. Por lo tanto, cuando lo pasa a una función, es posible que desee pasarlo por const en lugar de pasarlo por valor si solo planea leerlo sin modificarlo:

      bool intersects(const AABB& other) const { /* ... */ }                 ^^^^^     ^   
  • AABB::intersects0 comienza con un subrayado seguido de una letra mayúscula. Por lo tanto, es un identificador reservado para la implementación. Para solucionar esto, lo más sencillo que debe hacer es eliminar el guión guía y use lo más guía AABB::intersects1 en su lugar.

  • Donde sea posible (sugerencia: siempre), use AABB::intersects2 en lugar de AABB::intersects3 para evitar problemas de sobrecarga sutiles y complicados.

  • de C ++ 11 en adelante, puede escribir AABB::intersects4 en lugar de AABB::intersects5 Para inicializar de forma predeterminal el AABB::intersects6 . Es Terser e incurre menos cambios si alguna vez desea cambiar el nombre de la clase.

  • También puede colocar el nombre de la clase cuando declara e inicialice a la vez gracias a la inicialización uniforme de C ++ 11:

      AABB::intersects7  

    Tenga en cuenta que en este caso, lo que realmente desea escribir es probablemente esto:

      AABB::intersects8  

    Como una nota de tamaño, si necesita hacer más AABB::intersects9 / AABB020 Arithmetics, usted es mejor que implemente las clases completas y sobrecargue a los operadores para obtener la legibilidad y evitar tener Para escribir todo, coordinada por coordenada cada vez que necesita realizar una operación simple.

  • Si AABB1 nunca está destinado a cambiar, podría hacerlo una variable de miembro 998877766554433222254433222. Además, no usaría AABB3 por su nombre, que es un caso que generalmente usamos para denotar el uso de macros.

      AABB4  
  • Intente usar la lista de inicialización del constructor cuando puede, de modo que el compilador no tenga que asignar valores a la variable después de el objeto está construido:

      AABB5  

    No tiene que inicializar explícitamente los otros parámetros, ya que se inicializarán de forma predeterminada, de todos modos, si no escribe nada.

  • Usted tiene un LOOP con iteración basada en índices aquí:

      AABB7  

    Estoy seguro de que le gustará el Loop:

    loup: le gustará el bucle AABB9

    Oye, es Terser y ya no tiene que temer errores de iteración fuera de uno :)

  • Además, se preguntó si el inicializador en clase era C ++ 14. Buenas noticias, son disponibles en C ++ 11. Estaban solo un poco mejorados para cubrir casos más oscuros en C ++ 14, por lo que puede escribir totalmente su clase de la clase como esta:

      const1  

    El constructor usará los inicializadores en clase para inicializar la estructura. Tenga en cuenta que cambié const2 a const3 que es el literal correcto para const4 . Si bien los literales correctos generalmente no son tan relevantes, lo que los consigue correctamente se vuelve cada vez más importante en un mundo de C ++ de deducción de tipo.

 

Ok, so here we go for a few tips:

  • Several methods such as AABB::contains and AABB::intersects do not modify the AABB instance they are called with. Therefore, you should const-qualify these methods to make sure that they can also be called in a const context.

    bool intersects(AABB other) const { /* ... */ }                             ^^^^^ 
  • As pointed by @glampert in the comments, an AABB instance wheights four floats, so it's becoming quite heavy compared to a built-in type. Therefore, when you pass it to a function, you might want to pass it by const reference instead of passing it by value if you only plan to read from it without modifying it:

    bool intersects(const AABB& other) const { /* ... */ }                 ^^^^^     ^ 
  • _QUADTREE_H_ begins with an underscore followed by a capital letter. Therefore, it is an identifier reserved to the implementation. To fix this, the simplest thing to do is to drop the leading underscore and use QUADTREE_H_ instead.

  • Wherever possible (hint: always), use nullptr instead of NULL to avoid subtle and tricky overload problems.

  • From C++11 onward, you can write Point pos = {} instead of Point pos = Point() to default-initialize the Point. It is terser and incurs less changes if you ever want to change the class name.

  • You can also drop the class name when you declare and initialize at once thanks to C++11 uniform initialization:

    Point qSize = { boundary.halfSize.x, boundary.halfSize.y }; 

    Note that in this case, what you actually want to write is probably this:

    Point qSize = boundary.halfSize; 

    As a size note, if you need to do more Point/Vector arithmetics, you better implement the full classes and overload the operators to gain in readability and avoid having to write everything coordinate-by-coordinate everytime you need to perform a simple operation.

  • If CAPACITY is never meant to change, you could make it a static constexpr member variable. Also, I wouldn't use ALLCAPS_CASE for its name, which is a case that we generally use to denote the use of macros.

    static constexpr int capacity = 4; 
  • Try to use the constructor initialization list when you can so that the compiler does not have to assign values to variable after the object is constructed:

    template <class T> Quadtree<T>::Quadtree():     nw{nullptr},     ne{nullptr},     sw{nullptr},     se{nullptr} {} 

    You don't have to explicitly default-initialize the other parameters since they will be default-initialized anyway if you don't write anything.

  • You have an old C-style for loop with indices-based iteration here:

    for(int i = 0; i < objects.size(); i++) {     if(range.contains(objects.at(i).pos))     {         pInRange.push_back(objects.at(i));     } } 

    I am sure that you will like the C++11 range-based for loop:

    for(auto&& object: objects) {     if(range.contains(object.pos))     {         pInRange.push_back(object);     } } 

    Hey, it's terser and you don't have to fear off-by-one iteration errors anymore :)

  • Also, you wondered whether in-class initializer were C++14. Good news, they are avaible in C++11. They were only slightly upgraded to cover more obscure cases in C++14, so you can totally write your Point class like this:

    struct Point {     float x = 0.0f;     float y = 0.0f; }; 

    The constructor will then use the in-class initializers to initialize the structure. Note that I changed 0 to 0.0f which is the correct literal for float. While correct literals are generally not that relevant, getting them right becomes more and more important in a type-deducing C++ world.

 
 
         
         
3
 
vote

Creo que los centros que está calculando para los límites de los sub-árboles no coinciden con los nombres de los miembros: por ejemplo, la posición central para NW debe ser de hecho la de SW.

Esto podría ser un problema si agregará optimizaciones para elegir el nodo secundario correcto basado en las posiciones del objeto y los sub-nodos de acuerdo con el centro del árbol principal (y creo que debe hacerlo, por ejemplo, si va usar este quadtree para almacenar objetos geométricos en gráficos de computadora).


, pero no estoy totalmente seguro de eso, pensé que una lógica detrás del quadtree es almacenar datos solo en los nodos de las hojas; Ahora está almacenando parte de los datos en cada nodo y expandiendo el árbol según sea necesario: esto provocaría que las operaciones de búsqueda se ejecuten en cada nodo, lo que complica un poco la lógica para cada una de ellas, y esto podría ser un sub-óptimo solución.

 

I think the centres you are calculating for the boundaries of the sub-trees do not match the member names: for example, the centre position for nw should be in fact the one of sw.

This could be an issue if you will add optimisations for choosing the correct child node based on the object and sub-node positions according to the center of the parent tree (and I think you should do it, e.g. if you are going to use this quadtree to store geometrical objects in computer graphics).


Also, but I'm not totally sure about it, I thought some logic behind the quadTree is to store data only on leaf nodes; now you are storing part of the data in every node, and expanding the tree as needed: this would cause searching operations to be executed in every node, which complicates a bit the logic for each of them, and this could be a sub-optimal solution.

 
 
1
 
vote

Lo siento, estoy tarde a esta fiesta, pero su código es realmente útil para mí, así que lo estoy usando como un comienzo para mi propia; Aquí están mis comentarios sobre el estilo.

  1. No hay necesidad de; después de las funciones. Solo las declaraciones terminan en los puntos comunes.

  2. Al pasar los objetos AABB, que están en el lado grande, considere los parámetros de aprobación por Const & Amp; en lugar de copiar. Es más rápido copiar objetos menos de 3 palabras. Esto es 4 flotadores, es una especie de límite, pero verificaré. Ciertamente, si usa el doble, luego pasa por referencia. 2b. AABB es un nombre extraño. El límite sería mejor.

  3. No retire el código de la clase cuando sea tan corto. El constructor y el destructor son 4 líneas cada una, el código se vuelve más legible y más corta cuando se mantiene en la definición de la clase, y este es el tipo de código donde desea que los innigantes de todos modos.

  4. ¡No pase los datos por valor! Esto es enorme, no tienes idea de lo grande que podría ser. Siempre por referencia cuando no lo sabes.

  5. El más grande hasta ahora que encontré es que en el inserto, está probando NW, NE, SW, SE. ¡Debería comparar su valor y decidir cuál hacerlo sin probarlos a todos!

  6. Puede considerar tener solo un solo cuadro delimitador en la parte superior y computar los límites de cada subd quadtree dinámicamente. Puede ser tan rápido y tomaría un espacio sustancialmente menos.

 

Sorry I am late to this party, but your code is actually useful to me, so I am using it as a start for my own; here are my comments on style.

  1. No need for ; after functions. Only declarations end in semicolons.

  2. When passing AABB objects, which are on the large side, consider passing parameters by const & instead of copying. It is faster to copy objects less than 3 words. This is 4 floats, it is kind of borderline but I will check. Certainly if you use double, then pass by reference. 2b. AABB is a weird name. Boundary would be better.

  3. Do not pull code out of the class when it is so short. The constructor and destructor are 4 lines each, the code becomes more readable and shorter when kept in the class definition, and this is the kind of code where you want those inlined anyway.

  4. Do not pass Data by value!!! This is huge, you have no idea how big T could be. Always by reference when you don't know.

  5. The biggest so far that I found is that in insert, you are testing nw,ne,sw,se. You should be comparing your value and deciding which one to do without trying them all!

  6. You might consider having only a single bounding box at the top and computing the bounds of each sub quadtree dynamically. It might be just as fast and would take substantially less space.

 
 
 
 

Relacionados problema

5  Clase de vectores matemáticas fuertemente planteladas  ( Heavily templated mathematical vector class ) 
Comencé a escribir una biblioteca para el álgebra lineal para uso personal, pero también para la revitilización de mi C ++. A continuación se muestra la pri...

5  Fórmula Haversine en Clojure  ( Haversine formula in clojure ) 
Implementé el fórmula haversine para calcular la distancia entre dos (latitud , longitud) coordenadas. Me preguntaba si se ve natural para los programador...

17  Implementación vectorial (física)  ( Vector physics implementation ) 
Recientemente comencé a aprender Java, y decidí implementar un sistema de vectores básico para otro sistema de partículas que estaba construyendo. join()9 ...

3  Clases NODE2D y NODE3D implementadas utilizando un decorador compartido  ( Node2d and node3d classes implemented using a shared decorator ) 
Editar: He hecho otro Ir a esto usando Metaclasses aquí . Creo que es un enfoque mucho mejor. Tengo las siguientes clases. validator es un decorador que ...

1  Calculadora de vector simple [cerrado]  ( Simple vector calculator ) 
cerrado . Esta pregunta necesita detalles o claridad . Actualmente no está aceptando respuestas. ...

1  Funciones de comparación para 2D puntos [cerrados]  ( Comparison functions for 2d points ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

14  Comparación con el infinito al verificar si un punto está por encima de una línea  ( Comparison to infinity when checking if a point is above a line ) 
Tengo una función que se llama en un bucle apretado. He perfilado mi código y aquí es donde está mi cuello de botella más grande. La función es bastante simpl...

4  Implementación de Quadtree C ++  ( Quadtree c implementation ) 
Recientemente creé una implementación de Quadtree en C ++. Varía ligeramente de la mayoría de las implementaciones. En lugar de almacenar elementos, solo or...

21  Conversión de coordenadas polares a coordenadas rectangulares  ( Converting from polar coordinates to rectangular coordinates ) 
Este es un rendimiento crítico. Medí y determiné que el uso de 99887766655443319 es más rápido que usar el método 99887766655443320 . Soy consciente de q...

10  Encuentra el hogar visible no visible más cercano  ( Find the closest unvisited visible home ) 
Estoy escribiendo un juego más alto de 2D donde realizo una gran cantidad de búsquedas "más cercanas" entre un punto y todo el resto de los puntos. En este ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos