Convert DelaunayTriangulation-> Graph->AdjacencyMatrix

Question

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. — Szabolcs
– Szabolcs, Commented May 23, 2014 at 19:42
Bigger question: in what format do you have the Delaunay triangulation? — Szabolcs
– Szabolcs, Commented May 23, 2014 at 19:43
BTW you will soon be able to simply DelaunayMesh[pts]["AdjacencyMatrix"]. — Szabolcs
– Szabolcs, Commented May 23, 2014 at 19:45

Szabolcs · Accepted Answer · 2022-05-28 11:08:20Z

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

DelaunayMesh[points]["AdjacencyMatrix"]

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:

IGDelaunayGraph[points]

Community · Accepted Answer · 2017-04-13 12:55:36Z

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

Graphics`Region`RegionInit[];

Then,

mesh = DelaunayMesh[pts]; graph = Graph @ MeshTopologyGraph[mesh][[1]]; ( matrix = AdjacencyMatrix[graph] ) // MatrixForm

Mathematica graphics

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"]

@Öskå. Hmmm. I don't have v8, but good to know. It works fine in v9.0.1 — RunnyKine
– RunnyKine, Commented May 23, 2014 at 23:15
DelaunayMesh doesn't seem to work. here. Could you please set a SeedRandom and upload a picture of the Graph in the comments? :) — Öskå
– Öskå, Commented May 23, 2014 at 23:19

J. M.'s missing motivation · Accepted Answer · 2022-05-27 23:13:02Z

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.

3 Answers 3