Comment puis-je éviter le chevauchement dans un générateur d'arbre généalogique?
je crée un créateur d'arbre généalogique interactif, contrairement aux versions plus simples qui sont de simples cartes généalogiques/arbres.
Les exigences pour le mien (basé sur familyecho.com):
- de multiples partenaires vs juste un simple 2 parents 1 enfant que vous voyez normalement.
- frères et sœurs multiples
- les partenaires n'ont pas nécessairement besoin d'avoir des enfants
- il n'est pas nécessaire qu'il y ait toujours une "paire" de parents, il peut simplement y avoir un père/mère célibataire
Le problème je rencontre est le suivant: je suis de la génération de la décalages basé sur le "courant" node/membre de la famille et quand je vais au delà de la première génération avec 2 parents, il chevauche.
exemple de chevauchement ainsi que de partenaire n'étant pas dessiné sur le même axe X:
voici le app actuelle et fichier principal js où j'ai le problème. Et voici un jsfiddle simplifié j'ai créé qui montre la question parent / offset bien que je dois vraiment résoudre le chevauchement pour ce en général , en plus de s'assurer que les partenaires sont tirés sur le même axe x que les autres partenaire.
Comment puis-je résoudre ceci et d'éventuels conflits futurs qui se chevauchent? Ai-je besoin d'une sorte de fonction de réécriture qui détecte collisions et ajuste les offsets de chaque bloc à la détection? J'essaie de la rendre transparente pour qu'il y ait une quantité limitée de redessinée.
exemple de calcul de décalage par rapport au "contexte" ou au noeud courant:
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 );
}
3 réponses
je vais donner une réponse nuancée, et c'est parce que cette situation est plus compliquée que vous semblez connaître. Les algorithmes de graphisme sont un domaine de recherche actif. Il est facile de tenter un algorithme plus simple que général et puis de le faire échouer de manière spectaculaire quand vous faites injustifié, et généralement caché, hypothèses.
en général, les graphiques d'héritage génétique sont pas planar (voir Planar Graphs sur Wikipédia). Bien que rare, il arrive certainement que toutes les relations ancestrales ne soient pas remplies par des personnes uniques. Cela se produit, par exemple, lorsque des cousins secondaires ont des enfants.
une autre situation non-planaire peut se produire dans la situation des enfants de parents non-monogames. L'exemple le plus simple est celui de deux hommes et de deux femmes, en couple avec des enfants (donc au moins quatre). Vous ne pouvez pas étaler même les quatre paires de parents dans un rang sans lignes courbées.
ce ne sont que des exemples. Je suis sûr que vous découvrirez plus que vous travaillez sur votre algorithme. La vraie leçon ici est de modéliser explicitement la classe de relation que votre algorithme est capable d'établir et d'avoir du code de vérification dans l'algorithme pour détecter quand les données ne répondent pas à ces exigences.
la question que vous posez est beaucoup plus fondamentale. Vous avez des difficultés de base parce que vous avez besoin d'utiliser un profondeur - première traversée du graphe. C'est le (la plus facile) version complète de ce que signifie " jeter "par le haut" (dans un des commentaires). Ce n'est qu'un des nombreux algorithmes pour l'arbre transversal .
vous tracez un graphique dirigé avec (au moins) la notion implicite de rang. Le sujet est le rang 0; les parents sont le rang 1; les grands-parents au rang 2. (Après les mises en garde ci-dessus, le classement n'est pas toujours unique.) La plus grande partie de la superficie de ces graphiques est dans l'ascendance. Si vous n'étalez pas les noeuds de feuille d'abord, vous n'avez aucun espoir de réussir. L'idée est que vous disposez des noeuds avec le rang le plus élevé en premier, incorporant progressivement des noeuds de rang inférieur. Profondeur - première traversée est la façon la plus courante de le faire.
je traiterais ceci comme un algorithme de réécriture de graphe. La structure de base des données est un hybride de sous-graphes rendus et du graphe d'ascendance sous-jacent. Un rendu sous-graphe est un (1) un sous-arbre de le graphe entier avec (1a) un ensemble de progéniture, dont tous les ancêtres sont rendus et (2) une collection de données de rendu: positions des noeuds et des lignes, etc. L'état initial de l'hybride est l'ensemble du graphique et n'a pas rendu les sousgraphes. L'état final est un graphe Rendu entier. Chaque étape de l'algorithme convertit un ensemble d'éléments à la feuille limite de l'hybride graphique dans un (grand) rendus sous-graphe, en réduisant le nombre d'éléments dans l'hybride. À la fin il n'y a qu'un seul élément, le rendu graphique dans son ensemble.
comme vous utilisez déjà Family Echo , je vous suggère de regarder comment ils développent leur arbre généalogique en ligne, puisqu'ils semblent avoir résolu votre problème.
quand j'entre votre exemple de diagramme dans Family Echo, je peux construire un bel arbre qui semble être ce que vous cherchez sans cross over.
bien qu'ils soient en créant leurs diagrammes avec html et css, vous pouvez ajouter les gens à leurs diagrammes un par un et puis inspecter où les boîtes sont placées en termes de pixels gauche et haut de chaque élément.
si j'avais plus d'expertise en JavaScript, j'aurais essayé de créer un code pour répliquer ce que Family Echo fait, mais je crains que ce ne soit pas mon mojo.
vous devrez ajuster toutes les branches du noeud que vous affectez, chaque branche devra recalculer la position de ses noeuds, et chaque noeud devra être recalculé localement en atteignant les feuilles.Vous avez calculé une fois que les feuilles vont devoir recalculer tout le chemin à la marche arrière, tout cela de façon récursive. C'est comme un vrai arbre, quand on ajoute physiquement une branche au tronc ... les autres branches bougent seules pour laisser un peu d'Espace, toutes les feuilles sont automatiquement réinitialisées, donc vous avez imaginer. Et simuler ce processus dans votre diagramme. Traite chaque branche atteint chaque feuille, et recalcule jusqu'à recalculer les noeuds voisins modifiés. (un niveau au-dessus de vous a commencé) ce n'est pas facile ou un travail simple à faire.