/d3-voronoi-treemap

D3 plugin which computes a treemap based on a Voronoi tesselation

Primary LanguageJavaScriptBSD 3-Clause "New" or "Revised" LicenseBSD-3-Clause

d3-voronoi-treemap

This D3 plugin produces a Voronoï treemap. Given a convex polygon and nested weighted data, it tesselates/partitions the polygon in several inner cells which represent the hierarchical structure of your data, such that the area of a cell represents the weight of the underlying datum.

Because a picture is worth a thousand words:

square hexagon diamond circle

Available only for d3 v4, d3 v5 and d3 v6.

If you're interested on one-level map, take a look at the d3-voronoi-map plugin, which may be simpler to use (no need of a d3-hierarchy).

Context

D3 already provides a d3-treemap module which produces a rectangular treemap. Such treemaps could be distorted to fit shapes that are not rectangles (cf. Distorded Treemap - d3-shaped treemap).

This plugin allows to compute a treemap with a unique look-and-feel, where inner areas are not strictly aligned each others, and where the outer shape can be any hole-free convex polygons (squares, rectangles, pentagon, hexagon, ... any regular convex polygon, and also any non regular hole-free convex polygon).

The drawback is that the computation of a Voronoï treemap is based on a iteration/looping process. Hence, it requires some times, depending on the number and type of data/weights, the desired representativeness of cell areas.

Examples

Installing

If you use NPM, npm install d3-voronoi-treemap. Otherwise, load https://rawcdn.githack.com/Kcnarf/d3-voronoi-treemap/v1.1.0/build/d3-voronoi-treemap.js (or its d3-voronoi-treemap.min.js version) to make it available in AMD, CommonJS, or vanilla environments. In vanilla, you must load the d3-weighted-voronoi and d3-voronoi-map plugins prioir to this one, and a d3 global is exported:

<script src="https://d3js.org/d3.v6.min.js"></script>
<script src="https://rawcdn.githack.com/Kcnarf/d3-weighted-voronoi/v1.1.0/build/d3-weighted-voronoi.js"></script>
<script src="https://rawcdn.githack.com/Kcnarf/d3-voronoi-map/v2.1.0/build/d3-voronoi-map.js"></script>
<script src="https://rawcdn.githack.com/Kcnarf/d3-voronoi-treemap/v1.1.1/build/d3-voronoi-treemap.js"></script>
<script>
  var voronoiTreemap = d3.voronoiTreemap();
</script>

If you're interested in the latest developments, you can use the master build, available throught:

<script src="https://raw.githack.com/Kcnarf/d3-voronoi-treemap/master/build/d3-voronoi-treemap.js"></script>

TL;DR;

In your javascript, in order to define the tessellation:

function weightAccessor(d) {
  return d.weight; // computes the weight of one of your data; depending on your data, it may be 'd.area', or 'd.percentage', ...
}
var rootNode = d3.hierarchy(nestedData); // a d3-hierarchy of your nested data
rootNode.sum(weightAccessor); // assigns the adequate weight to each node of the d3-hierarchy

var voronoiTreemap = d3.voronoiTreemap().clip([
  [0, 0],
  [0, height],
  [width, height],
  [width, 0],
]); // sets the clipping polygon
voronoiTreemap(rootNode); // computes the weighted Voronoi tessellation of the d3-hierarchy; assigns a 'polygon' property to each node of the hierarchy

Then, later in your javascript, in order to draw cells:

var allNodes = rootNode.descendants();
d3.selectAll('path')
  .data(allNodes)
  .enter()
  .append('path')
  .attr('d', function (d) {
    // d is a node
    return d3.line()(d.polygon) + 'z'; // d.polygon is the computed Voronoï cell encoding the relative weight of your underlying original data
  })
  .style('fill', function (d) {
    return fillScale(d.data); // d.data is your original data
  });

Reference

API

# d3.voronoiTreemap()

Creates a new voronoiTreemap with the default configuration values and functions (clip, extent, size, convergenceRatio, maxIterationCount, minWeightRatio and prng).

# voronoiTreemap(root)

Computes the Voronoï treemap for the specified d3-hierarchy, where root is the root node of the hierarchy, assigning a polygon property on the root and its descendants. A polygon is represented as an array of points [x, y] where x and y are the point coordinates, a site field that refers to its site (ie. with x, y and weight retrieved from the original data), and a site.originalObject field that refers to the corresponding element in data. Polygons are open: they do not contain a closing point that duplicates the first point; a triangle, for example, is an array of three points. Polygons are also counterclockwise (assuming the origin ⟨0,0⟩ is in the top-left corner).

