Алгоритм эффективного рисования деревьев? - PullRequest
Новая
       19

Алгоритм эффективного рисования деревьев?

11 голосов
/ 28 ноября 2011

Мне нужно нарисовать дерево корпоративной структуры (вроде семейного древа) в C #. Весь вспомогательный код там. Это цветной, интерактивный и модный. Единственная проблема в том, что алгоритм, который на самом деле решает, куда поместить каждый узел, доставляет мне много горя.

На данный момент ящики имеют размер 100x50, и у меня есть класс под названием StaffNode, который представляет сотрудника с определенной координатой x, y.

Алгоритм просто должен создать List<StaffNode> с соответствующими x и y.

Это невероятно сложно.

По сути, алгоритм является рекурсивным по корпоративной структуре, поэтому слева -> вправо, затем сверху вниз - вдоль дерева. Очевидно, что это плохо, если два узла находятся друг над другом.

Я могу придумать несколько алгоритмов, которые могут выдавать что-то вроде этого: 

          *
    o         O
o o o o o     O
o         O O O O O
                O

Тогда как что-то подобное было бы лучше, так как дерево очень большое и пространство очень ограничено: 

       *
    o     O
o o o o o O
o     O O O O O
            O

Кто-нибудь из вас раньше рисовал такое дерево? Если у вас есть, я уверен, что вы столкнулись со многими препятствиями, которые у меня есть. Какие-нибудь советы? Пока я потратил на это целый день.

Ответы [ 2 ]

15 голосов
/ 28 ноября 2011

Существует много хороших алгоритмов для рисования деревьев, каждый из которых демонстрирует свое свойство деревьев. Если вы хотите показать иерархию, есть этот код для WPF, который рисует иерархии . Для более общего обсуждения того, как рисовать графики и деревья, рассмотрим на этих слайдах лекции , подробно описывающих многие из таких алгоритмов. Также есть эти превосходные слайды , покрывающие аналогичный материал.

Надеюсь, это поможет!

1 голос
/ 28 ноября 2011

Вы можете использовать итеративный подход. Разложите дерево, как в первом примере, который вы использовали выше. Затем переместите узлы или поддеревья ближе друг к другу, следя за тем, чтобы не нарушались никакие ограничения (например, узлы не могут перекрываться, дочерние узлы должны быть ниже родительских узлов).

Плюсы:

  • Простой алгоритм.
  • Получает достаточно хорошее решение.
  • Может непрерывно применяться к изменяющемуся дереву.
  • Можно заставить выглядеть круто.

Минусы:

  • Может потребоваться много итераций, чтобы хорошо выглядеть.
  • Может не найти оптимального решения (попадает в локальный максимум)
...