Algorithmus, um Eltern vor Kindern zu sortieren

Question

Ich schreibe eine Zeichenanwendung, die Formen enthält, die Kinder haben können. Wenn ich die Leinwand neu zeichnen muss, möchte ich die Formen sortieren, um zu zeichnen, damit die Eltern vor ihren Kindern erscheinen. Auf diese Weise wird eine Elternform nicht über eine Kinderform gezeichnet. Hier ist die relevante Funktion (geschrieben in JavaScript). Variablen, die vorangestellt sind my. sind Instanzvariablen. my.draw_order ist eine Reihe von Formindizes, die neu gezeichnet werden müssen (durch den Code unten besiedelt). my.ctx ist der HTML -Canvas -Kontext, in dem die Formen gezeichnet werden, my.shapes ist eine Reihe von Formen in willkürlicher Reihenfolge, my.update_rects ist eine Reihe von schmutzigen Rechtecken, die optional von einer sehr großen Form verwendet werden können, um nur eine teilweise Neuausrichtung durchzuführen.

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

Meine Frage ist: Was ist der beste Weg, um Shape_Sort zu implementieren, wie im Code verwiesen wird? Dies ist eine Routine, die oft als als Effizienz eingestuft wird. Jede Form hat eine übergeordnete Eigenschaft, die einen Verweis auf die Form seines Elternteils enthält. Vorschläge für ein besseres Design sind willkommen. Aufrechterhaltung der my.shapes Array in sortierter Reihenfolge ist eine unerwünschte Option.

Answer 1

Ich würde die Formen als Baum aufrechterhalten. Erstellen Sie eine einzelne Wurzel (die den gesamten Bildschirm darstellen) und geben Sie den Eltern ihren Kindern Zeiger. Dann würde eine einfache Vorbestellung des Baumes ausreichen.

Um in Bezug auf Ihr vorhandenes Design zu implementieren, müssen Sie die nicht abgeben my.shapes Array. Fügen Sie einfach a hinzu my.root, Fügen Sie Zeiger von den Eltern zu Kindern hinzu und durchqueren:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}

Answer 2

Wenn Sie Datenstrukturen benötigen, die komplexer sind als Bäume, sollten Sie a überprüfen Topologische Art Algorithmus.