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

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算法。