19

我正在创建一个交互式家谱创建者，这与更简单的版本不同，后者是简单的谱系图/树。

我的要求（基于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 );
                        }
4

3 回答 3

19

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

通常，遗传继承图不是平面图（参见Wikipedia 上的平面图）。虽然不常见，但肯定会发生所有祖先关系都不是由独特的人填补。例如，当第二代堂兄弟有孩子时，就会发生这种情况。

另一种非平面情况可能发生在非一夫一妻制父母的孩子的情况中。最简单的例子是两男两女，每人都有孩子（因此至少有四个）。如果没有曲线，您甚至无法将四对父级排列在一个等级中。

这些只是示例。我相信您在研究算法时会发现更多。这里真正的教训是明确地建模您的算法能够布置的关系类别，并在算法中使用验证码来检测数据何时不满足这些要求。

但是，您实际上要问的问题要基本得多。您遇到了基本困难，因为您需要使用图的深度优先遍历。这是“从上到下”（在其中一条评论中）布局的（最简单的）完整版本。这只是树遍历的众多算法之一。

您正在使用（至少）隐含的等级概念来布置有向图。主题为 0 级；父母排名第一；排名第 2 的祖父母。（根据上面的警告，排名并不总是唯一的。）此类图表的大部分区域都在祖先中。如果不先布局叶子节点，就没有成功的希望。这个想法是您首先布置具有最高等级的节点，逐渐合并较低等级的节点。深度优先遍历是最常见的方法。

我会将其视为图形重写算法。基本数据结构是渲染子图和底层祖先图的混合体。渲染的子图是 (1) 整个图的子树，具有 (1a) 一组后代，其所有祖先都被渲染，以及 (2) 渲染数据的集合：节点和线的位置等。初始状态混合图是整个图并且没有渲染子图。最终状态是渲染的整个图。算法的每一步都将混合图叶边界处的一组元素转换为（更大的）渲染子图，从而减少混合图中的元素数量。最后只有一个元素，整个渲染图。

于 2015-12-05T15:48:15.953 回答
3

由于您已经在使用Family Echo，我建议您看看他们如何开发他们的在线家谱图，因为他们似乎已经解决了您的问题。

当我将您的示例图输入到 Family Echo 中时，我可以构建一棵看起来很漂亮的树，这似乎是您正在寻找的，没有交叉。

在此处输入图像描述

尽管他们使用 html 和 css 创建图表，但您可以将人员一一添加到他们的图表中，然后根据每个元素的左侧和顶部像素位置检查框的放置位置。

在此处输入图像描述

如果我在 JavaScript 方面有更多的专业知识，我会尝试构建一些代码来复制 Family Echo 正在做的一些事情，但恐怕这不是我的魔力。

于 2015-12-05T18:03:28.540 回答
2

您必须调整您影响的节点上的所有分支，每个分支都必须重新计算其节点的位置，并且每个节点都必须在本地重新计算到达叶子。您计算一旦叶子将有以递归方式重新计算一直到备份。就像一棵真正的树，当您将物理分支添加到树干时......其他分支单独移动以留下一些空间，所有纸张都会自动重置，所以您必须想象。并在您的图表中模拟此过程。处理每个分支到达每个叶子，并重新计算以重新计算修改后的节点邻居。（比你开始的高一级）这不是一件容易的事，也不是一项单一的工作。

于 2015-12-11T23:54:23.377 回答