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

We start by generating a random graph in the 2D unit cube, fixing the random seed to ensure reproducibility.

np.random.seed(0)
x, y = np.random.rand(2, 30)
g = ig.Graph(30)
g.vs["x"] = x
g.vs["y"] = y

Because we already set the x and y vertex attributes, we can use igraph.Graph.layout_auto() to wrap them into a igraph.Layout object.

layout = g.layout_auto()

Now we can calculate the delaunay triangulation using scipy’s scipy.spatial.Delaunay class:

delaunay = Delaunay(layout.coords)

Given the triangulation, we can add the edges into the original graph:

for tri in delaunay.simplices:
    g.add_edges([
        (tri[0], tri[1]),
        (tri[1], tri[2]),
        (tri[0], tri[2]),
    ])

Because adjacent triangles share an edge/side, the graph now contains some edges more than once. It’s useful to simplify the graph to get rid of those multiedges, keeping each side only once:

g.simplify()

<igraph.Graph object at 0x795f8b967e50>

Finally, plotting the graph gives a good idea of what the triangulation looks like:

fig, ax = plt.subplots()
ig.plot(
    g,
    layout=layout,
    target=ax,
    vertex_size=4,
    vertex_color="lightblue",
    edge_width=0.8
)
plt.show()