Nearest Neighbour Queries

One useful feature of Voronoi tessellations is that they can be used to obtain nearest neighbours, since by definition a Voronoi tile contains all points in the plane closest to the associated generator. This implies that finding a nearest neighbour is the same as a point location problem, meaning given a point p find the Voronoi tile P containing it. Here we give an example of how we can use triangulations or tessellations to find the nearest neighbour in the point set to a given point. We note that these same ideas could be applied for power diagrams, except that the metric used for defining distances is based on the power distance instead of the Euclidean distance (see the power diagram tutorial for more details); this is not demonstrated in this tutorial. First, we load in the packages we need.

using DelaunayTriangulation
using CairoMakie

Now we define the tessellation we will use for this example. The white points shown are the points that we will query.

points = [
    (-3.0, 7.0), (2.0, 6.0), (0.0, 3.0),
    (0.0, 0.0), (-5.0, 5.0), (-3.0, 1.0),
    (2.0, -3.0), (5.0, 5.0), (-4.0, 3.0),
]
tri = triangulate(points)
vorn = voronoi(tri)
p, q = (-2.0, 7.5), (0.0, 4.0)
fig, ax, sc = voronoiplot(vorn, markersize = 14)
scatter!(ax, [p, q], color = :white, strokecolor = :black, strokewidth = 2, markersize = 14)
fig

To get the nearest neighbour of a point, we use get_nearest_neighbour.

np = get_nearest_neighbour(vorn, p)

1

nq = get_nearest_neighbour(vorn, q)

3

We see that the nearest point in points to p is the first point, and to q it is the third point. We note that we could have also performed this query without constructing vorn directly, instead using tri:

np_tri = get_nearest_neighbour(tri, p)

1

nq_tri = get_nearest_neighbour(tri, q)

3

Both methods lead to the same results because they use the same algorithm.

Just the code

An uncommented version of this example is given below. You can view the source code for this file here.

using DelaunayTriangulation
using CairoMakie

points = [
    (-3.0, 7.0), (2.0, 6.0), (0.0, 3.0),
    (0.0, 0.0), (-5.0, 5.0), (-3.0, 1.0),
    (2.0, -3.0), (5.0, 5.0), (-4.0, 3.0),
]
tri = triangulate(points)
vorn = voronoi(tri)
p, q = (-2.0, 7.5), (0.0, 4.0)
fig, ax, sc = voronoiplot(vorn, markersize = 14)
scatter!(ax, [p, q], color = :white, strokecolor = :black, strokewidth = 2, markersize = 14)
fig

np = get_nearest_neighbour(vorn, p)

nq = get_nearest_neighbour(vorn, q)

np_tri = get_nearest_neighbour(tri, p)

nq_tri = get_nearest_neighbour(tri, q)

This page was generated using Literate.jl.