Как я могу предотвратить наложение в генераторе генеалогического дерева?
Я создаю интерактивное средство создания генеалогического дерева, в отличие от более простых версий, которые представляют собой простые родословные диаграммы / деревья.
Требования к моим (на основе familyecho.com):
- несколько партнеров по сравнению с простыми 2 родителями на 1 ребенка, которых вы обычно видите.
- несколько братьев и сестер
- партнеры не обязательно должны иметь детей
- не всегда должна быть родительская "пара", может быть просто отец / мать
Проблема, с которой я сталкиваюсь: я генерирую смещения на основе "текущего" узла / члена семьи, и когда я прохожу мимо первого поколения с, скажем, 2 родителями, оно перекрывается.
Пример перекрытия, а также того, что партнер не отображается на одной оси X:
Вот собственно приложение и основной файл js, где у меня проблема. И вот упрощенный jsfiddle, который я создал, который демонстрирует проблему родителя / смещения, хотя мне действительно нужно решить перекрытие для этого в целом, в дополнение к тому, чтобы убедиться, что партнеры нарисованы на той же оси x, что и другие партнеры.
Как я могу решить этот и возможные будущие конфликты? Нужна ли какая-то функция перерисовки, которая обнаруживает столкновения и корректирует смещения каждого блока при обнаружении? Я пытаюсь сделать это без проблем, так что количество перерисовок ограничено.
Пример вычисления смещения относительно "контекста" или текущего узла:
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 );
}
3 ответа
Я собираюсь дать сложный ответ, и это потому, что эта ситуация сложнее, чем вы, кажется, знаете. Алгоритмы верстки графиков являются активной областью исследований. Легко попробовать более простой, чем общий алгоритм, а затем потерпеть неудачу захватывающим образом, когда вы делаете необоснованные и обычно скрытые предположения.
В целом, графики генетического наследования не являются плоскими (см. Планарные графики в Википедии). Хотя это необычно, конечно, случается так, что все родовые отношения не заполнены уникальными людьми. Это происходит, например, когда у двоюродных братьев есть дети.
Другая неплоская ситуация может возникнуть в ситуации детей от немоногамных родителей. Самый простой пример - это двое мужчин и две женщины, каждый в паре с детьми (то есть, по крайней мере, четыре). Вы не можете выложить даже четыре родительские пары в одном ряду без изогнутых линий.
Это только примеры. Я уверен, что вы узнаете больше, когда будете работать над своим алгоритмом. Настоящий урок здесь состоит в том, чтобы явным образом смоделировать класс отношений, которые ваш алгоритм способен выложить, и иметь проверочный код в алгоритме, чтобы обнаружить, когда данные не соответствуют этим требованиям.
Вопрос, который вы на самом деле задаете, гораздо более простой. У вас есть базовые трудности, потому что вам нужно использовать обход глубины графика. Это (самая простая) полная версия того, что значит выкладывать "сверху вниз" (в одном из комментариев). Это только один из многих алгоритмов обхода дерева.
Вы создаете ориентированный граф с (по крайней мере) неявным понятием ранга. Субъект ранга 0; родители ранга 1; бабушка и дедушка на 2-м уровне. (Кстати, вышеизложенные предупреждения не всегда уникальны.) Большая часть таких графов относится к родословной. Если вы сначала не раскроете листовые узлы, у вас нет надежды на успех. Идея состоит в том, что вы сначала размещаете узлы с самым высоким рангом, постепенно добавляя узлы с более низким рангом. Обход в глубину - самый распространенный способ сделать это.
Я бы отнесся к этому как к алгоритму переписывания графов. Базовая структура данных представляет собой гибрид визуализированных подграфов и базового графа предков. Рендеринг подграфа представляет собой (1) поддерево всего графа с (1a) набором потомства, все чьи предки рендерится, и (2) набором данных рендеринга: положения узлов и линий и т. Д. Исходное состояние гибрида является целым графом и не имеет визуализированных подграфов. Конечное состояние - это весь визуализированный граф. Каждый шаг алгоритма преобразует некоторый набор элементов на границе листа гибридного графа в (более крупный) визуализированный подграф, уменьшая количество элементов в гибридном графе. В конце есть только один элемент, граф визуализации в целом.
Поскольку вы уже используете Family Echo, я бы посоветовал вам взглянуть на то, как они разрабатывают свою онлайн-схему семейного древа, поскольку они, похоже, решили вашу проблему.
Когда я ввожу вашу примерную диаграмму в Family Echo, я могу создать красивое дерево, которое, как вам кажется, без переходов.
Хотя они создают свои диаграммы с помощью html и css, вы можете добавлять людей к их диаграммам один за другим, а затем проверять расположение блоков с точки зрения расположения левого и верхнего пикселов каждого элемента.
Если бы у меня было больше опыта в JavaScript, я бы попытался создать некоторый код, чтобы повторить часть того, что делает Family Echo, но я боюсь, что это не мое моджо.
Вам нужно будет отрегулировать все ответвления от узла, на который вы воздействуете, каждая ветвь должна будет пересчитать положение своих узлов, и каждый узел должен быть пересчитан локально, достигая листьев. Вы рассчитываете, как только листья будут иметь пересчитать весь путь до резервного копирования, все это рекурсивно. Это как настоящее дерево, когда вы добавляете физическую ветвь к стволу... другие ветки перемещаются в одиночку, чтобы оставить некоторое пространство, все листы автоматически сбрасываются, так что вы должны представить. И смоделируйте этот процесс на своей диаграмме. Обрабатывает каждую ветвь до каждого листа и пересчитывает до пересчета соседей модифицированного узла. (на один уровень выше, чем вы начали) Это непростая или не простая работа.