es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Tratando de encontrar nodos hoja en un Quadtree (C++)

30 Jul, 2023 Programación

Estoy haciendo un Quadtree en C++. Necesito encontrar los nodos hoja del árbol. Para hacer esto, tengo esta función que debe devolver un vector de los nodos hoja. Por ahora, todo lo demás parece funcionar, pero esta función no y no entiendo por qué.

vector<quadtree*> find_leaves(QuadTree* quad, vector<quadtree*>& list_of_leaves) {

    if (quad->is_leaf) {
        list_of_leaves.push_back(quad);
    }

    else {
        for (int i = 0; i < 4; i++) {
            find_leaves(quad->children[i], list_of_leaves);
        }
    }
    return list_of_leaves;
}

Antes de hacerlo en C++, lo hice en Python (que conozco mucho mejor). Esta función hace lo mismo pero en Python y funciona perfectamente:

def find_leaves(quad, list_of_leaves = []):

    if quad.is_leaf:
        list_of_leaves.append(quad)

    else:
        for i in quad.children:
            find_leaves(i, list_of_leaves)

    return list_of_leaves

En ambos códigos, quad es un nodo del árbol. ¿Alguien ve dónde está el error o alguien conoce otra manera de encontrar los nodos hoja en un Quadtree? Gracias por tu ayuda.</quadtree></quadtree>

Tags:  , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Un posible problema con el código de C++ podría ser que el vector de nodos hoja no se esté pasando por referencia correctamente, lo que conduce a un comportamiento inesperado. Para solucionar esto, la firma de la función debería actualizarse a:

    “`c++
    void find_leaves(QuadTree* quad, vector<quadtree*>& list_of_leaves);


    Además, la función se podría modificar para evitar devolver el vector y, en su lugar, pasarlo como parámetro de referencia. Esto mejoraría el rendimiento al evitar copias innecesarias del vector:

```c++
void find_leaves(QuadTree* quad, vector<quadtree*>& list_of_leaves) {
    if (quad->is_leaf) {
        list_of_leaves.push_back(quad);
    }
    else {
        for (int i = 0; i < 4; i++) {
            find_leaves(quad->children[i], list_of_leaves);
        }
    }
}

    Otra posible solución para encontrar los nodos hoja de un QuadTree es realizar un recorrido en profundidad, comprobando si cada nodo es una hoja o no. Esto se puede implementar de la siguiente manera:

    “`c++
    void find_leaves(QuadTree* quad, vector<quadtree>& list_of_leaves) {
    // Realizar recorrido en profundidad
    stack<quadtree    > nodes_stack;
    nodes_stack.push(quad);

    while (!nodes_stack.empty()) {
    QuadTree* current = nodes_stack.top();
    nodes_stack.pop();

    if (current->is_leaf) {
        list_of_leaves.push_back(current);
    }
    else {
        for (int i = 3; i >= 0; i--) { // Recorrer los hijos en orden inverso para mantener el orden espacial correcto
            if (current->children[i] != nullptr) {
                nodes_stack.push(current->children[i]);
            }
        }
    }
}

    }
    “`

    Esta implementación utiliza una pila para realizar un recorrido en profundidad del árbol, comprobando cada nodo para ver si es una hoja. En este caso, los nodos hoja se añaden directamente al vector de salida.</quadtree></quadtree></quadtree></quadtree>

Comments are closed.