Круговое представление древовидной структуры

Question

У меня есть некоторые данные в древовидной структуре, и я хочу представить их графически, с корневым узлом в середине сцены, его дети смещены по кругу вокруг него и так далее для каждого ребенка, вокруг их родителей. Я не хочу перекрывающихся узлов, поэтому вопрос в том, как расположить пространство оптимальным образом. Что-то меньше или больше, например (найдено через Google)

Какие алгоритмы мне нужно искать, чтобы понять что-то подобное?

Answer 1

Вы можете сделать это в срочном порядке, настроив систему, в которой каждый узел дерева пытается сохранить как можно большее расстояние от всех других узлов (кроме родительского), но как можно меньшее расстояние от родителя (вниз на какое-то минимальное расстояние, которое он должен выдерживать). Если вы будете запускать этот алгоритм для каждого узла несколько раз, пока он не стабилизируется, у вас будет механизм, подобный тому, который вы описали. Я уверен, что вы можете сделать много оптимизаций, но я уверен, что это будет самый простой подход. Попытка рассчитать весь макет заранее будет очень сложной ...

Answer 2

Если вас не волнует как это сделано, а только то, что вы визуализируете данные, взгляните на graphviz радиальное расположение . Хотя пример выглядит не совсем так, как вам нужно, вам нужен макет. Это также даст вам некоторые идеи о том, как это делается с большим количеством исследовательских работ. Удачи!

Вы также можете увидеть, как легко развернуть эту бумагу в круглую структуру.

Answer 3

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

Другим подходом было бы отказаться от физического моделирования и просто построить его итеративно. Я делал нечто подобное на прошлой неделе, но мои деревья, вероятно, намного менее вовлечены, чем ваши.

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

Вот мой основной алгоритм:

1) Изучите все древовидные данные и найдите все узлы листьев. 2) пока вы делаете это, не забудьте измерить длину каждой ветвящейся структуры, чтобы вы знали, какая из них самая длинная. 3) как только у вас будут все ваши листовые узлы, распределите их поровну по концентрической окружности. Вы можете использовать либо весь круг, либо только некоторую часть области углов. 4) как только все листовые узлы были решены, вы снова проходите по дереву, проходя снаружи внутрь. Каждый встреченный вами узел, который не является листовым, нуждается в компоновке. По сути, каждый узел с этого момента имеет угол, который является средним значением всех его дочерних узлов, а смещение представляет собой graph_radius * (deep_of_node / maximum_depth)

Я обнаружил, что это дает мне очень приличный и понятный человеку дистрибутив, хотя и не очень эффективный с точки зрения использования экрана. Я загрузил анимацию моего дерева здесь: GIF anim

Answer 4

Вы пытаетесь нарисовать плоское представление графика. Найдите модные слова и, возможно, ресурс здесь А в википедии

А, и я забыл: вы можете сделать это ньютоновским путем с помощью сил. Просто дайте всем узлам отталкивающий потенциал, например, сделайте их протонами, которые отталкивают друг друга. Придайте ребрам свойства ньютоновских пружин, прилагая усилия, которые сближают их, и все готово. Можно даже создать хорошую анимацию таким образом. Это также официальный способ рисования графиков, но я не знаю названия.