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

Question

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

Требование шахтного (на основе familyecho.com) являются:

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

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

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

Здесь actual app и main js file, где у меня вопрос. И вот simplified jsfiddle, который я создал, который демонстрирует проблему с родительским/смещением, хотя мне действительно нужно разрешить перекрытие для этого вообще, в дополнение к тому, чтобы партнеры были нарисованы на той же оси x, что и другие партнеры.

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

Пример расчета смещения относительно «контекста» или текущего узла:

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); 
         } 

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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