All examples By author By category About

nitaku

Label placement for Hilbert treemaps

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 for Hilbert regions). More general and rigorous approaches to the problem of finding the Largest Rectangle within a polygon can be found in Daniels 1997 (found in this StackOverflow post).

Using a web font (such in this case) can slightly alter the placement. It seems that if the font is not already loaded when the original text's bounding box is computed, a different font is used for the computation, resulting in a different bounding box.