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));};Benefits of Using MDX
This post demonstrates the power of MDX (Markdown + JSX) for blog posts:
- Direct Component Import: Astro components can be imported and used directly in the content
- Interactive Content: Rich, interactive demos embedded seamlessly in text
- Better Developer Experience: TypeScript support, better tooling, and cleaner code
- Performance: Astro islands ensure only necessary JavaScript is loaded
- Flexibility: Mix static content with dynamic components as needed