List connectivity of points in discretized mesh

I'm trying to automate the extraction of the points and a compatible connectivity list for meshes created using the DiscretizeRegion or similar method.

If I create a bounding polygon from a list of points (x,y,z) I could then start to create a discretized mesh using the DiscretizeRegion function. Sample code I've been tinkering with below, using a Disk[] for illustration...

foo = DiscretizeRegion[Disk[], MaxCellMeasure -> 0.1] And the points from the mesh I believe can be extracted using:

MeshCoordinates[foo]

In addition to the co-ordinates of the nodes I would also like to extract a list of connectivity that I can then take forward into my analysis.

For example, say that MeshCoordinates[foo] returns a list of co-ordinates in {x,y,z} format, say:

{{x1,y1,z1},{x2,y2,z2},{x3,y3,z3}, etc}

and if that first point is connected to the second and the third point (but the second and third points are not connected), the list that I'm looking to create, that would define the connectivity would be:

{{1,2},{1,3}}

Ideally all of the perimeter nodes would be defined in sequential order, with the internal node numbering following on with the next node number in the sequence. ie the perimeter nodes could be 1-10, with the first internal node being node number 11.

• I don't have version 10 (or a computer, for that matter), but I believe the output of DiscretizeRegion[] should have a GraphicsComplex[] object in it somewhere. Can you check? – J. M. will be back soon Jul 28 '15 at 14:00
• I'm not sure how I would check that in all honesty... I'll dig into it and see if I can work out how to check the output – ASBO Allstar Jul 28 '15 at 15:22
• The stuff within Polygon[] looks to be useful; you'll note that it has a list of triples, corresponding to the triangle whose vertices are indexed by the integers in the triple. You should now have something to start with. – J. M. will be back soon Jul 28 '15 at 16:02
• Something like this? test=ToString[InputForm[foo]];ToExpression[StringTake[test,StringPosition[test,"Polygon"][[1, 1]], StringPosition[test, "Properties"][[1, 1]] - 4}]] – Neven Caplar Jul 28 '15 at 17:19
• Have a look at the documentation for ToElementMesh and ElementMesh. Either use the ElementIncidents or the boundary or mesh element connectivity data structures. There is also a Tutorial – user21 Jul 28 '15 at 17:22

If we want all pairs of indices of vertices connected by a line segment, then MeshCells will return the list in the form {Line[{i, j}]..}.

foo = DiscretizeRegion[Disk[], MaxCellMeasure -> 0.1];
bobbie = MeshCells[foo, 1][[All, 1]]
(*
{{9, 10}, {10, 23}, {23, 9}, {35, 8}, {8, 9}, {9, 35}, {29, 20}, {20,
16}, {16, 29}, {6, 7}, {7, 20}, {20, 6}, {36, 12}, {12, 25}, {25,
36}, {23, 35}, {21, 7}, {7, 8}, {8, 21}, {20, 21}, {21, 16}, {29,
22}, {22, 5}, {5, 29}, {1, 27}, {27, 37}, {37, 1}, {24, 17}, {17,
23}, {23, 24}, {21, 35}, {35, 32}, {32, 21}, {19, 28}, {28,
31}, {31, 19}, {34, 15}, {15, 33}, {33, 34}, {3, 28}, {28, 2}, {2,
3}, {25, 26}, {26, 18}, {18, 25}, {24, 10}, {10, 11}, {11, 24}, {5,
6}, {6, 29}, {26, 13}, {13, 14}, {14, 26}, {31, 4}, {4, 22}, {22,
31}, {2, 27}, {1, 2}, {17, 33}, {33, 32}, {32, 17}, {15, 32}, {12,
13}, {13, 25}, {4, 5}, {30, 22}, {29, 30}, {30, 19}, {19, 22}, {17,
35}, {36, 11}, {11, 12}, {24, 36}, {36, 33}, {33, 24}, {18,
36}, {37, 14}, {14, 1}, {26, 37}, {37, 34}, {34, 26}, {28, 27}, {27,
19}, {19, 37}, {3, 4}, {31, 3}, {16, 30}, {32, 30}, {16, 32}, {30,
15}, {15, 19}, {33, 18}, {18, 34}, {34, 19}}
*)

