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?

Answer 1

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]

Answer 2

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

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

Answer 3

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.