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

  • 1
    $\begingroup$ 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. $\endgroup$
    – Szabolcs
    May 23, 2014 at 19:42
  • $\begingroup$ Bigger question: in what format do you have the Delaunay triangulation? $\endgroup$
    – Szabolcs
    May 23, 2014 at 19:43
  • 2
    $\begingroup$ BTW you will soon be able to simply DelaunayMesh[pts]["AdjacencyMatrix"]. $\endgroup$
    – Szabolcs
    May 23, 2014 at 19:45
  • 2
    $\begingroup$ @Szabolcs soon for what values of soon? $\endgroup$
    – Yves Klett
    May 23, 2014 at 20:56
  • $\begingroup$ @Yves I don't know more than you. $\endgroup$
    – Szabolcs
    May 23, 2014 at 21:35

3 Answers 3


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


to obtain an adjacency matrix.

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

mesh = DelaunayMesh[points]
IGMeshCellAdjacencyMatrix[mesh, 0]

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

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


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}];

Load the undocumented Region context



mesh = DelaunayMesh[pts];

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

( matrix = AdjacencyMatrix[graph] ) // MatrixForm

Mathematica graphics


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"]
  • $\begingroup$ It doesn't work for me on v8.. Picture here. $\endgroup$
    – Öskå
    May 23, 2014 at 23:05
  • $\begingroup$ @Öskå. Hmmm. I don't have v8, but good to know. It works fine in v9.0.1 $\endgroup$
    – RunnyKine
    May 23, 2014 at 23:15
  • $\begingroup$ @Öskå, does the Region context work for you in v8? $\endgroup$
    – RunnyKine
    May 23, 2014 at 23:17
  • $\begingroup$ DelaunayMesh doesn't seem to work. here. Could you please set a SeedRandom and upload a picture of the Graph in the comments? :) $\endgroup$
    – Öskå
    May 23, 2014 at 23:19
  • $\begingroup$ @Öskå here. SeedRandom[2345] $\endgroup$
    – RunnyKine
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.