## make graph from Delaunay triangulation

Showing 1-4 of 4 messages
 make graph from Delaunay triangulation Tom 7/31/11 7:20 PM 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 Re: [networkx-discuss] make graph from Delaunay triangulation Aric Hagberg 8/1/11 4:55 AM On Sun, Jul 31, 2011 at 8:20 PM, Tom 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.Aricfrom scipy.spatial import Delaunayimport networkx as nx# nodes and positionsnodes = 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 nodesfor 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 graphG = nx.Graph(edges)pos = dict(zip(nodes,points))# drawimport matplotlib.pyplot as pltnx.draw(G,pos)plt.show() Re: make graph from Delaunay triangulation Tom 8/1/11 2:31 PM 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 wrote: Re: make graph from Delaunay triangulation Tom 8/1/11 5:00 PM 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() # --------------------------------------