如何防止在族树生成器中重叠？

Question

我正在创建一个交互式家谱树创建者,不像更简单的版本,它是简单的谱系图表/树.

我的要求(基于familyecho.com)是:

• 多个合作伙伴与您通常看到的简单2父母对1个孩子.
• 多个兄弟姐妹
• 伙伴们不一定需要生孩子
• 并不总是必须是父母"对",只有一个父亲/母亲

我遇到的问题是:我正在根据"当前"节点/家庭成员生成偏移量,当我越过第一代时,例如2个父母,它重叠.

重叠的示例以及未在同一X轴上绘制的伙伴:

这是我遇到问题的实际app和主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 );
                        }

Answer 1

我将给出一个复杂的答案,那是因为这种情况比你想象的要复杂得多.图形布局算法是一个活跃的研究领域.尝试一种比通用算法简单的算法更容易,然后当你做出无根据的,通常是隐藏的假设时,它会以惊人的方式失败.

在一般情况下,基因遗传图是不平坦的(见平面图上维基百科).虽然不常见,但肯定会发生所有祖先关系都没有被独特的人填补.例如,当第二代堂兄弟有孩子时就会发生这种情况.

在非一夫一妻制的父母的孩子的情况下可能出现另一种非平面情况.最简单的例子是两个男人和两个女人,每个女人与孩子配对(因此至少有四个).如果没有曲线,你甚​​至不能在一个等级中布置四个父对.

这些仅是示例.我相信你在研究你的算法时会发现更多.这里真正的教训是明确地建模您的算法能够布局的关系类,并在算法中使用验证码来检测数据何时不符合这些要求.

不过,你实际问的问题要基本得多.您遇到了基本的困难,因为您需要使用图的深度优先遍历.这是"从上到下"(在其中一条评论中)布局的最简单的完整版本.这只是树遍历的众多算法之一.

你正在制定一个有(至少)隐含的等级概念的有向图.主题是0级; 父母是1级; 排名第2的祖父母.(上述警告,排名并不总是唯一的.)这些图的大部分区域都在祖先.如果您没有首先布置叶节点,那么您没有任何成功的希望.我们的想法是首先布置排名最高的节点,逐步合并排名较低的节点.深度优先遍历是执行此操作的最常见方式.

我会把它当作图重写算法.基本数据结构是渲染子图和基础祖先图的混合体.渲染子图是(1)整个图的子树,其中(1a)是一组后代,其所有祖先都被渲染,(2)渲染数据的集合:节点和线的位置等.初始状态混合的是整个图形,没有渲染的子图.最终状态是渲染的整个图形.算法的每一步都将混合图的叶边界处的一些元素集转换为(更大的)渲染子图,从而减少混合中元素的数量.最后只有一个元素,渲染图作为一个整体.