#algorithm #data-structures #graphics #tree #visualization
#алгоритм #структуры данных #графика #дерево #визуализация
Вопрос:
У меня есть произвольная древовидная структура узлов. Я хочу нарисовать это дерево, чтобы предоставить пользователям визуальное представление. Мне нужно выполнить рекурсию по дереву и для каждого узла добавить графический элемент в список, а затем просто нарисовать список элементов после завершения рекурсии дерева. Рекурсия и рисование элементов, конечно, тривиальны — что немного сложнее, так это как расположить графические узлы, чтобы они не перекрывались с другими ветвями.
Я использую Android, но это не важно — я ищу подход, возможно, алгоритм, который может поддерживать изображение 2D-пространства при прохождении по дереву, чтобы он просто выделял наиболее подходящие координаты для каждого узла при прохождении.
Есть идеи?
Обновить
Ответ №1:
Я бы попробовал алгоритм Walker. Вот академическая статья об алгоритме. Если вы хотите просмотреть код, посмотрите на NodeLinkTreeLayout в Prefuse. Prefuse имеет открытый исходный код, поэтому проблем с адаптацией кода к вашей ситуации возникнуть не должно, если вы соблюдаете условия лицензии.
Комментарии:
1. в конце я использовал версию Walker от Buchhiem. Спасибо
Ответ №2:
Я предлагаю нарисовать дерево линейно. Вы делаете это с помощью какого-то движущегося «курсора рисования».
Вы могли бы сохранить атрибут width для каждого узла, который вычисляется следующим образом:
widthзначение leave равно 1widthвнутреннего узла — это сумма всех дочернихwidthузлов
Затем вы рисуете корень «в первой строке» посередине, что означает, что вы просто берете width половину корня.
Затем вы создаете сетку поверх изображения таким образом, чтобы каждая линия сетки соответствовала одной строке соответственно. один шаг слева направо, и каждое пересечение линий сетки может содержать узел, и на каждом узле достаточно места.
Затем вы выполняете итерацию по дочерним элементам, и во время итерации вы накапливаете дочерние width элементы и рисуете дочерние элементы «в следующей строке». Чтобы нарисовать currentChild , вы перемещаете курсор рисования currentWidth/2 вправо, рисуете currentChild и перемещаете курсор рисования на оставшуюся часть currentWidth/2 вправо.
Чтобы расположить узлы в правильном порядке, вы могли бы рассмотреть поиск в ширину.
Я надеюсь, что мое объяснение понятно, но я думаю, будет лучше, если я нарисую небольшую картинку.
Это наше дерево ( x это узлы, все остальное ребра)
-------x-- -------
| | |
-x- - x - -x-
| | | | | | | | |
x x x x x x x x x
Итак, вы вычисляете width s листа:
-------x-- -------
| | |
-x- - x - -x-
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Затем, снизу вверх, width s как суммы дочерних width s:
-------9-- -------
| | |
-2- - 4 - -3-
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Итак, вы начинаете с корня ( width 9) и переходите на 4,5 шага к rigt в первой строке.
Затем вы перемещаете свой «курсор рисования» на вторую строку, «столбец 0» (перейдите влево).
У первого дочернего элемента есть width 2, поэтому мы идем 2/2=1 по линиям сетки вправо и рисуем узел, а затем перемещаем курсор рисования на оставшиеся 1 линию сетки вправо, чтобы закончить узел. Итак, следующий узел имеет width 4, что означает, что мы идем вправо 4/2 = 2 линии сетки, рисуем, проходим оставшиеся 2 шага и так далее.
И так далее со следующей строкой. В конце (или на промежуточных этапах) соедините узлы.
Эта процедура гарантирует отсутствие перекрывающихся узлов (если линии сетки находятся достаточно далеко друг от друга), но это может привести к созданию довольно больших древовидных диаграмм, которые могли бы использовать пространство более эффективно.
Чтобы обнаружить неиспользуемое пространство, можно просто просканировать строки после описанного выше процесса и посмотреть, есть ли неиспользуемые пересечения линий сетки, а затем, возможно, перестроить некоторые узлы, чтобы заполнить пространство.
Комментарии:
1. это то, что я придумал, хотя это усложняется, когда ветви многоуровневые, и вам приходится выполнять рекурсию до самого низа всех из них, прежде чем вы сможете определить, как они взаимодействуют друг с другом. спасибо за ответ, высоко ценится.
2. что произойдет, если нижний лист находится в самой правой части дерева? Как в вашем примере, если бы у одного из узлов шириной 1 был другой дочерний элемент — тогда узел был бы нарисован слева, справа? Я имею в виду, что она имела бы ширину 1, поэтому 1/2 = .5 и была бы размещена в левой части дерева… что было бы неправильно. Как бы ваш алгоритм справился с этим случаем?
Ответ №3:
Взгляните на точку. Вы можете преобразовать свое дерево в точечное представление, а затем с помощью Graphviz визуализировать в любом формате, который вам нравится. Например, Doxygen использует ее для представления структуры программы.
Комментарии:
1. Спасибо, хотя Grpahviz не будет работать на Android, так что на самом деле это не так уж сильно помогает : (
2. @flesh, ты сказал «Я использую Android, но это не важно». Теперь вы говорите, что если это не работает на Anroid, это не так уж сильно помогает?
3. Ларш — Я сказал, что это не важно, потому что я искал теоретический подход или алгоритм, а не библиотеку. Вы предложили библиотеку или, по крайней мере, язык, для анализа которого требуется библиотека, но, похоже, ни один из них не работает на Android. Однако я ценю ваше предложение 🙂
Ответ №4:
Graphviz и mfgraph являются мощными, но они предназначены для общих графиков и, вероятно, излишни для деревьев.
Попробуйте погуглить tree layout algorithm или посмотреть Графическое дерево Javascript с Layout. Последний старый, но он использует HTML canvas и javascript и объясняет код, поэтому и код, и подход должны быть переносимыми.
Ответ №5:
В зависимости от характера ваших данных, TreeMap может быть более подходящим, чем представление tinkertoy.