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 <t.r.eth...@gmail.com> wrote: Maybe you can use scipy.spatial.Delaunay? Here is some untested code. from scipy.spatial import Delaunay # build graph |

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 <ahagb...@gmail.com> 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() # -------------------------------------- |