Example 9 - Constructing the Voronoi diagram

The dual of a Delaunay triangulation is its Voronoi diagram. Stripy can efficiently calculate the voronoi points from a triangulation and, optionally, build the Voronoi regions for you.

Contents

• Voronoi points

• Voronoi regions

import numpy as np
import stripy
import matplotlib.pyplot as plt

%matplotlib inline

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 3
      1 import numpy as np
      2 import stripy
----> 3 import matplotlib.pyplot as plt
      5 get_ipython().run_line_magic('matplotlib', 'inline')

ModuleNotFoundError: No module named 'matplotlib'

import stripy as stripy

xmin = 0.0
xmax = 10.0
ymin = 0.0
ymax = 10.0
extent = [xmin, xmax, ymin, ymax]

spacingX = 0.5
spacingY = 0.5

## Set up a coarse mesh for visual clarity

mesh = stripy.cartesian_meshes.elliptical_mesh(extent, spacingX, spacingY)

fig = plt.figure(figsize=(10, 8), facecolor="none")

ax = fig.add_subplot(111, title="Delaunay triangulation")
ax.axis('off')
ax.triplot(mesh.x, mesh.y, mesh.simplices, c='LightGrey', zorder=1)
ax.scatter(mesh.x, mesh.y, c='C0', marker='.', zorder=2)

plt.show()

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[3], line 1
----> 1 fig = plt.figure(figsize=(10, 8), facecolor="none")
      3 ax = fig.add_subplot(111, title="Delaunay triangulation")
      4 ax.axis('off')

NameError: name 'plt' is not defined

Voronoi points

A voronoi point (or circumcentre) exists for every triangle in the mesh. They are calculated by finding a constant radius (the circumradius) that is shared between each point in the triangle. Depending on the mesh, some voronoi points will reside outside the area contained within a triangle.

To calculate the Voronoi points from the mesh, use the voronoi_points method. This method may optionally return the circumradius, signed triangle area, or aspect ratio for each voronoi point.

vx, vy = mesh.voronoi_points()


fig = plt.figure(figsize=(10, 8), facecolor="none")

ax = fig.add_subplot(111, title="Delaunay triangulation + Voronoi points")
ax.axis('off')
ax.triplot(mesh.x, mesh.y, mesh.simplices, c='LightGrey', zorder=1)
ax.scatter(mesh.x, mesh.y, c='C0', marker='.', zorder=2)
ax.scatter(vx, vy, c='C1', marker='*', zorder=3)

plt.show()

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[4], line 4
      1 vx, vy = mesh.voronoi_points()
----> 4 fig = plt.figure(figsize=(10, 8), facecolor="none")
      6 ax = fig.add_subplot(111, title="Delaunay triangulation + Voronoi points")
      7 ax.axis('off')

NameError: name 'plt' is not defined

Voronoi regions

Often it is desirable to obtain the corresponding region enclosed by voronoi points. We can easily find the line segments connecting each voronoi point by retrieving the neighbour simplices.

neighbours = mesh.neighbour_simplices()

circumcentres = np.column_stack([vx, vy])
voronoi_edges = circumcentres[neighbours]
voronoi_edges[neighbours == -1] = np.nan # remove edges at infinity


lines = []
lines.extend(zip(circumcentres, voronoi_edges[:,0,:]))
lines.extend(zip(circumcentres, voronoi_edges[:,1,:]))
lines.extend(zip(circumcentres, voronoi_edges[:,2,:]))

# Plot it
from matplotlib.collections import LineCollection

linesC = LineCollection(lines, edgecolor='k')

fig = plt.figure(figsize=(10, 8), facecolor="none")
ax = fig.add_subplot(111, title='Voronoi diagram')
ax.axis('off')
ax.scatter(mesh.x, mesh.y, c='C0', marker='.', zorder=2)
ax.scatter(vx, vy, c='C1', marker='*', zorder=3)
ax.add_collection(linesC)

plt.show()

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[6], line 2
      1 # Plot it
----> 2 from matplotlib.collections import LineCollection
      4 linesC = LineCollection(lines, edgecolor='k')
      6 fig = plt.figure(figsize=(10, 8), facecolor="none")

ModuleNotFoundError: No module named 'matplotlib'

Looks good! But in order to find which voronoi points belong to a region, we need to iterate through all of the triangles. Since each vertex in the Delaunay represents a voronoi “site”, we can accumulate all of the circumcentres into a list and sort them using voronoi_points_and_regions.

vx, vy, regions = mesh.voronoi_points_and_regions()


linesC = LineCollection(lines, edgecolor='k')

fig = plt.figure(figsize=(10, 8), facecolor="none")
ax = fig.add_subplot(111, title='Voronoi diagram')
ax.axis('off')
ax.scatter(mesh.x, mesh.y, c='C0', marker='.', zorder=2)
ax.scatter(vx, vy, c='C1', marker='*', zorder=3)
ax.add_collection(linesC)

# highlight specific region
r = 1
region = regions[r]

# iterate through region and connect up the points
for i in range(len(region)):
    i0 = region[i - 1]
    i1 = region[i]

    xx = [vx[i0], vx[i1]]
    yy = [vy[i0], vy[i1]]
    ax.plot(xx, yy, c='r', linewidth=5)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[7], line 4
      1 vx, vy, regions = mesh.voronoi_points_and_regions()
----> 4 linesC = LineCollection(lines, edgecolor='k')
      6 fig = plt.figure(figsize=(10, 8), facecolor="none")
      7 ax = fig.add_subplot(111, title='Voronoi diagram')

NameError: name 'LineCollection' is not defined