如何防止在家谱树生成器中的重叠？ [英] How can I prevent overlapping in a family tree generator?

问题描述

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

I'm creating an interactive family tree creator, unlike more simpler versions which are simple pedigree charts/trees.

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

The requirements for mine (based on familyecho.com) are:

• 多个合作伙伴vs只是一个简单的2个家长，你通常看到的1个孩子。 li>
  
• 多个兄弟姐妹


• 合作伙伴不一定需要有子女


• pair，只能有一个父亲/母亲

问题 ：我基于当前节点/家庭成员生成偏移量，当我经过第一代，说，2父母，它重叠。

The problem I'm encountering is: I'm generating the offsets based on the "current" node/family member and when I go past the first generation with say, 2 parents, it overlaps.

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

这里是实际应用和 main js file 我遇到的问题。这里是一个简化的jsfiddle 我创建的演示父/偏移问题，但我真的必须解决除了确保合作伙伴在与其他合作伙伴相同的x轴上绘制外，还会为此一般重叠。

Here is the actual app and main js file where I'm having the issue. And here is a simplified jsfiddle I created that demonstrates the parent/offset issue though I really have to solve overlapping for this in general, in addition to making sure partners are drawn on the same x axis as other partners.

如何解决这个问题和未来可能的重叠冲突？我需要某种重绘功能来检测冲突，并在检测到时调整每个块的偏移量？

How can I go about solving this and possible future overlapping conflicts? Do I need some sort of redraw function that detects collisions and adjusts the offsets of each block upon detecting? I'm trying to make it seamless so there's a limited amount of redrawing done.

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

An example of calculating offset relative to the "context" or current node:

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 );
                        }

推荐答案

一个复杂的答案，这是因为这种情况比你看起来更复杂。图形布局算法是一个活跃的研究领域。这是很容易尝试一个更简单的通用算法，然后使它失败在壮观的方式，当你做无根据的，通常隐藏的假设。

I'm going to give a complicated answer, and that's because this situation is more complicated than you seem aware of. Graph layout algorithms are an active field of research. It's easy to attempt a simpler-than-general algorithm and then have it fail in spectacular ways when you make unwarranted, and usually hidden, assumptions.

一般来说，遗传继承图表不是平面（请参阅维基百科上的平面图）。虽然不常见，但肯定发生的是，所有的祖先关系不是由独特的人填充。这发生，例如，当第二个表兄弟有孩子。

In general, genetic inheritance graphs are not planar (see Planar Graphs on Wikipedia). Although uncommon, it certainly happens that all the ancestral relationships are not filled by unique people. This happens, for example, when second cousins have children.

另一种非平面情况可能发生在来自非一夫一妻制父母的儿童的情况中。最简单的例子是两个男人和两个女人，每个人与孩子配对（因此至少有四个）。你甚至不能在没有曲线的一个排名中排列四个父对。

Another non-planar situation can occur in the situation of children from non-monogamous parents. The very simplest example is two men and two women, each pairing with children (thus at least four). You can't lay out even the four parent pairs in one rank without curved lines.

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

These are only examples. I'm sure you'll discover more as you work on your algorithm. The real lesson here is to explicitly model the class of relationship your algorithm is able to lay out and to have verification code in the algorithm to detect when the data doesn't meet these requirements.

你实际上问的问题是更基本的。您遇到了基本困难，因为您需要使用深度优先遍历图形。这是（最简单的）完整版的意思是从上到下（在其中一个意见）。这只是树遍历的众多算法之一。

The question you are actually asking, though, is far more basic. You're having basic difficulties because you need to be using a depth-first traversal of the graph. This is the (easiest) full version of what it means to lay out "from the top down" (in one of the comments). This is only one of many algorithms for tree traversal.

你正在布局一个有（至少）隐含的秩概念的有向图。主题是0;父母是1级;祖父母在等级2.（Apropos上面的警告，排名并不总是唯一的。）这些图的大部分区域是在祖先。如果你不首先布置叶节点，你没有任何希望成功。这个想法是，你排列第一个最高排名的节点，逐步结合排名较低的节点。深度优先遍历是最常见的做法。

You're laying out a directed graph with (at least) implicit notion of rank. The subject is rank 0; parents are rank 1; grandparents at rank 2. (Apropos the warnings above, ranking is not always unique.) Most of the area of such graphs is in the ancestry. If you don't lay out the leaf nodes first, you don't have any hope of succeeding. The idea is that you lay out nodes with the highest rank first, progressively incorporating lower-ranked nodes. Depth-first traversal is the most common way of doing this.

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

I would treat this as a graph-rewriting algorithm. The basic data structure is a hybrid of rendered subgraphs and the underlying ancestry graph. A rendered subgraph is a (1) a subtree of the whole graph with (1a) a set of progeny, all of whose ancestors are rendered and (2) a collection of rendering data: positions of nodes and lines, etc. The initial state of the hybrid is the whole graph and has no rendered subgraphs. The final state is a rendered whole graph. Each step of the algorithm converts some set of elements at the leaf boundary of the hybrid graph into a (larger) rendered subgraph, reducing the number of elements in the hybrid. At the end there's only one element, the render graph as a whole.

这篇关于如何防止在家谱树生成器中的重叠？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！