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

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

如果您需要比树木更复杂的数据结构，你应该检查Topological Sort算法。