make graph from Delaunay triangulation

[Tom]

Given a set of points in space with coordinates of x and y, I would
like to create a graph in NetworkX that is the edges of the triangles
formed by a Delaunay triangulation of those points.

I'm having some trouble figuring out how to do this, but it strikes me
as something that should be fairly simple, so perhaps someone may have
done this before?

Any help would be much appreciated.

Tom

[Aric Hagberg]

On Sun, Jul 31, 2011 at 8:20 PM, Tom <t.r.eth...@gmail.com> wrote:
> Given a set of points in space with coordinates of x and y, I would
> like to create a graph in NetworkX that is the edges of the triangles
> formed by a Delaunay triangulation of those points.
>
> I'm having some trouble figuring out how to do this, but it strikes me
> as something that should be fairly simple, so perhaps someone may have
> done this before?

Maybe you can use scipy.spatial.Delaunay?

Here is some untested code.
Aric

from scipy.spatial import Delaunay
import networkx as nx
# nodes and positions
nodes = list('abcde')
points = [(0,0),(7,7),(5,5),(1,7),(3,4)]
t = Delaunay(points)
edges = []
m = dict(enumerate(nodes)) # mapping from vertices to nodes
for i in range(t.nsimplex):
edges.append( (m[t.vertices[i,0]], m[t.vertices[i,1]]) )
edges.append( (m[t.vertices[i,1]], m[t.vertices[i,2]]) )
edges.append( (m[t.vertices[i,2]], m[t.vertices[i,0]]) )
print edges

# build graph
G = nx.Graph(edges)
pos = dict(zip(nodes,points))
# draw
import matplotlib.pyplot as plt
nx.draw(G,pos)
plt.show()

[Tom]

Great, yes! I haven't tested the code, but I can see where you are
going here, and that should work perfectly for me.

Many thanks for this Aric - and indeed for putting together NetworkX
which is excellent!

Tom

On Aug 1, 11:55 pm, Aric Hagberg <ahagb...@gmail.com> wrote:

[Tom]

Just to follow up on this, I made some slight changes, as the code
Aric provided didn't account for duplicate edges. So I have compiled
the edges as a set (sorting the index of the points first) so that
duplicated edges are not included, and then converted the set to a
list in order to create the graph.

My code is below in case it is useful for anyone else.

Tom

# --------------------------------------

# import point data as xy coordinates
points = [(0,0),(0,1),(2,2),(3,4),(4,3)]

# --------------------------------------

# make a Delaunay triangulation of the point data
import scipy.spatial
delTri = scipy.spatial.Delaunay(points)

# create a set for edges that are indexes of the points
edges = set()
# for each Delaunay triangle
for n in xrange(delTri.nsimplex):
# for each edge of the triangle
# sort the vertices
# (sorting avoids duplicated edges being added to the set)
# and add to the edges set
edge = sorted([delTri.vertices[n,0], delTri.vertices[n,1]])
edges.add((edge[0], edge[1]))
edge = sorted([delTri.vertices[n,0], delTri.vertices[n,2]])
edges.add((edge[0], edge[1]))
edge = sorted([delTri.vertices[n,1], delTri.vertices[n,2]])
edges.add((edge[0], edge[1]))

# --------------------------------------

# make a graph based on the Delaunay triangulation edges
import networkx as nx
graph = nx.Graph(list(edges))
print(graph.edges())

# --------------------------------------

# plot graph
import matplotlib.pyplot as plt
pointIDXY = dict(zip(range(len(points)), points))
nx.draw(graph, pointIDXY)
plt.show()

# --------------------------------------

[OAN]

Even many years later I found this very helpful. Thank you, Tom and Aric