아이들 전에 부모를 정렬하는 알고리즘

Question

아이들을 가질 수있는 도형이 포함 된 그리기 응용 프로그램을 작성하고 있습니다. 캔버스를 다시 그려야 할 때 부모님이 자녀보다 먼저 나타나도록 그릴 모양을 정렬하고 싶습니다. 이렇게하면 부모 모양이 자식 모양 위에 그려지지 않습니다. 다음은 관련 함수 (JavaScript로 작성)입니다. my. 접두사가 붙은 변수는 인스턴스 변수입니다. my.draw_order은 모양을 그려야하는 HTML 캔버스 컨텍스트 인 my.ctx은 다시 그려야하는 모양 인덱스 배열이며 my.ctx은 모양이 그려지는 HTML 캔버스 컨텍스트이며 은 더러운 사각형 배열입니다. 부분 그리기 만하기 위해 매우 큰 모양으로 선택적으로 사용할 수 있습니다.

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 어레이를 도랑에 집어 넣을 필요가 없습니다.

function preorder_draw(root) { 

    //do stuff with root 
    draw(root); 

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

} 

Answer 2

당신은 나무보다 더 복잡한 데이터 구조를 필요로, 당신이 Topological Sort 알고리즘을 확인해야할까요 : 그냥하는 my.root를 추가 부모에게서 자녀에게 포인터를 추가하고, 트래버스.