nitaku

This example uses python graph-tool to convert a tangled tree into a regular tree. A tangled tree is a tree with some nodes with multiple parents, or, more precisely, a Directed Acyclic Graph with a node identified as root, in which not too many nodes have multiple parents.

Starting from this example tangled tree rooted in the node A:

Two different methods are presented: a simple algorithm yielding one of the shortest tree covering all nodes, and a more complex one that returns one of the longest. In both cases, for each node, its distance from the root is computed. The difference is that the shortest tree algorithm uses the shortest distance (by invoking the corresponding function in graph-tool), while the ot

nitaku

A label placement algorithm for Hilbert treemaps. For each region, a label that do not overlap the boundaries is drawn. The label is placed inside the largest area rectangle that can be found within the region. Use the mouse to zoom and pan, and click the map to display the largest rectangle of each region.

The algorithm works in integer coordinates, and proceeds as follows: First, the X axis is scanned to find contiguous sequences of cells along the Y axis (tall boxes). Each box is then enlarged along X until it finds a boundary (even if a one-cell-wide hole is found). Then the process is repeated scanning the Y axis, producing wide boxes then enlarging them along Y.

The largest box is then chosed as the largest area rectangle (shown in yellow if you click on the map), that is used to fit the text's bounding box.

The implementation is very simplistic and unoptimized, and works only for polygonal regions composed of contiguous cells of a square tiling (as is the case fo

nitaku

Same as this example, but supporting the intersection of three regions. The code could be easily generalized to more regions.

nitaku

The label placement algorithm introduced here can be also used in treemaps built by using a Peano space-filling curve.

Peano regions always have a landscape (or square) orientation, yielding more horizontal labels than Hilbert treemaps.

nitaku

se

nitaku

Hilbert curves of even order cannot be overlapped with Hilbert curves of odd order (click the canvas to see it). This makes them somewhat problematic for Hilbert treemaps like the ones we showed in this and this examples.

According to our data cartography methodology, if a dataset is slightly changed, only a slight change should be reflected by the map. But, if we use Hilbert layouts, we can observe a disastrous change on an already full map if a single cell is added to it: the map will be flipped!

Peano curves are not affected by this problem (see here). A solution for fixing Hilbert curves is presented in this example.

nitaku

A stabilized version of a Hilbert curve, more suitable for Hilbert treemaps. Odd orders are rotated by 90 degrees and flipped along Y, making each curve overlappable to each other (click the canvas to see it).

Classical Hilbert curves of even order cannot be overlapped with Hilbert curves of odd order (see this example showing it). Peano curves are not affected by this problem (see here).

nitaku

A Peano space-filling curve drawn with an implementation of an L-system renderer. This is different from the other curve also called Peano by some.

This curve, named Peano at least on Wikipedia and in this article about L-systems, is also named Hilbert II (in this page).

The drawing of the line is animated using Mike Bostock's stroke dash interpolation.

nitaku

A Quadratic Gosper space-filling curve drawn with an implementation of an L-system renderer. L-system definition is taken from this examples.

The drawing of the line is animated using Mike Bostock's stroke dash interpolation.

nitaku

A sample FASS curve from this book about L-systems. FASS stands for space-Filling, self-Avoiding, Simple, self-Similar. Hilbert, Peano and Gosper curves are all FASS.