Алгоритм отрисовки генеалогического древа: Как правильно рассчитать координаты X для узлов, чтобы линии супружеских связей не перекрывали линии потомства?
Отрисовка генеалогического дерева — нетривиальная задача визуализации графов. Главная сложность состоит в том, что в отличие от обычного дерева здесь присутствуют два типа рёбер: вертикальные (родитель → потомок) и горизонтальные (супружеская пара). Их пересечение делает схему нечитаемой. Ниже описан практический алгоритм.
## 1. Базовые принципы
Каждое поколение располагается на отдельном уровне по оси Y. По оси X нужно разместить узлы так, чтобы:
— супруги стояли рядом (минимальный горизонтальный зазор между ними);
— дети центрировались под серединой пары;
— поддеревья не перекрывались.
## 2. Представление данных
Модель: каждый человек — узел с полями `id`, `spouseId`, `children[]`, `generation`. Супружеская пара образует «семейный блок» (FamilyUnit), который является атомарной единицей размещения.
## 3. Алгоритм расчёта X (bottom-up)
**Шаг 1. Листовые узлы.** Людям без детей присваивается ширина `NODE_WIDTH + MARGIN`. Если у листового узла есть супруг, ширина блока = `2 * NODE_WIDTH + COUPLE_GAP`.
**Шаг 2. Внутренние узлы (рекурсия снизу вверх).** Ширина семейного блока = максимум из:
— суммы ширин всех дочерних блоков;
— `2 * NODE_WIDTH + COUPLE_GAP` (минимум для самой пары).
**Шаг 3. Присвоение X.** Обход сверху вниз:
function assignX(familyUnit, startX):
midX = startX + familyUnit.width / 2
husbandX = midX — COUPLE_GAP / 2 — NODE_WIDTH / 2
wifeX = midX + COUPLE_GAP / 2 + NODE_WIDTH / 2
childrenTotalWidth = sum(child.width for child in children)
childStartX = midX — childrenTotalWidth / 2
for child in children:
assignX(child, childStartX)
childStartX += child.width
## 4. Линия супружеской связи
Линия рисуется горизонтально между `husbandX` и `wifeX` на уровне Y поколения. Линия потомства опускается вертикально от середины этой горизонтали (`midX`) вниз к детям. Таким образом, горизонтальная линия пары и вертикальные линии потомства **пересекаются только в одной точке** — `midX`, что визуально корректно.
## 5. Разрешение конфликтов при повторных браках
Если у человека несколько браков, каждый брак образует отдельный FamilyUnit. Общий родитель смещается так, чтобы его X-координата находилась между центрами всех его семейных блоков. Для этого применяется алгоритм Reingold–Tilford с модификацией под биграфы.
## 6. Постобработка: устранение остаточных пересечений
После первичного размещения запускается проход, проверяющий все пары линий на пересечение методом sweep line. При обнаружении конфликта поддерево сдвигается вправо на минимально необходимое расстояние, после чего пересчитываются X родительских узлов.
## 7. Рекомендуемые константы
— `NODE_WIDTH` = 120 px
— `COUPLE_GAP` = 40 px (расстояние между супругами)
— `MARGIN` = 20 px (зазор между соседними блоками)
— `LEVEL_HEIGHT` = 160 px
Соблюдение этих принципов гарантирует, что линии браков всегда остаются горизонтальными, а линии потомства — вертикальными, без взаимных перекрытий.