I have a MeshRegion R and I want to extract all pairs of adjacent faces efficiently. The way that I've been computing this is demonstrated below:

R = DiscretizeRegion[Sphere[]];
faces = MeshCells[R, 2, "Multicells" -> True][[1, 1]];
adj = Select[Subsets[faces, {2}],Length[Intersection[#[[1]], #[[2]]]] == 2 &];

Of course, this is not very efficient since I explicitly construct all pairs of faces and then filter them by requiring that they have both contain two of the same vertices. Any thoughts on how I could compute the same thing efficiently?


With Szabolcs' IGraphM package that's super easy and fast (1000 times faster for your given example):

R = DiscretizeRegion[Sphere[]];

pairs = UpperTriangularize[IGMeshCellAdjacencyMatrix[R, 2, 2]]["NonzeroPositions"];
facepairs = Partition[
  MeshCells[R, 2, "Multicells" -> True][[1, 1]][[Flatten[pairs]]],

For the development history of this code see How to obtain the cell-adjacency graph of a mesh? Also notice that the code the code in my answer 160457 there is a bit more up to date and hence a bit faster.

| improve this answer | |

NDSolve`FEM - "BoundaryConnectivity"

If you allow connections through a vertex to define neighbors, you can use NDSolve`FEM:

bmesh = ToBoundaryMesh[R];
connectivity = bmesh["BoundaryConnectivity"];

HighlightMesh[R, {Style[MeshCells[R, {2, 1}], Red], 
  MeshCells[R, #] & /@ Thread[{2, connectivity[[1]]}]}]

enter image description here

We can modify connectivity to keep only elements adjacent through an edge:

connectivity2 = MapIndexed[Function[{x, ind}, 
  DeleteCases[x, 0|_?(Length[Intersection[faces[[ind[[1]]]], faces[[#]]]] != 2&)]], 

HighlightMesh[R, {Style[MeshCells[R, {2, 1}], Red], 
  Style[MeshCells[R, {2, 10}], Green], 
  MeshCells[R, {2, #}] & /@ connectivity2[[1]], 
  MeshCells[R, {2, #}] & /@ connectivity2[[10]]}]

enter image description here

| improve this answer | |
  • $\begingroup$ Erm. The implementation involving Nearest takes twice as long as OP's implementation... I think the reason is that the chosen distance function is no distance function at all, so Nearest cannot take any advantage of it. $\endgroup$ – Henrik Schumacher Jul 12 '19 at 12:07
  • $\begingroup$ @HenrikSchumacher, erm indeed:) Should have tested before posting. $\endgroup$ – kglr Jul 12 '19 at 17: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.