4
$\begingroup$

I am new to Mathematica and I am currently in need of some help with creating a neighboring list of triangles for a given triangulation and finding the path to the triangle containing the random point and constructing a tile. So basically, this problem involves the Delaunay Triangulation. I can generate the triangles usingDelaunayMesh but I can't find the neighboring triangles, the path to the triangle containing the random point, and construct the tile. This is what I have so far.

(* Number of data points *)
numpts = 5;
(* Test data set *)
pts = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0.3, 0.4}};
dmesh = DelaunayMesh[pts];
(* Extract the triangle list from the Delaunay triangulation *)
tris = MeshCells[dmesh, 2];
numtris = Length[tris];
(* This demonstrates how to access the pts from the tris list *)
Print["Number of triangles numtris = ", numtris];
Do[
  Print["Tri ", i,
   " v1=", pts[[tris[[i, 1, 1]]]],
   " v2=", pts[[tris[[i, 1, 2]]]],
   " v3 = ", pts[[tris[[i, 1, 3]]]]],
  {i, 1, numtris}
  ];
(* Data structure to hold neighbor data *)
nghbrs = Table[{0, 0, 0}, {i, 1, numtris}];

I want to use do loops to find the neighboring list of triangles and the path but I don't know what to enter. Can anyone please help me by showing me what code (I would prefer simple coding as I am still new to this programming language) to enter in the do loops? I would definitely appreciate all the help I can get. Thank you.

$\endgroup$
4
$\begingroup$

See here. What you are looking for is TNT = CellAdjacencyLists[dmesh, 2, 2]. TNT[[i]] contains the list of all triangles neighboring triangle i (in the sense that they share an edge).

You can also create a graph G = CellAdjacencyGraph[dmesh, 2, 2] with the triangles' indices as vertices and with an edge between two vertices if and only if the respective triangles are neighbors. You can find the shortest path between the ith and jth triangle with FindShortestPath[G,i,j].

See also Chip Hurst's answer to the same post.

conn = dmesh["ConnectivityMatrix"[2, 1]];
A = conn.Transpose[conn]

It gives you the triangle-triangle-adjacency matrix A; the neighbor lists can be obtained with TNT = A["AdjacencyLists"] and the graph with G = AdjacencyGraph[A, VertexLabels -> "Name"].

$\endgroup$
  • 1
    $\begingroup$ Henrik Schumacher, I have tried to use Chip Hurst’s code but it doesn’t give me the neighbor lists in the structure that I have provided. Can you possibly show me how to get the neighbor lists to be in the structure that I provide? $\endgroup$ – J.Kwan Apr 24 '18 at 22:52

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.