Algoritmo para classificar os pais antes dos filhos

Question

Estou escrevendo um aplicativo de desenho que inclui formas que podem ter filhos.Quando preciso redesenhar a tela, gostaria de ordenar as formas a serem desenhadas para que os pais apareçam diante dos filhos.Dessa forma, uma forma pai não será desenhada sobre uma forma filha.Aqui está a função relevante (escrita em JavaScript).Variáveis ​​prefixadas com my. são variáveis ​​de instância. my.draw_order é uma matriz de índices de formas que precisam ser redesenhados (preenchidos pelo código abaixo), my.ctx é o contexto da tela HTML onde as formas são desenhadas, my.shapes é uma matriz de formas em uma ordem arbitrária, my.update_rects é uma matriz de retângulos sujos que pode opcionalmente ser usado por uma forma muito grande para fazer apenas um redesenho 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;
};

Minha pergunta é:qual é a melhor maneira de implementar shape_sort conforme referenciado pelo código?Esta é uma rotina que será chamada com frequência, portanto a eficiência pode ser uma preocupação.Cada forma possui uma propriedade pai que contém uma referência à forma pai.Sugestões para um design melhor são bem-vindas.Mantendo o my.shapes array em ordem classificada é uma opção indesejável.

Answer 1

Eu manteria as formas de uma árvore.Crie uma única raiz (representando a tela inteira) e dê dicas aos pais para seus filhos.Então, um simples percurso de pré-encomenda da árvore seria suficiente.

Para implementar em termos de seu design existente, você não precisa abandonar o my.shapes variedade.Basta adicionar um my.root, adicione ponteiros de pais para filhos e percorra:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}

Answer 2

Se você precisar de estruturas de dados mais complexas que árvores, verifique um Classificação topológica algoritmo.