javascript - 如何防止家谱生成器中的重叠？

Question

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

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

• 多个合作伙伴与您通常看到的简单的 2 个 parent 和 1 个 child 。
• 多个 sibling
• 伴侣不一定需要有 child
• 并不总是必须有一对 parent ，可以只有一个父亲/母亲

我遇到的问题是:我根据“当前”节点/家庭成员生成偏移量，当我通过第一代(例如，2个 parent )时，它会重叠。

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

这是actual app和 main js file我遇到问题的地方。这是 simplified jsfiddle我创建的演示了父/偏移问题，但除了确保合作伙伴与其他合作伙伴绘制在相同的 x 轴上之外，我确实必须一般解决此问题的重叠问题。

我该如何解决这个问题以及 future 可能出现的重叠冲突？我是否需要某种重绘函数来检测 collisions并在检测时调整每个 block 的偏移量？我正在努力使其无缝，因此完成的重绘数量有限。

计算相对于“上下文”或当前节点的偏移量的示例:

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 Graphs)。虽然不常见，但确实并非所有的祖先关系都是由独特的人填补的。例如，当远房表 sibling 有了 child 时，就会发生这种情况。

另一种非平面情况可能发生在非一夫一妻制 parent 的 child 的情况下。最简单的例子是两个男人和两个女人，每个人都带着 child (因此至少有四个)。如果没有曲线，您甚至无法将四个父对排列在一个行中。

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

不过，您实际上问的问题要基本得多。您遇到了基本困难，因为您需要使用 depth-first traversal图表的。这是“从上到下”布局的(最简单的)完整版本(在评论之一中)。这只是 tree traversal 的众多算法之一。 .

您正在布置一个有向图(至少)包含隐式的排名概念。该主题的等级为 0； parent 排名第一；祖 parent 排名第 2。(关于上面的警告，排名并不总是唯一的。)此类图表的大部分区域都在祖先中。如果不先布置叶节点，就没有成功的希望。这个想法是，首先布置排名最高的节点，然后逐渐合并排名较低的节点。深度优先遍历是最常见的方法。

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