Алгоритм сортировки родителей перед детьми

StackOverflow https://stackoverflow.com/questions/1627389

  •  06-07-2019
  •  | 
  •  

Вопрос

Я пишу приложение для рисования, которое включает фигуры, которые могут иметь детей. Когда мне нужно перерисовать холст, я бы хотел отсортировать фигуры так, чтобы родители появлялись перед своими детьми. Таким образом, родительская фигура не будет рисоваться поверх дочерней фигуры. Вот соответствующая функция (написана на 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 в отсортированном порядке является нежелательным вариантом.

Это было полезно?

Решение

Я бы поддерживал формы в виде дерева. Создайте единый корень (представляющий весь экран) и присвойте родителям указатели своим детям. Тогда достаточно простого обхода дерева по предзаказу.

Для реализации с точки зрения существующего дизайна вам не нужно отбрасывать массив my.shapes . Просто добавьте my.root , добавьте указатели от родителей на детей и пройдите: 

function preorder_draw(root) {

    //do stuff with root
    draw(root);

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

}

Другие советы

Если вам требуются структуры данных, которые являются более сложными, чем деревья, вам следует проверить Топологическую сортировку алгоритм.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top