New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Binary tree algorithm for treemap #653
Comments
Hey, this is cool! Sorry for the delay in commenting. I wasn't aware of the binary treemap algorithm. Is there a paper or similar that describes the algorithm? One possibility is that we could add a mode property to the treemap layout that lets you select the desired algorithm (which could default to "squarified", but also allow "binary" or "slice-and-dice"). We did something similar for the Protovis treemap implementation. If there's not much code sharing, another possibility is to make this a standalone d3 plugin. However, I suspect that there will be code sharing between this and the existing treemap / hierarchy layout, so I'm guessing it makes more sense to enable it as a mode flag. I'm a little unsure yet how to deal with sticky & ratio when you change the mode, though. I think it'd be fine to ignore the ratio flag and document that it's only observed by the "squarify" mode. Stickiness is trivially supported by the slice-and-dice layout algorithm, since the horizontal or vertical decision is independent of value. We'd need to figure out how to make stickiness work with the new binary algorithm. (It should be easy if we can record how the splits are made, similar to the existing squarify implementation.) |
Cool, I'm glad you like it! I wasn't able to find a paper or any actual description of the algorithm. I only found a mention of it on Wikipedia, which links to this page, which also mentions it: http://www.cs.umd.edu/hcil/treemap-history/index.shtml . It looks like there's a Java implementation available there, but I didn't look at it. The algorithm is really simple -- it just finds the closest-to-halfway midpoint in the dataset and cuts the rectangle into two, based on the position of that almost-midpoint. It then recurses into each half and repeats. It is a little extra confusing because there are two different recursions -- one to handle nested datasets, and one to implement the binary tree layout. It doesn't really share much code. The bulk of it just replaces the squarify() function. |
A few years late, but I’ve implemented this in d3-hierarchy for D3 4.0 as d3.treemapBinary, which you pass to the new treemap.tile method. You can see the implementation in d3/d3-hierarchy@492c5ca. Thanks for the suggestion! |
Turns out this is also referred to as “split treemaps”; see d3/d3-hierarchy#71 and Ordered and Unordered Treemap Algorithms and Their Applications on Handheld Devices by Engdahl. |
I love the simplicity and speed of d3's treemap -- I have several thousand nodes and it is far faster than jit or Google treemap -- but I found myself really preferring the binary tree layout algorithm, instead of the squarified algorithm, for my data. You can see an example of it in Google's treemap visualization: https://developers.google.com/chart/interactive/docs/gallery/treemap (here's a screenshot of it with my data, to give you an idea: http://i.imgur.com/clVB5.png ).
I've implemented this algorithm for d3 (screenshot of that [the gradients are unrelated]: http://i.imgur.com/3YIVs.png ), and want to contribute the code back to d3. However, after several intense days of getting it working, my brain is a bit fried and I want/need to move on to other parts of my project to get it done. Thus, it is not complete. The layout algorithm basically works, but here's what's left to do:
I apologize for the incomplete code dump, but I figured it was better than keeping it to myself entirely. Hopefully someone can make use of it, and just maybe, finish it up and get it incorporated into d3 proper.
Here's the branch (just one new commit): https://github.com/mackstann/d3/tree/binarytree_treemap
The text was updated successfully, but these errors were encountered: