5
$\begingroup$

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

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

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.

$\endgroup$
4
$\begingroup$

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"]
$\endgroup$
8
  • $\begingroup$ It doesn't work for me on v8.. Picture here. $\endgroup$ – Öskå May 23 '14 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 '14 at 23:15
  • $\begingroup$ @Öskå, does the Region context work for you in v8? $\endgroup$ – RunnyKine May 23 '14 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 '14 at 23:19
  • $\begingroup$ @Öskå here. SeedRandom[2345] $\endgroup$ – RunnyKine May 24 '14 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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