Edge crossing with Reingold-Tilford radial tree layout #973

Closed
adriaanbaelus opened this Issue Dec 20, 2012 · 2 comments

Comments

Projects
None yet
2 participants

Disclaimer: This is my first time using d3, or doing any real data visualization, so please feel free to correct me or point me to documentation if this is incorrect or trivial.

While playing around with the radial tree layout, I've noticed in some edge cases the links cross. I'm not sure if this is a bug or not. According to http://hci.stanford.edu/courses/cs448b/f09/lectures/CS448B-20091021-GraphsAndTrees.pdf Reingold-Tilford shouldn't have edge crossings, but I'm not sure if that's a reliable source?

An example of what I am talking about: http://bl.ocks.org/4344931
I would've expected that same layout, but with child B at 180° opposite to child A.

If this behaviour is to be expected from the algorithm, is there some way to take this particular situation into account (perhaps by modifying the separation function)?

It just occurred to me the crossing links are probably due to the radial layout, not the algorithm itself (i.e. if this was a top-down tree, the links wouldn't cross). My apologies for the confusion.

I'd still be interested to hear if there is a straightforward solution to this particular case, though!

Owner

mbostock commented Jan 23, 2013

Right, this is the expected behavior. The issue in particular is that d3.svg.diagonal is using Béziers in Cartesian coordinates. If you wanted to keep this layout but strictly avoid edge crossing, you’d need to use curves in polar coordinates, which would be Archimedean spirals (related #700). This is actually quite tricky because you need to decompose the spiral into multiple Bézier or linear segments, since SVG doesn’t natively support spirals.

A much simpler in this case is to limit the angular breadth of the tree when you have a small number of nodes, e.g., spanning 180° rather than 360°.

mbostock closed this Jan 23, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment