Wie kann ich Überlappungen in einem Stammbaumgenerator verhindern?

Question

Ich erstelle einen interaktiven Stammbaumersteller, im Gegensatz zu einfacheren Versionen, die einfache Ahnentafel/Bäume sind.

Die Anforderungen für Mine (basierend auf familyecho.com) sind:

• mehrere Partner vs nur ein einfaches 2 Elternteil 1 Kind, die Sie normalerweise sehen.
• mehrere Geschwister
• Partner nicht unbedingt Kinder haben müssen
• es muss nicht immer ein Elternteil „Paar“ sein, kann es nur eine einzige Vater/Mutter sein

Das Problem Ich begegne ist: Ich erzeuge die Offsets basierend auf dem "aktuellen" Knoten/Familienmitglied und wenn ich über die erste Generation mit sagen, 2 Eltern, es überlappt.

Beispiel der Überlappung sowie Partner nicht auf der gleichen X-Achse gezogen wird:

Hier ist die actual app und main js file, wo ich das Problem habe. Und hier ist ein simplified jsfiddle Ich erstellt, dass das Eltern/Offset-Problem, obwohl ich wirklich Überschneidungen für diese im Allgemeinen lösen muss, zusätzlich zu sicherzustellen, dass Partner auf der gleichen x-Achse wie andere Partner gezeichnet werden.

Wie kann ich diese und mögliche Konflikte in der Zukunft lösen? Benötige ich irgendeine Art von Neuzeichnungsfunktion, die collisions erkennt und die Offsets jedes Blocks bei der Erkennung anpasst? Ich versuche, es nahtlos zu machen, so dass nur ein begrenztes Neuzeichnen möglich ist.

Ein Beispiel zum „Kontext“ versetzt Berechnung oder aktuellen Knoten:

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

ich eine komplizierte Antwort geben werde, und das ist, weil diese Situation komplizierter ist, als Sie sich bewusst zu sein scheinen. Graph-Layout-Algorithmen sind ein aktives Forschungsgebiet. Es ist einfach, einen einfacheren Algorithmus als den allgemeinen Algorithmus zu verwenden und dann auf spektakuläre Weise zu versagen, wenn Sie unberechtigte und normalerweise verborgene Annahmen machen.

Im Allgemeinen sind genetische Vererbungsdiagramme nicht planar (siehe Planar Graphs auf Wikipedia). Obwohl es ungewöhnlich ist, kommt es sicher vor, dass alle Beziehungen der Vorfahren nicht von einzigartigen Menschen ausgefüllt werden. Dies passiert zum Beispiel, wenn Cousins ​​zweiten Grades Kinder haben.

Eine andere nichtplanare Situation kann in der Situation von Kindern von nicht monogamen Eltern auftreten. Das einfachste Beispiel sind zwei Männer und zwei Frauen, die sich jeweils mit Kindern paaren (also mindestens vier). Sie können nicht einmal die vier Elternpaare in einem Rang ohne geschwungene Linien auslegen.

Dies sind nur Beispiele. Ich bin sicher, Sie werden mehr entdecken, wenn Sie an Ihrem Algorithmus arbeiten. Die wahre Lektion hier ist, die Klasse der Beziehung, die Ihr Algorithmus erstellen kann, explizit zu modellieren und einen Verifizierungscode im Algorithmus zu haben, um zu erkennen, wenn die Daten diese Anforderungen nicht erfüllen.

Die Frage, die Sie tatsächlich stellen, ist jedoch viel einfacher. Sie haben grundlegende Schwierigkeiten, weil Sie eine depth-first traversal des Diagramms verwenden müssen. Dies ist die (einfachste) Vollversion dessen, was es bedeutet, "von oben nach unten" auszulegen (in einem der Kommentare). Dies ist nur einer von vielen Algorithmen für tree traversal.

Sie legen einen gerichteten Graphen mit (zumindest) implizitem Rangbegriff an. Das Thema ist Rang 0; Eltern sind Rang 1; Großeltern auf Rang 2. (Apropos die Warnungen oben, Ranking ist nicht immer eindeutig.) Der größte Teil der Fläche solcher Graphen ist in der Abstammung. Wenn Sie die Blattknoten nicht zuerst auslegen, haben Sie keine Hoffnung auf Erfolg. Die Idee ist, dass Sie Knoten mit dem höchsten Rang zuerst auslegen und nach und nach Knoten mit niedrigerem Rang einbeziehen. Tiefe-zuerst-Traversierung ist die gebräuchlichste Art, dies zu tun.

Ich würde dies als Graph-Rewriting-Algorithmus behandeln. Die grundlegende Datenstruktur ist eine Mischung aus gerenderten Untergraphen und dem zugrundeliegenden Ahnengraph. Ein gerenderter Untergraph ist ein (1) ein Teilbaum des gesamten Graphen mit (1a) einem Satz von Nachkommen, von denen alle Vorfahren gerendert werden und (2) eine Sammlung von Rendering-Daten: Positionen von Knoten und Linien, usw. Der Anfangszustand der Hybrid ist der gesamte Graph und hat keine gerenderten Untergraphen. Der Endzustand ist ein gerenderter ganzer Graph. Jeder Schritt des Algorithmus wandelt einen Satz von Elementen an der Blattgrenze des Hybridgraphen in einen (größeren) gerenderten Untergraphen um, wodurch die Anzahl von Elementen in dem Hybrid reduziert wird. Am Ende gibt es nur ein Element, den Rendergraphen als Ganzes.

Answer 2

Da Sie bereits Family Echo verwenden, würde ich vorschlagen, Sie schauen, wie sie ihre Online-Stammbaum-Diagramm entwickeln, da sie Ihr Problem gelöst haben scheinen.

Wenn ich Ihr Beispieldiagramm in Family Echo eintrage, kann ich einen schön aussehenden Baum bauen, der scheinbar ohne Überkreuzung aussieht.

Obwohl sie ihre Diagramme mit HTML und CSS erstellen, können Sie die Menschen in ihre Diagramme nacheinander hinzufügen und dann prüfen, wo die Kisten in Bezug auf die linken und oberen Pixelpositionen platziert werden jedes Element.

Wenn ich mehr Erfahrung in JavaScript hätte, würde ich habe versucht, einen Code Aufbau zu einigen zu replizieren, was Familie Echo tut, aber ich fürchte, das ist nicht mein mojo.

Answer 3

Sie müssen alle Zweige von dem Knoten anpassen, den Sie beeinflussen, jeder Zweig muss die Position seiner Knoten neu berechnen, und jeder Knoten muss lokal neu berechnet werden, um die Blätter zu erreichen. Sie haben einmal die Blätter berechnet müssen den ganzen Weg bis zur Sicherung neu berechnen, alles rekursiv. Es ist wie bei einem echten Baum, wenn Sie physisch zum Stamm verzweigen ... die anderen Zweige bewegen sich alleine, um Platz zu lassen, alle Blätter werden automatisch zurückgesetzt, also müssen Sie sich vorstellen. Und simuliere diesen Prozess in deinem Diagramm. Verarbeitet jeden Zweig erreicht jedes Blatt und berechnet neu, um die modifizierten Knotennachbarn neu zu berechnen. (eine Stufe über dir begann) Das ist nicht einfach oder Einzelarbeit.