Binary tree algorithm for treemap

[mackstann]

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:

• More testing with various datasets.
• It doesn't utilize the optional rounding function.
• Sticky mode doesn't work. stickify() is left unmodified and will surely break horribly if you try to use it.
• There's no way to select between the squarified and binary tree layouts -- I simply replaced squarify() with binarytree().
• The ratio option is no longer used but is still there in a vestigial form.
• I ported the change into d3.v2.js but none of the other files built by the Makefile (most notably, d3.v2.min.js) are updated.
• One last thing I just noticed: The Google algorithm seems to alternate vertical/horizontal at each step of its descent, but my algorithm picks the dimension that is currently larger and chooses that dimension to cut in half. This keeps the aspect ratio of the individual rectangles more square-like, but also results in some rows of nearly-identical repeated shapes, while Google's is more random looking. Maybe it could be configurable to work either way?

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

[mbostock]

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.)

[mackstann]

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.

[mbostock]

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!

[mbostock]

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.