如何防止家谱生成器中的重叠? [英] 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:

• 多个伴侣，而不是您通常看到的简单的 2 对 1 孩子.
• 多个兄弟姐妹
• 伴侣不一定要孩子
• 不必总是有一对父母，可以只有一个父亲/母亲

问题我遇到的是:我根据当前"节点/家庭成员生成偏移量，当我超过第一代时，比如说有 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 轴上绘制的示例:

这是实际应用和主 js 文件，我遇到了问题.这是我创建的 简化的 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.

一般来说，遗传遗传图不是平面的(参见平面图a> 在维基百科上).虽然不常见，但肯定会发生所有祖先关系都不是由独特的人填补的.例如，当表亲有孩子时，就会发生这种情况.

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；父母排名第一；祖父母排在第 2 位.(根据上面的警告，排名并不总是唯一的.)此类图的大部分区域都在祖先中.如果你不先布置叶子节点，你就没有任何成功的希望.这个想法是您首先布置排名最高的节点，逐步合并排名较低的节点.深度优先遍历是最常用的方法.

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屋！