Algorithme pour trier les parents avant les enfants

Question

J'écris une application de dessin qui comprend des formes pouvant avoir des enfants. Lorsque j'ai besoin de redessiner la toile, j'aimerais trier les formes à dessiner afin que les parents apparaissent devant leurs enfants. De cette façon, une forme parent ne sera pas dessinée sur une forme enfant. Voici la fonction pertinente (écrite en JavaScript). Les variables précédées de my. sont des variables d'instance. my.draw_order est un tableau d'index de formes à redessiner (renseigné par le code ci-dessous), my.ctx est le contexte du canevas HTML dans lequel les formes sont dessinées. my.shapes est un tableau de formes dans un ordre arbitraire, my.update_rects est un tableau de rectangles sales qui peuvent éventuellement être utilisés par une très grande forme. redessin partiel.

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;
};

Ma question est la suivante: quel est le meilleur moyen d'implémenter shape_sort tel que référencé par le code? C’est une routine que l’on appellera souvent. L’efficacité peut donc être un problème. Chaque forme a une propriété parent qui contient une référence à la forme de son parent. Les suggestions pour un meilleur design sont les bienvenues. Conserver le tableau my.shapes dans un ordre trié est une option indésirable.

Answer 1

Je voudrais maintenir les formes comme un arbre. Créez une seule racine (représentant tout l'écran) et donnez aux parents des pointeurs sur leurs enfants. Ensuite, une simple traversée de l’arbre en préordre suffirait.

Pour mettre en œuvre votre conception existante, vous n'avez pas besoin de supprimer le tableau my.shapes . Ajoutez simplement un my.root , ajoutez des pointeurs des parents aux enfants et parcourez:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}

Answer 2

Si vous avez besoin de structures de données plus complexes que les arborescences, vous devez vérifier le Tri topologique algorithme.