Animating Family Trees, a la Pachinko

In musing on how a family tree is kind of like Pachinko, I wondered if this could be animated somewhat like a Pachinko machine in the family tree visualization I have been playing with (available at https://learnforeverlearn.com/ancestors).

I took some first steps towards this by pulling out the Bezier curve parameters d3 is generating for the links between nodes, coupled with Particle in Cell's notes on computing the intersection between Bezier curves and a line , to make some first steps towards a Pachinko-like animation effect. Some details on this implementation are at the bottom of this note.

A few youtube videos demonstrating this are below. You can also go directly to the interactive visualization with the tree for Charles II of Spain automatically loaded via this link, and clicking the "Do Pachinko" button.

An animation in time of my family tree

An animation of pedigree collapse in the family tree of the British Monarchy
(direct link to this tree is at
https://learnforeverlearn.com/ancestors/?file=royal92.txt

While I still need to play with the timing and smoothness, it is nevertheless interesting to watch the animations play over and over, reflecting on the huge number of things that had to happen (or not happen) through the centuries to result in me being here today.

Equations to be Solved to Find the Coordinates of the Animated Circles

Shown below is an example of a curve displayed on the screen and the svg path generated by d3:

${\bf P_0}$ is the center of the circle for the parent, and ${\bf P_3}$ is the center of the circle for the child. The C stuff in there for the "d" attribute contains the cubic B├ęzier commands. The equation for the thicker blue curve is given by
$${\bf{r}}(t) = {(1-t)}^3 {\bf P_0} + 3{(1-t)}^2 t {\bf P_1} + 3{(1-t)} t^2 {\bf P_2} + t^3 {\bf P_3}, \ t \in [0,1]$$ Placing a circle on this curve at a given year $\hat{y}$ (i.e., height) requires finding the $\hat{t}$ so that $$\begin{eqnarray} \hat{y} & = & \text{y-coordinate of } {\bf{r}}(\hat{t}) \\ & = & \text{y-coordinate of } {(1-\hat{t})}^3 {\bf P_0} + 3{(1- \hat{t})}^2 \hat{t} {\bf P_1} + 3{(1-\hat{t})} \hat{t}^2 {\bf P_2} + \hat{t}^3 {\bf P_3} \end{eqnarray} $$
and then using that $\hat{t}$ to find the $x$ coordinate $\hat{x}$ of the intersection. The center of the animated circle is then $(\hat{x},\hat{y})$. The cubic equation can be solved exactly (some preprocessing is done using the parent and child birth years to ensure that the line at year $y$ passes through the curve) - but there's some potential tedium dealing with multiple roots. The root-finding implementation in this visualization, from Particle in Cell, is originally from Stephen Schmitt (this was apparently on a Verizon personal web space site that no longer exists).

There are optimizations I need to address with respect to quickly finding the paths intersecting a given point in time, but it seems to work ok on small to moderately-sized trees.

The Genetic Pachinko for You and Me

In looking for other famous family trees, I came across someone who had compiled a tree for Winston Churchill with more than 6000 people in it. He graciously sent me a GEDCOM file of this tree, and I have included it as one of the samples in the (d3) family tree visualization project I am playing with. A screenshot is below. I had to cull people born before about 1300 because of (apparent) needed optimizations in the processing steps. It's kind of a mosh pit prior to 1300, anyway - the "widest point of the Ancestor Cone happens for most of us around 1200AD" (info via Tim Urban's awesome article on ancestors/pedigree collapse).

Visualization of Winston Churchill's Family Tree
GEDCOM file courtesy T. Dowling.
Interactive Visualization available at
https://learnforeverlearn.com/ancestors

(Better) Handling of Pedigree Collapse in a D3 Family Tree Visualization

I have been playing with building a d3.js family tree visualization (available at https://learnforeverlearn.com/ancestors), where you can load your own GEDCOM family tree file, or explore prepackaged sample trees for some famous folks. The other day I realized that I was not really handling pedigree collapse properly under the hood. Visually, things worked, but the calculations related to "duplicate" people in the tree were not right. I needed to more properly keep track of the individual paths between nodes in order to tabulate duplicate folks. In doing this, it also made it easy to dynamically highlight the paths between a person in the tree and the "root" person when the user hovers on a person in the tree. A screenshot of the updated visualization is below (for the poor pedigree collapse "champion" Charles II of Spain).

The Family Braid for Charles II of Spain,
highlighting the different ways Charles V was related to him.
Charles V was his great-great-great-great grandfather,
his great-great-great grandfather (twice),
and his great-great grandfather
(direct link to this tree in the visualization)

Popular Posts