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

Question

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

javascriptchartsjsplumbfamily-treegenealogy

19

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

我的要求（基于familyecho.com）是：

- 多个配偶而不仅仅是通常看到的两个父母和一个孩子。 - 多个兄弟姐妹 - 配偶不一定需要有孩子 - 不一定总是有一个父母“对”，可能只有单身父亲/母亲

我遇到的问题是：我基于“当前”节点/家庭成员生成偏移量时，当我超过第一代时，例如有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 );
                        }

- meder omuraliev

1

对于重叠的祖父/祖母的问题，你所要做的就是拉开相关父母之间的距离，也许？ - Rodrigo

1

你尝试过从上往下布置节点而不是当前的自下而上的方法吗？你遇到重叠的问题，因为（至少在JavaScript示例中）你是基于子节点的位置来定位父节点的。这种方法失败了，因为它在添加新的父节点时没有考虑兄弟节点，只是将它们随意放置并希望一切顺利。 - aroth

@Rodrigo - 我相信我尝试过那个，但遇到了其他问题。我会尝试在另一个fiddle中重新创建它。 - meder omuraliev

@aroth - 目前只是自下而上的方式，我认为我可能需要一个函数，在每个新节点添加时触发它，它将检查碰撞和/或重新排列每个节点。我实际上尝试使用自上而下的方法在d3js中重新完成所有这些工作，但我遇到了类似的问题，所以我最好在这里解决它们。 - meder omuraliev

@Rodrigo - 你的意思是每个节点都要包括在内，并且不包括边界线吗？每个块的大小为100x90像素，画布的大小将是5000x5000，但我可能会把它做得更大。 - meder omuraliev

显示剩余8条评论

3个回答

3

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

当我将您的示例图表输入到Family Echo中时，我可以构建一个漂亮的树形图，它似乎是您正在寻找的，没有交叉。

虽然他们是用html和css创建他们的图表，但你可以逐个添加人员到他们的图表中，然后检查每个元素左上角像素位置放置的盒子。

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

- lkessler

代码真的太混淆了，很多数学计算和iframe嵌入。很难理解familyecho是如何实现的。因此基本上是在询问如何以类似的方式实现它。 - meder omuraliev

还可以在stackoverflow上查看相关问题，也许对您有所帮助：https://dev59.com/CW035IYBdhLWcg3wE71s - lkessler

1

我已经研究了几乎所有相关的SO问题和项目，但似乎没有一个符合需求。https://github.com/djfun/geneajs可能是一个不错的起点。 - meder omuraliev

1

链接到http://philogb.github.io/jit/static/v20/Jit/Examples/Hypertree/example1.html - 这需要对我的图表需求进行广泛的定制，基本上需要做同样数量的工作/重新做我正在做的事情。 - meder omuraliev

1

如果你找到了一个类似我需要的图表，请告诉我！我一直在搜索，但还没有找到。 - meder omuraliev

显示剩余2条评论

2

如果你要调整节点，那么你需要调整该节点所影响的所有分支，每个分支都必须重新计算其节点的位置，每个节点都必须在本地重新计算，一直到达叶子节点。一旦计算好了叶子节点，就需要递归地向上重新计算所有内容。这就像是一棵真正的树，当你在主干上添加分支时，其他分支会自动移动以留出一些空间，所有的叶子也会被自动重置，所以你需要想象并在图表中模拟这个过程。处理每个分支，到达每个叶子节点，并重新计算以重新计算修改后的节点邻居（从你开始的上一级）。这不是一个容易完成的单一工作。

- user1817927

你能详细说明一下“单个任务”是什么意思吗？ - meder omuraliev

也许你会发现这个有用：https://github.com/mbostock/d3/wiki/Gallery 第三十个画廊（可折叠树状布局）：http://bl.ocks.org/robschmuecker/7880033 - user1817927

或者这个（可折叠力导向图）：http://mbostock.github.com/d3/talk/20111116/force-collapsible.html 在同一个画廊中：https://github.com/mbostock/d3/wiki/Gallery - user1817927

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eh9 · Accepted Answer

我会给出一个复杂的答案，因为这种情况比你所认识的要复杂得多。图形布局算法是一个活跃的研究领域。尝试一个简单的算法很容易失败，并且通常存在未经证明且隐藏的假设。

一般来说，遗传谱系图并不是平面图（请参阅维基百科上的平面图）。虽然不太常见，但确实存在所有祖先关系都不是唯一人填补的情况。例如，当表兄弟姐妹有孩子时就会发生这种情况。

在非一夫一妻家庭中，还会出现另一种非平面情况。最简单的例子是两个男人和两个女人，每个人都与孩子配对（至少四个）。即使只是排列这四个父母对，也无法在同一层级上摆放而不使用曲线。

这些只是例子。我相信在你研究算法时会发现更多情况。真正的教训是明确地对算法能够布局的关系类进行建模，并在算法中编写验证代码以检测数据是否符合要求。

但你实际上正在询问的问题更基本。你遇到基本困难是因为需要使用深度优先遍历图形。这是“从上到下”布局意义的（最简单）完整版本之一（见评论中）。这只是众多树遍历算法之一。

您正在布置一个带有（至少）隐含级别概念的有向图。主题是第0级; 父母在第一级; 祖父母在第二级。（关于上面的警告，排名并不总是唯一的。）这类图的大部分区域都在祖先那里。如果您不先布置叶子节点，则没有任何成功的希望。您的想法是首先布置最高级别的节点，逐步合并较低级别的节点。深度优先遍历是实现此目标最常见的方法。

我会将其视为图重写算法。基本数据结构是渲染子图和底层谱系图的混合体。已渲染的子图是整个图的子树，具有以下特征：（1a）所有祖先都已被呈现，并且（1b）一组后代，以及（2）渲染数据的集合，例如节点和线的位置等。混合物的初始状态是整个图形，没有呈现的子图。最终状态是已经渲染好的整个图形。该算法的每个步骤将混合图的边界处的某些元素转换为（更大的）渲染子图，从而减少混合中元素的数量。最后只有一个元素，即整个渲染图。