Алгоритм сортировки родителей перед детьми

Question

Я пишу приложение для рисования, которое включает фигуры, которые могут иметь детей. Когда мне нужно перерисовать холст, я бы хотел отсортировать фигуры так, чтобы родители появлялись перед своими детьми. Таким образом, родительская фигура не будет рисоваться поверх дочерней фигуры. Вот соответствующая функция (написана на JavaScript). Переменные с префиксом my. являются переменными экземпляра. my.draw_order - это массив индексов фигур, которые необходимо перерисовать (заполняется приведенным ниже кодом), my.ctx - это контекст HTML-холста, в котором рисуются фигуры, my.shapes - это массив фигур в произвольном порядке, my.update_rects - это массив грязных прямоугольников, который может использоваться очень большой формой, чтобы сделать только частичное перерисовывание.

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

Мой вопрос: каков наилучший способ реализации shape_sort, на который ссылается код? Это процедура, которая будет часто вызываться, поэтому эффективность может быть проблемой. Каждая форма имеет родительское свойство, которое содержит ссылку на форму своего родителя. Предложения по улучшению дизайна приветствуются. Поддержание массива my.shapes в отсортированном порядке является нежелательным вариантом.

Answer 1

Если вам требуются структуры данных, более сложные, чем деревья, вам следует проверить алгоритм Topological Sort .

Answer 2

Я бы поддерживал формы как дерево. Создайте единый корень (представляющий весь экран) и присвойте родителям указатели своим детям. Тогда достаточно простого обхода дерева по предзаказу.

Для реализации с точки зрения существующего дизайна вам не нужно отбрасывать массив my.shapes. Просто добавьте my.root, добавьте указатели от родителей на детей и пройдите:

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}