As others d3-hierarchy layouts (rectangular treemap, or circle packing), the Voronoï treemap layout considers the weight of a node to be the value propertyof that node. Hence, you must call root.sum before passing the hierarchy to the Voronoï treemap layout, in order to properly set the value property of each node (root, intermediates and leaves). For example, considering that your original nested data have leaves with a weight property, you must use rootNode.sum(function(d){ return d.weight; }).

# voronoiTreemap.clip([clip])

If clip is specified, sets the clipping polygon, , compute the adequate extent and size, and returns this layout . clip defines a hole-free convex polygon, and is specified as an array of 2D points [x, y], which must be (i) open (no duplication of the first D2 point) and (ii) counterclockwise (assuming the origin ⟨0,0⟩ is in the top-left corner). If clip is not specified, returns the current clipping polygon, which defaults to:

[
  [0, 0],
  [0, 1],
  [1, 1],
  [1, 0],
];

# voronoiTreemap.extent([extent])

If extent is specified, it is a convenient way to define the clipping polygon as a rectangle. It sets the extent, computes the adequate clipping polygon and size, and returns this layout. extent must be a two-element array of 2D points [x, y], which defines the clipping polygon as a rectangle with the top-left and bottom-right corners respectively set to the first and second points (assuming the origin ⟨0,0⟩ is in the top-left corner on the screen). If extent is not specified, returns the current extent, which is [[minX, minY], [maxX, maxY]] of current clipping polygon, and which defaults to:

[
  [0, 0],
  [1, 1],
];

# voronoiTreemap.size([size])

If size is specified, it is a convenient way to define the clipping polygon as a rectangle. It sets the size, computes the adequate clipping polygon and extent, and returns this layout. size must be a two-element array of numbers [width, height], which defines the clipping polygon as a rectangle with the top-left corner set to [0, 0] and the bottom-right corner set to [width, height] (assuming the origin ⟨0,0⟩ is in the top-left corner on the screen). If size is not specified, returns the current size, which is [maxX-minX, maxY-minY] of current clipping polygon, and which defaults to:

[1, 1];

# voronoiTreemap.convergenceRatio([convergenceRatio])

If convergenceRatio is specified, sets the convergence ratio, which stops computation when (cell area errors / (clip-ping polygon area) <= convergenceRatio. If convergenceRatio is not specified, returns the current convergenceRatio , which defaults to:

var convergenceRation = 0.01; // stops computation when cell area error <= 1% clipping polygon's area

The smaller the convergenceRatio, the more representative is the treemap, the longer the computation takes time.

# voronoiTreemap.maxIterationCount([maxIterationCount])

If maxIterationCount is specified, sets the maximum allowed number of iterations, which stops computation when it is reached, even if the convergenceRatio is not reached. If maxIterationCount is not specified, returns the current maxIterationCount , which defaults to:

var maxIterationCount = 50;

If you want to wait until computation stops only when the convergenceRatio is reached, just set the maxIterationCount to a large amount. Be warned that computation may take a huge amount of time, due to flickering behaviours in later iterations.

# voronoiTreemap.minWeightRatio([minWeightRatio])

If minWeightRatio is specified, sets the minimum weight ratio, which allows to compute the minimum allowed weight (= maxWeight * minWeightRatio). If minWeightRatio is not specified, returns the current minWeightRatio , which defaults to:

var minWeightRatio = 0.01; // 1% of maxWeight

minWeightRatio allows to mitigate flickerring behaviour (caused by too small weights), and enhances user interaction by not computing near-empty cells.

# voronoiTreemap.prng([prng])

If prng is specified, sets the pseudorandom number generator which is used when randomness is required (i.e. when setting intial random position of data/seeds). The given pseudorandom number generator must implement the same interface as Math.random and must only return values in the range [0, 1). If prng is not specified, returns the current prng , which defaults to Math.random.

Considering the same set of data, severall Voronoï treemap computations lead to disctinct final arrangements, due to the non-seedable Math.random number generator. If prng is set to a seedable PRNG which produces repeatable results, then several computations will produce the exact same final arrangement. This is useful if you want the same arrangement for distinct page loads/reloads. For example, using seedrandom:

<script src="//cdnjs.cloudflare.com/ajax/libs/seedrandom/2.4.3/seedrandom.min.js"></script>
<script>
  var mySeededPrng = new Math.seedrandom('my seed'); // (from seedrandom's doc) Use "new" to create a local prng without altering Math.random
  voronoiTreemap.prng(mySeededPrng);
</script>

You can also take a look at d3-random for random number generator from other-than-uniform distributions.

Dependencies

  • d3-voronoi-map.voronoiMap

Semantic Versioning

d3-voronoi-treemap attempts to follow semantic versioning and bump major version only when backwards incompatible changes are released.