Check:

GraphicsRow[{
foo,
Show[
foo,
Graphics[
GraphicsComplex[
MeshCoordinates[foo],
Line[bobbie]
]]
]}
] • You beat me to it. +1 – RunnyKine Jul 28 '15 at 19:12
• @RunnyKine Haven't seen you much lately, it seems. (Well since the end of June, I've been somewhat busy and not paying close attention.) Good to hear from you in any case. :) – Michael E2 Jul 28 '15 at 19:15
• Thank you :). I've been busy with school work, so not much time to participate here. – RunnyKine Jul 28 '15 at 19:34

I was a bit confused about your definition of "connectivity" and which points are and are not to be selected, but I hope I understood what you wanted.

AllConnections=Table[DeleteCases[Flatten[Select[MeshCells[foo, 1][[All, 1]], #[] == n || #[] == n &]],n], {n, Length[MeshCells[foo, 0]]}];

FinalResult=Table[Partition[Flatten[{{i,AllConnections[[i,j]]},{ConstantArray[i,Length[Complement[AllConnections[[i]],Join[{AllConnections[[i,j]]},AllConnections[[AllConnections[[i,j]]]]]]]],Complement[AllConnections[[i]],Join[{AllConnections[[i,j]]},AllConnections[[AllConnections[[i,j]]]]]]}//Transpose}],2],{i,Length[AllConnections]},{j,Length[AllConnections[[i]]]}]

What this code does, after it has selected one point which is connected to starting point to select also all the others which are not connected to the first connected point. For example

GraphicsRow[Table[Show[foo = DiscretizeRegion[Disk[], MaxCellMeasure -> 0.1],ListPlot[Map[Part[MeshCoordinates[foo], #] &, FinalResult[[1, j]]],
PlotStyle -> Blue, Joined -> True], ListPlot[Map[Part[MeshCoordinates[foo], #] &, FinalResult[[1, j]]][],
PlotStyle -> Red, Joined -> True]], {j, 4}]] So, first you select red line (first connection) and look for all connections which are not neighbours (blue lines). I hope that this helps! Is this what you wanted?

• Thanks for the answer, but it's not quite what I was looking for. Essentially I've got a shape that's been discretized into triangles which has introduced lots of additional points. I'm looking to create a list of the nodes that a each node is directly connected to. I've edited the example in the original question a little to help make it clearer what I'm hoping to achieve. Thanks for answering though. – ASBO Allstar Jul 28 '15 at 15:26
• Lets have a look at the example which is shown in my "answer". What would be result there? There are 4 points, lets called them (1,2,3,4) from bottom to top. Lets call the point of origin P (one to the most-right) What would be answer there? (P,1) and (P,4)... or? – Neven Caplar Jul 28 '15 at 15:41
• Yes, if P is the point on the boundary that you've connected the lines too, and those points are 1-4, then the connectivity list would be {{p,1},{p,2},{p,3},{p,4}} if point p was indeed connected to all four points... – ASBO Allstar Jul 28 '15 at 15:49

Thanks to Guess Who It is and user21 for their help in the comments of the original question, if they want to submit the same answer fully I'll remove this no problems and vote theirs up.

Defining a region:

foo = DiscretizeRegion[Disk[], MaxCellMeasure -> 0.1]

Then the connectivity of the polygon data exists if the output of foo is inspected. (Guess Who It Is code)

InputForm[foo]

The polygon component can be extracted using the following code. (user21 code edited)

test = ToString[InputForm[foo]];
jim = ToExpression[
StringTake[
test, {StringPosition[test, "Polygon"][[1, 1]],
StringPosition[test, "Properties"][[1, 1]] - 4}]]

Taking the first element from this leaves just the list data...

jim=jim[]

Gives a list that can now be parsed and tweaked to identify the connectivity. I've sorted the list in the first line, but this step isn't strictly necessary...

moo = Sort[jim];
bob = Partition[Flatten[Riffle[moo, moo]], 2]

{{1, 27}, {37, 1}, {27, 37}, {2, 27}, {1, 2}, {27, 1}, {3, 4}, {31, 3}, {4, 31}, {3, 28}, {2, 3}, {28, 2}, {3, 31}, {28, 3}, {31, 28}, {6, 7}, {20, 6}, {7, 20}, {8, 35}, {21, 8}, {35, 21}, {9, 10}, {23, 9}, {10, 23}, {11, 36}, {24, 11}, {36, 24}, {12, 13}, {25, 12}, {13, 25}, {14, 37}, {26, 14}, {37, 26}, {16, 20}, {21, 16}, {20, 21}, {17, 33}, {32, 17}, {33, 32}, {19, 15}, {34, 19}, {15, 34}, {19, 28}, {31, 19}, {28, 31}, {19, 30}, {15, 19}, {30, 15}, {19, 31}, {22, 19}, {31, 22}, {20, 29}, {6, 20}, {29, 6}, {21, 7}, {8, 21}, {7, 8}, {21, 20}, {7, 21}, {20, 7}, {21, 32}, {16, 21}, {32, 16}, {21, 35}, {32, 21}, {35, 32}, {22, 4}, {5, 22}, {4, 5}, {22, 30}, {19, 22}, {30, 19}, {23, 35}, {9, 23}, {35, 9}, {24, 10}, {11, 24}, {10, 11}, {24, 17}, {23, 24}, {17, 23}, {24, 23}, {10, 24}, {23, 10}, {24, 33}, {17, 24}, {33, 17}, {24, 36}, {33, 24}, {36, 33}, {25, 26}, {18, 25}, {26, 18}, {26, 13}, {14, 26}, {13, 14}, {26, 25}, {13, 26}, {25, 13}, {26, 34}, {18, 26}, {34, 18}, {26, 37}, {34, 26}, {37, 34}, {27, 28}, {19, 27}, {28, 19}, {28, 27}, {2, 28}, {27, 2}, {29, 5}, {6, 29}, {5, 6}, {29, 20}, {16, 29}, {20, 16}, {29, 22}, {5, 29}, {22, 5}, {30, 22}, {29, 30}, {22, 29}, {30, 29}, {16, 30}, {29, 16}, {30, 32}, {15, 30}, {32, 15}, {31, 4}, {22, 31}, {4, 22}, {32, 30}, {16, 32}, {30, 16}, {32, 35}, {17, 32}, {35, 17}, {33, 15}, {32, 33}, {15, 32}, {33, 36}, {18, 33}, {36, 18}, {34, 15}, {33, 34}, {15, 33}, {34, 33}, {18, 34}, {33, 18}, {34, 37}, {19, 34}, {37, 19}, {35, 8}, {9, 35}, {8, 9}, {35, 23}, {17, 35}, {23, 17}, {36, 11}, {12, 36}, {11, 12}, {36, 12}, {25, 36}, {12, 25}, {36, 25}, {18, 36}, {25, 18}, {37, 14}, {1, 37}, {14, 1}, {37, 27}, {19, 37}, {27, 19}}

This shows that node 1 is connected to 27, 37 connected to 1, etc, etc...

• Your result contains both {a, b} and {b, a} -- for example, {1, 27} and {27, 1}. Is that what you want? (My answer contains only one of the pairs, but the others are easily added.) – Michael E2 Jul 28 '15 at 19:10
• You're quite correct, my last needs some tidying up to remove duplicates – ASBO Allstar Jul 28 '15 at 19:19