Is there a way to convert a Delaunay triangulation into a Graph structure, so that one can generate an adjacency matrix of the triangulation?

• You don't need to go through a graph. Once you have the Delaunay triangulation as a set of point-index pairs, you can SparseArray@Thread[pairs -> 1] assuming the indices start from 1. Commented May 23, 2014 at 19:42
• Bigger question: in what format do you have the Delaunay triangulation? Commented May 23, 2014 at 19:43
• BTW you will soon be able to simply DelaunayMesh[pts]["AdjacencyMatrix"]. Commented May 23, 2014 at 19:45
• @Szabolcs soon for what values of soon? Commented May 23, 2014 at 20:56
• @Yves I don't know more than you. Commented May 23, 2014 at 21:35

In version 10, which is at the moment publicly accessible through the Programming Cloud, you can simply use:

DelaunayMesh[points]["AdjacencyMatrix"]


The IGraph/M package has support for converting meshes into matrices. This problem would be solved by

mesh = DelaunayMesh[points]


0 means the adjacency relation of 0-dimensional mesh cells, i.e. points.

There is also a function for directly constructing the Delaunay graph:

IGDelaunayGraph[points]


Since you want to go from DelaunayTriangulation to Graph to AdjacencyMatrix, how about the following (works in version 9.0.1)

pts = RandomReal[4, {25, 2}];


GraphicsRegionRegionInit[];


Then,

mesh = DelaunayMesh[pts];

graph = Graph @ MeshTopologyGraph[mesh][[1]];

( matrix = AdjacencyMatrix[graph] ) // MatrixForm


OR

pairs = MeshTopologyGraph[mesh][[1]] /. Rule -> List

matrix = Normal @ SparseArray[Thread[pairs -> 1]]


Surprise , surprise as suggested by Szabolcs (only, you can do it now in v9) but with a little twist, you can get it directly:

matrix = mesh[[1]]["AdjacencyMatrix"]

• It doesn't work for me on v8.. Picture here.
– Öskå
Commented May 23, 2014 at 23:05
• @Öskå. Hmmm. I don't have v8, but good to know. It works fine in v9.0.1 Commented May 23, 2014 at 23:15
• @Öskå, does the Region context work for you in v8? Commented May 23, 2014 at 23:17
• DelaunayMesh doesn't seem to work. here. Could you please set a SeedRandom and upload a picture of the Graph in the comments? :)
– Öskå
Commented May 23, 2014 at 23:19
• @Öskå here. SeedRandom[2345] Commented May 24, 2014 at 0:03

These days, one would do something like the following:

pts = RandomReal[1, {18, 2}];
dm = DelaunayMesh[pts];
mcg = MeshConnectivityGraph[dm]


and then evaluate AdjacencyMatrix[mcg] if you want to see the corresponding adjacency matrix.