Delaunay Triangulation ¶
Delaunay Triangulation¶
This example demonstrates how to calculate the Delaunay triangulation of an input graph. We start by generating a set of points on a 2D grid using random numpy
arrays and a graph with those vertex coordinates and no edges.
import numpy as np
from scipy.spatial import Delaunay
import igraph as ig
import matplotlib.pyplot as plt
# Generate a random graph in the 2D unit cube
np.random.seed(0) # To ensure reproducibility
x, y = np.random.rand(2, 30)
g = ig.Graph(30)
g.vs['x'] = x
g.vs['y'] = y
We then use SciPy’s Delaunay function to generate the triangles, and then loop through them to add them back into our original graph. We make sure to simplify the graph afterwards to remove multiple edges caused by triangles sharing a side.
# Calculate the delaunay triangulation, and add the edges into the original graph
coords = g.layout_auto().coords
delaunay = Delaunay(coords)
for tri in delaunay.simplices:
g.add_edges([
(tri[0], tri[1]),
(tri[1], tri[2]),
(tri[0], tri[2]),
])
g.simplify()
Finally, we display the graph:
# Plot the graph
fig, ax = plt.subplots()
ig.plot(
g,
target=ax,
vertex_size=0.04,
vertex_color="lightblue",
edge_width=0.8
)
plt.show()
Our output looks like this:

The Delaunay triangulation¶
Advanced: Improving plotting style¶
Sometimes, we would like to emphasise the actual triangles generated by the Delaunay triangulation. We’ll add in some triangles and color them according to their y coordinate.
# Plot the triangles
fig, ax = plt.subplots()
palette = ig.GradientPalette("midnightblue", "lightblue", 100)
for tri in delaunay.simplices:
# get the points of the triangle
tri_points = [delaunay.points[tri[i]] for i in range(3)]
# calculate the vertical center of the triangle
center = (tri_points[0][1] + tri_points[1][1] + tri_points[2][1]) / 3
# draw triangle onto axes
poly = plt.Polygon(tri_points, color=palette.get(int(center*100)))
ax.add_patch(poly)
We then plot the original graph edges on top:
# Plot the graph on top
ig.plot(
g,
target=ax,
vertex_size=0.0,
edge_width=0.2,
edge_color="white",
)
plt.show()
The final output looks like this:

The Delaunay triangulation, with colored triangles.¶