在孩子面前为父母排序的算法

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

我会将形状保持为树状。创建一个根（代表整个屏幕），并给父母指点他们的孩子。然后一个简单的前序遍历树就足够了。

要根据现有设计实现，您不需要抛弃 my.shapes 数组。只需添加 my.root ，添加从父项到子项的指针，然后遍历：

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}

Answer 2

如果您需要比树更复杂的数据结构，则应检查拓扑排序算法。