자녀 앞에서 부모를 분류하는 알고리즘

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

나무보다 더 복잡한 데이터 구조가 필요하면 토폴로지 정렬 연산.