How can I prevent overlapping in a family tree generator?

meder omuraliev

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

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

  • multiple partners vs just a simple 2 parent to 1 child that you normally see.
  • multiple siblings
  • partners dont necessarily need to have children
  • there doesn't always have to be a parent "pair", there can just be a single father/mother

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.

Example of the overlap as well as partner not being drawn on the same X axis:

enter image description here

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

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.

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.

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

How can I prevent annoying workspace- overlapping window appearance?

From Dev

How can I prevent values from overlapping in a Python multiprocessing?

From Dev

How can I prevent custom Tree Node Data loss for a TTreeView?

From Dev

How can I mitigate having bidirectional relationships in a family tree, in Neo4j?

From Dev

How can I prevent images from overlapping when the window is scaled up?

From Dev

How can I prevent a conflict between JSON encode and a unique id generator?

From Java

How to prevent overlapping in view?

From Dev

How to prevent textblock to overlapping?

From Dev

How can I manage overlapping DropDownBox drawers?

From Dev

How can I stop these buttons overlapping?

From Dev

How can I define "overlapping" enums in Rust?

From Dev

How can I match overlapping strings with regex?

From Dev

How can i find overlapping times in python

From Dev

How can I Prioritize Overlapping Patterns in RegEx?

From Dev

App Generator: How can I declare a variable for use in the entire generator?

From Dev

How to prevent overlapping schedules in Spring?

From Dev

How to prevent divs from overlapping?

From Dev

How can I convert this async callback to a generator?

From Dev

How can I write a generator in a JavaScript class?

From Dev

How can I extend the JOOQ code generator?

From Dev

How can I write a code generator in Ceylon

From Dev

How can I get the following generator to work?

From Dev

How can I set android font family to make the width the same?

From Dev

How can i get list of font family(or Name of Font) in matplotlib

From Dev

What is the default font family in HTML and how can I check this?

From Dev

How can i get list of font family(or Name of Font) in matplotlib

From Dev

How to create a family tree structure in JSON format

From Dev

How to create a family tree structure in JSON format

From Dev

How to format family tree from array

Related Related

  1. 1

    How can I prevent annoying workspace- overlapping window appearance?

  2. 2

    How can I prevent values from overlapping in a Python multiprocessing?

  3. 3

    How can I prevent custom Tree Node Data loss for a TTreeView?

  4. 4

    How can I mitigate having bidirectional relationships in a family tree, in Neo4j?

  5. 5

    How can I prevent images from overlapping when the window is scaled up?

  6. 6

    How can I prevent a conflict between JSON encode and a unique id generator?

  7. 7

    How to prevent overlapping in view?

  8. 8

    How to prevent textblock to overlapping?

  9. 9

    How can I manage overlapping DropDownBox drawers?

  10. 10

    How can I stop these buttons overlapping?

  11. 11

    How can I define "overlapping" enums in Rust?

  12. 12

    How can I match overlapping strings with regex?

  13. 13

    How can i find overlapping times in python

  14. 14

    How can I Prioritize Overlapping Patterns in RegEx?

  15. 15

    App Generator: How can I declare a variable for use in the entire generator?

  16. 16

    How to prevent overlapping schedules in Spring?

  17. 17

    How to prevent divs from overlapping?

  18. 18

    How can I convert this async callback to a generator?

  19. 19

    How can I write a generator in a JavaScript class?

  20. 20

    How can I extend the JOOQ code generator?

  21. 21

    How can I write a code generator in Ceylon

  22. 22

    How can I get the following generator to work?

  23. 23

    How can I set android font family to make the width the same?

  24. 24

    How can i get list of font family(or Name of Font) in matplotlib

  25. 25

    What is the default font family in HTML and how can I check this?

  26. 26

    How can i get list of font family(or Name of Font) in matplotlib

  27. 27

    How to create a family tree structure in JSON format

  28. 28

    How to create a family tree structure in JSON format

  29. 29

    How to format family tree from array

HotTag

Archive