Как предотвратить перекрытие в генераторе генеалогического древа?

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

Требования для моего (на основе familyecho.com):

несколько партнеров по сравнению с простым родителем от 2 до 1, который вы обычно видите.
несколько братьев и сестер
партнеры не обязательно должны иметь детей
не всегда должна быть родительская "пара", может быть только один отец/мать

Проблема. Я встречаю: я генерирую смещения на основе "текущего" node/члена семьи, и когда я прохожу мимо первого поколения, скажем, 2 родителя, он перекрывается.

Пример перекрытия, а также партнера, который не нарисован на той же оси X:

Вот фактическое приложение и главный файл js где у меня проблема. И вот упрощенная jsfiddle Я создал, что демонстрирует проблему с родителем/смещением, хотя мне действительно нужно разрешить перекрытие для этого вообще, в дополнение к тому, чтобы партнеры были нарисованы на той же оси x, что и другие партнеры.

Как я могу решить это и возможные конфликты, перекрывающиеся в будущем? Нужна ли какая-то функция перерисовки, которая обнаруживает конфликты и корректирует смещения каждого блока при обнаружении? Я пытаюсь сделать его бесшовным, чтобы было сделано ограниченное количество перерисовки.

Пример вычисления смещения относительно "контекста" или текущего node:

var offset = getCurrentNodeOffset();

                        if ( relationship == RELATIONSHIPS.PARTNER ) {
                            var t = offset.top; // same level
                            var l = offset.left + ( blockWidth + 25 );
                        } else {
                            var t = offset.top - (blockHeight + 123 ); // higher
                            var l = offset.left - ( blockWidth - 25 );
                        }

Ответ 1

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

В общем, графики генетического наследования не являются плоскими (см. Planar Graphs в Википедии). Хотя необычно, конечно, случается, что все родовые отношения не заполняются уникальными людьми. Это происходит, например, когда у вторых кузенов есть дети.

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

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

Вопрос, который вы на самом деле задаете, тем не менее, является более основополагающим. У вас возникают основные трудности, потому что вам необходимо использовать глубину первого прохождения графика. Это (самая простая) полная версия того, что означает выкладывать "сверху вниз" (в одном из комментариев). Это только один из многих алгоритмов для обход дерева.

Вы выставляете ориентированный граф с (по крайней мере) неявным понятием ранга. Предметом является ранг 0; родители - ранг 1; бабушки и дедушки в ранге 2. (По поводу вышеприведенных предупреждений, ранжирование не всегда уникально.) Большая часть области таких графиков находится в родословной. Если вы сначала не выкладываете листовые узлы, у вас нет надежды на успех. Идея состоит в том, что сначала выкладываете узлы с самым высоким рангом, постепенно включая узлы с более низким рангом. Самый распространенный способ сделать это - обход по глубине.

Я бы рассматривал это как алгоритм перезаписи графа. Основная структура данных представляет собой гибрид визуализированных подграфов и базового графика предков. Отремонтированный подграф представляет собой (1) поддерево целого графа с (1a) набором потомства, все предки которого визуализируются и (2) набор данных рендеринга: положения узлов и строк и т.д. Начальное состояние гибрида - весь график и не имеет обработанных подграфов. Конечным состоянием является рендеринг целых графов. Каждый шаг алгоритма преобразует некоторый набор элементов на границе листа гибридного графа в (более крупный) визуализированный подграф, уменьшая количество элементов в гибриде. В конце есть только один элемент, графа рендеринга в целом.

Ответ 2

Поскольку вы уже используете Family Echo, я бы предложил вам посмотреть, как они разрабатывают свою онлайн-диаграмму генеалогического древа, поскольку они кажутся чтобы решить вашу проблему.

Когда я ввожу вашу диаграмму образцов в Family Echo, я могу построить красивое дерево, которое, похоже, является тем, что вы ищете, без перекрестка.

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

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

Ответ 3

вам нужно будет отрегулировать все ветки с node, на которые вы воздействуете, каждая ветвь должна будет пересчитать позицию своих узлов, и каждый node должен быть пересчитан локально, дойдя до листьев. Вы рассчитали как только листья должны будут пересчитать весь путь к резервному копированию, все это рекурсивно. Это похоже на реальное дерево, когда вы добавляете физическую ветвь в туловище... другие ветки перемещаются в одиночку, чтобы оставить некоторое пространство, все листы автоматически reset, поэтому вы должны себе представить. И имитируйте этот процесс на диаграмме. Процессы каждой ветки достигают каждого листа и пересчитывают до пересчета измененных соседей node. (один уровень выше вас начался) Это непростая или простая работа.