One of the most common queries when working with maps is the nearest neighbour query. This blog post will use Voronoi Diagrams to explain more regarding the nearest neighbour query.

Below is an example of a Voronoi diagram generated using d3.js. One of the good use cases of a voronoi diagram in real-life applications would be where would be finding a place to build emergency services. This place should have the most number of neighbouring regions. For example, if you click on the region in the Voronoi diagram below, you can see how many regions in which it would consider this region to be its neighbour. The diagram is randomly generated based on a number of points and thus every refresh of this page will show a different Voronoi diagram.

Fig 1. Voronoi Diagram generated with 30 random points

The codes to create this diagram are as follows :-

const createVoronoi = () => {
  const width = 600;
  const height = 600;
  const vertices = d3.range(30).map(function (d) {
    return [Math.random() * width, Math.random() * height];
  });

  const delaunay = d3.Delaunay.from(vertices);
  const voronoi = delaunay.voronoi([0, 0, width, height]);
  let svg = d3.select("#canvas").append("svg").attr("viewBox", `0 0 600 600`);

  const mesh = svg
    .append("path")
    .attr("fill", "none")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", voronoi.render());

  const bounds = svg
    .append("path")
    .attr("fill", "none")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", voronoi.renderBounds());

  const points = svg
    .append("path")
    .attr("fill", "black")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", delaunay.renderPoints());
};

Example of a query

I will now re-use my data set of point from an earlier blog entry and I will generate the voronoi diagram. Basically, I would use a query point as well to find out the nearest neighbour and the surrounding neighbours. The figure below shows that the d3-delaunay provides a simple functions that allows you to find the point in which is the closest to the query point. This is done by using delaunay.find(). So if you are inside the blue region, your closest point would be the point inside the blue region.

It’s surrounding neighbours could then be easily obtained once you have this point by using delaunay.neighbor() and passing the result of the first find function. So, the regions which are in teal would be the neighbours of the region in blue. All the other regions would be coloured in green. This simple data structure would allow you to easily obtain the nearest neighbour. However, of course, there is also the importance of the build time, insertion time and removal time as well.

Fig 2. Voronoi Diagram for a NN query.

The codes to create this diagram are as follows
const queryExample = () => {
  let points = [
    [40, 74],
    [34, 118],
    [41, 87],
    [44, 93],
    [39, 104],
    [32, 96],
    [47, 122],
    [42, 71],
  ];

  // Function to transform the points so that it would work on the grid
  const transform = (point) => {
    return [(point[0] / 90) * 500, (point[1] / 180) * 500];
  };

  let transformed = [];

  points.forEach((element) => {
    transformed.push(transform(element));
  });

  const delaunay = d3.Delaunay.from(points);
  const voronoi = delaunay.voronoi([0, 0, 500, 500]);

  // Call the draw Voronoi function.
  drawVoronoi("#exampleQuery", transformed);
};

const drawVoronoi = (id, vertices, color) => {
  const width = 500,
    height = 500;

  const delaunay = d3.Delaunay.from(vertices);
  const voronoi = delaunay.voronoi([0, 0, width, height]);
  let svg = d3.select(id).append("svg").attr("viewBox", `0 0 500 500`);

  const mesh = svg
    .append("path")
    .attr("fill", "none")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", voronoi.render());

  const bounds = svg
    .append("path")
    .attr("fill", "none")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", voronoi.renderBounds());

  // Find the closest point to this coordinate.
  const ans = delaunay.find(40, 73);
  const neighbours = delaunay.neighbors(ans);
  for (const iterator of neighbours) {
    renderCell(svg, voronoi, iterator, d3.schemeTableau10[3]);
  }

  renderCell(svg, voronoi, ans, d3.schemeTableau10[0]);
  const points = svg
    .append("path")
    .attr("fill", "black")
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", delaunay.renderPoints());
};

const renderCell = (svg, voronoi, index, color) => {
  svg
    .append("path")
    .attr("fill", color)
    .attr("stroke", "#ccc")
    .attr("stroke-width", 1)
    .attr("d", voronoi.renderCell(index));
};

Lessons from this blog post.

  • The learning curve for d3.js is pretty insane.
  • Voronoi are pretty easy using d3.
  • Generators can be iterated using the for...of construct. MDN link
  • There is a way to make SVG responsive. Refer this post.