d3-voronoi-map

This D3 plugin produces a Voronoï map (i.e. one-level treemap). Given a convex polygon and weighted data, it tesselates/partitions the polygon in several inner cells, such that the area of a cell represents the weight of the underlying datum.

Because a picture is worth a thousand words:

Available for d3 v4 and d3 v5.

If you're interested on multi-level treemap, which handle nested/hierarchical data, take a look at the d3-voronoi-treemap plugin.

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 map 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ï map 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

• The Individual Costs of Being Obese in the U.S. (2010), a remake of HowMuch.net's post

Installing

Load https://rawgit.com/Kcnarf/d3-voronoi-map/master/build/d3-voronoi-map.js (or its d3-voronoi-map.min.js version) to make it available in AMD, CommonJS, or vanilla environments. In vanilla, you must load the d3-weighted-voronoi plugin prior to this one, and a d3 global is exported:

<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://raw.githack.com/Kcnarf/d3-weighted-voronoi/master/build/d3-weighted-voronoi.js"></script>
<script src="https://raw.githack.com/Kcnarf/d3-voronoi-map/master/build/d3-voronoi-map.js"></script>
<script>
  var voronoiMap = d3.voronoiMap();
</script>

TL;DR;

In your javascript, in order to define the tessellation:

var voronoiMap = d3.voronoiMap()
  .weight(function(d){ return weightScale(d); }           // set the weight accessor
  .clip([[0,0], [0,height], [width, height], [width,0]])  // set the clipping polygon

var res = voronoiMap(data); // compute the weighted Voronoi tessellation; returns {polygons, iterationCount, convergenceRatio}
var cells = res.polygons

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

d3.selectAll('path')
  .data(cells)
  .enter()
  .append('path')
  .attr('d', function(d) {
    return cellLiner(d) + 'z';
  })
  .style('fill', function(d) {
    return fillScale(d.site.originalObject);
  });

Reference

• based on Computing Voronoï Treemaps - Faster, Simpler, and Resolution-independent
• https://github.com/ArlindNocaj/power-voronoi-diagram for a Java implementation

API

# d3.voronoiMap()

Creates a new voronoiMap with the default accessors and configuration values (weight, clip, convergenceRatio, maxIterationCount, minWeightRatio, prng, initialPosition, and initialWeight).

# voronoiMap(data)

Computes the Voronoï map for the specified data weights.

Returns a hash where hash.polygons is a sparse array of polygons clipped to the clip-ping polygon, one for each cell (each unique input point) in the diagram. Each 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). Furthermore, hash.iterationCount is the number of iterations required to compute the resulting map, and hash.convergenceRatio is the final convergence ratio (ie. cell area errors / area of the clip-ping polygon).

# voronoiMap.weight([weight])

If weight-accessor is specified, sets the weight accessor. If weight is not specified, returns the current weight accessor, which defaults to:

function weight(d) {
  return d.weight;
}

# voronoiMap.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]];

# voronoiMap.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 defaults to:

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

# voronoiMap.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 defaults to:

[1, 1];

# voronoiMap.convergenceRatio([convergenceRatio])

If convergenceRatio is specified, sets the convergence ratio, which stops computation when (cell area errors / clipping 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 map, the longer the computation takes time.

# voronoiMap.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.

# voronoiMap.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.

# voronoiMap.prng([prng])

If prng is specified, sets the pseudorandom number generator which is used when randomness is required (e.g. in d3.voronoiMapInitialPositionRandom(), cf. initialPosition). 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ï map computations lead to disctinct final arrangements, due to the non-seedable Math.random default number generator. If prng is set to a seedable pseudorandom number generator 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 pprng without altering Math.random
  voronoiMap.prng(myseededprng);
</script>

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

# voronoiMap.initialPosition([initialPosition])

If initialPosition is specified, sets the initial coordinate accessor. The accessor is a callback wich is passed the datum, its index, the array it comes from, and the current d3-voronoi-map. The accessor must provide an array of two numbers [x, y] inside the clipping polygon, otherwise a random initial position is used instead. If initialPosition is not specified, returns the current accessor, which defaults to a random position policy which insure to randomly pick a point inside the clipping polygon.

A custom accessor may look like:

function precomputedInitialPosition(d, i, arr, voronoiMap) {
  return [d.precomputedX, d.precomputedY];
}

Furthermore, two predefined policies are available:

• the random policy, available through d3.voronoiMapInitialPositionRandom(), which is the default intital position policy; it uses the specified prng, and may produce repeatable arrangement if a seeded random number generator is defined;
• the pie-based policy, available through d3.voronoiMapInitialPositionPie() which initializes positions of data along an inner circle of the clipping polygon, in an equaly distributed counterclockwise way (reverse your data to have a clockwise counterpart); the first datum is positioned at 0 radian (i.e. at right), but this can be customized through the d3.voronoiMapInitialPositionPie().startAngle(<yourFavoriteAngleInRad>) API; the name of this policy comes from the very first iteration which looks like a pie;

You can take a look at these policies to define your own complex initial position policies/accessors.

# voronoiMap.initialWeight([initialWeight])

If initialWeight is specified, sets the initial weight accessor. The accessor is a callback wich is passed the datum, its index, the array it comes from, and the current d3-voronoi-map. The accessor must provide a positive amount. If initialWeight is not specified, returns the current accessor, which defaults to initialize all sites with the same amount (which depends on the clipping polygon and the number of data):

A custom accessor may look like:

function precomputedInitialWeight(d, i, arr, voronoiMap) {
  return d.precomputedWeight;
}

Furthermore, the default half average area policy is available through d3.voronoiMapInitialWeightHalfAverageArea().

Considering a unique clipping polygon where you want to animate the same data but with slightly different weights (e.g., animate according to the time), this API combined with the initialPosition API allows you to maintain areas from one set to another:

• first, compute the Voronoï map of a first set of data
• then, compute the Voronoï map of another set of data, by initilizing sites to the final values (positions and weights) of first Voronoï map

Dependencies

• d3-polygon.{polygonCentroid, polygonArea, polygonContains}
• d3-weighted-voronoi.weightedVoronoi

Testing

In order to test the code

git clone https://github.com/Kcnarf/d3-voronoi-map.git
[...]
yarn install
[...]
yarn test