Algoritmo para ordenar padres antes que hijos

Question

Estoy escribiendo una aplicación de dibujo que incluye formas que pueden tener hijos. Cuando necesito volver a dibujar el lienzo, me gustaría ordenar las formas para dibujar para que los padres aparezcan antes que sus hijos. De esa manera, una figura principal no se dibujará encima de una figura secundaria. Aquí está la función relevante (escrita en JavaScript). Las variables con el prefijo my. son variables de instancia. my.draw_order es una matriz de índices de formas que se deben volver a dibujar (con el siguiente código), my.ctx es el contexto del lienzo HTML donde se dibujan las formas, my.shapes es una matriz de formas en un orden arbitrario, my.update_rects es una matriz de rectángulos sucios que pueden ser utilizados opcionalmente por una forma muy grande para hacer solo un redibujo parcial.

redraw = function () {
    var i, shape_count, shape;

    shape_count = 0;
    for (i = 0; i < my.shapes.length; i++) {
        shape = my.shapes[i];

        if (shape.visible && shape.dirty) {
            my.draw_order[shape_count] = i;
            shape_count++;
        }
    }

    my.draw_order.length = shape_count;

    // sort shapes to draw so that parents appear before children ???
    my.draw_order.sort(shape_sort);

    for (i = 0; i < my.draw_order.length; i++) {
        shape = my.shapes[my.draw_order[i]];

        shape.draw(my.ctx, my.update_rects);
        shape.dirty = false;
    }

    my.update_rects.length = 0;
};

Mi pregunta es: ¿cuál es la mejor manera de implementar shape_sort como se menciona en el código? Esta es una rutina que se llamará con frecuencia, por lo que la eficiencia puede ser una preocupación. Cada forma tiene una propiedad padre que contiene una referencia a la forma de su padre. Sugerencias para un mejor diseño son bienvenidas. Mantener la matriz my.shapes en orden es una opción indeseable.

Answer 1

Mantendría las formas como un árbol. Cree una única raíz (que represente toda la pantalla) y proporcione a los padres punteros a sus hijos. Entonces sería suficiente un simple recorrido previo del pedido del árbol.

Para implementar en términos de su diseño existente, no necesita deshacerse de la matriz my.shapes . Simplemente agregue un my.root , agregue punteros de padres a hijos y recorra:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

    for (child in root.children) {
        preorder_draw(child);
    }

}

Answer 2

Si necesita estructuras de datos que sean más complejas que los árboles, debe verificar un Clasificación topológica algoritmo.