Voronoi diagrams

The Voronoi diagram of a set of points (called sites, seeds) is a tessellation of the plane. Each cell of the tessellation is the locus of points that are closer to a specific site than to the other sites. Paths.js computes the Voronoi diagram of a given set of sites using the Euclidean metric to measure the distance between points. The algorithm used for the computation is the Fortune's algorithm, which is characterized by O(n * log(n)) complexity. Four points are added to the given input sites for the purpose of visualization. These points are placed sufficiently far from the given input sites in order not to affect the portion of the plot that is shown. The Voronoi graph can be used as follows:

var Voronoi = require('paths/voronoi');
var voronoi = Voronoi({
  data: [
    { city: 'London', latitude: 51.51, longitude: -0.13},
    { city: 'Milan', latitude: 45.47, longitude: 9.19},
    { city: 'Madrid', latitude: 40.42, longitude: -3.70},
    { city: 'Lyon', latitude: 45.76, longitude: 4.83},
    { city: 'Berlin', latitude: 52.52, longitude: 13.40},
  ],
  accessor: function(x) { return [x.latitude, x.longitude]; },
  compute: {
    color: function(i) { return somePalette[i]; }
  },
  xrange: [40, 55],
  yrange: [-5, 10],
  width:  500,
  height: 380,
});

Parameters:

• xrange, yrange: the ranges of the x and y axis shown by the plot.
• width, height: the desired width and height of the plot in terms of pixels. These values are used only for scaling the plot, while the actual size of the plot is defined by the HTML element that contains it. NB: it is advisable not to provide width and height smaller than the actual width and height of the container element. In fact, far away from the given width and height, the outer cells of the graph are truncated in an arbitrary way.
• data: contains an array with the data to plot. The precise form of the data is not important, because the actual value of the data will be extracted by the accessor function.
• accessor: a function that is applied to each datum in data to extract a numeric value.
• compute (optional): see the introduction.

The return value from Voronoi is an object with the properties curves and nodes, on which one can iterate to draw the cells and the sites. curves is an array of objects, each one having the properties line, item and index, where line contains the actual path object. nodes is an array of objects, each one having the properties point and item, representing the sites of the graph.