Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Выравнивание и центрирование дерева по ширине

Выравнивание и центрирование дерева по ширине

Поделиться
2pizzaПостоялецwww11 ноя. 201718:58#0
Всем привет!
Подскажите алгоритм выравнивания древовидной диаграммы как на рисунке.
Левая диаграмма это то, что я имею на данный момент, правая диаграмма - идеальный вариант, который мне нужен.

Структура данных является вложенным json с таким интерфейсом { level: 1, children: [...] }
Алгоритмами обхода вложенной структуры владею (BFS, DFS)

На данный момент алгоритм такой:
- я рисую дерево сверху вниз по уровням
- новый уровень начинается с новой высоты = prevLevelCoordY + offsetHeight
- на новом уровне рисуются все его дочерние узлы
- каждый узел имеет фиксированный отступ по x

В итоге получаю первую диаграмму, где узлы накладываются друг на друга.

Как мне получить результат как во второй диаграмме? Сначала просто отрисовать дерево, а потом пробежаться снизу вверх и как-то расставить узлы?
Подскажите!

Untitled Diagram | Выравнивание и центрирование дерева по ширине

VoidSpiritПостоялецwww11 ноя. 201721:22#1
Судя по всему, узлы распихиваются в стороны так чтобы ни один нижележащий не перекрывался
susagePПостоялецwww11 ноя. 201721:25#2
ширина узла =  (сумма ширина подузла) + (количество подузлов-1)*отступ между узлами.
MikleМодераторwww12 ноя. 201710:57#3
2pizza
> Как мне получить результат как во второй диаграмме?
Рисуй снизу вверх, вышележащие узлы располагай над усреднённым центром всех их корней.
2pizzaПостоялецwww12 ноя. 201715:28#4
Mikle
Звучит неплохо на первый взгляд. А как выровнять крайний правый узел (2 уров.)? У него нет дочерних узлов
MikleМодераторwww12 ноя. 201718:22#5
2pizza
Да, такой случай (корень неполной длины) ломает алгоритм. В частности, такому узлу может не хватить места, придётся всё, что правее, сдвигать вправо на 1 позицию.
2pizzaПостоялецwww16 ноя. 201711:37#6
Есть у кого-нибудь еще идеи?
TelVoltПостоялецwww17 ноя. 201722:02#7
Ширина всех прямоугольников одинаковая?
TelVoltПостоялецwww17 ноя. 201722:22#8
И, кстати, уточняющий условие вопрос - если правому узлу добавить одного потомка, по где по условию он должен рисоваться?
9К720Участникwww18 ноя. 20171:23#9
2pizza
> А как выровнять крайний правый узел (2 уров.)? У него нет дочерних узлов
Да точно так же. как если бы был один дочерний узел
Нужно посчитать для каждого узлу его ширину, делается элементарно.
Она равна сумме ширин всех его дочерних элементов, либо единице, в случае их отсутствия.  В данном случае, ширина корневого элемента 4, у левой двойки ширина 2, у остальных по одному. Каждый элемент располагается на середине отведенного ему пространства, элементы могут перекрывать узлы сетки.

Будет как-то так. Рисовать можно начинать сверху
tree_aligment | Выравнивание и центрирование дерева по ширине

MikleМодераторwww18 ноя. 20178:32#10
9К720
> посчитать для каждого узлу его ширину, делается элементарно.
> Она равна сумме ширин всех его дочерних элементов, либо единице, в случае их
> отсутствия.
Тогда в нижнем ряду будут оставаться дырки даже тогда, когда есть место сдвинуть дерево.
clcПостоялецwww18 ноя. 201721:16#11
вы издеваетесь? в посте susageP всё решение

неужто трудно найти максимум?

Правка: 18 ноя. 2017 21:17

FordPerfectПостоялецwww19 ноя. 20170:16#12
// Sets up positions in all nodes of a (sub)tree. Returns total width of a subtree.
int process(Node &node,int offset=0,int spacing)
{
    int ret=node.width;
    int x=0;
    for(int i=0,n=node.children.size();i<n;++i)
        x+=process(node.children[i],offset+x,spacing)+(i<n-1)*spacing;
    if(x>ret) ret=x;
    node.x=offset+(ret-node.width)/2;
    return ret;
}
вроде.

Правка: 19 ноя. 2017 0:17

9К720Участникwww19 ноя. 201714:05#13
Mikle
> Тогда в нижнем ряду будут оставаться дырки даже тогда, когда есть место
> сдвинуть дерево.
Они в любом случае будут оставаться. Ты  конечно можешь сдвигать все слои чтобы ни в одном дырок не было, но тогда это дерево хер прочитаешь взглядом

/ Форум / Программирование игр / 2D графика и изометрия

2001—2017 © GameDev.ru — Разработка игр