# Cell-adjacency Graph of a Square Mesh

Consider the list of points

pts = {{1, 1}, {1, 2}, {2, 1}, {2, 2}}

I want to use them to define a 2x2 square mesh using VoronoiMesh, where each cell has two neighbours. Following the discussion in this question, consider the following code

mesh = VoronoiMesh[pts, ImageSize -> Medium];
conn = mesh["ConnectivityMatrix"[2, 1]];
centers = PropertyValue[{mesh, 2}, MeshCellCentroid];
VertexCoordinates -> centers];
Show[mesh, g]

As one can see, unlike other meshes, this one does not seem to work exactly as I want, since the diagonal edge should not appear. Why is this happening? Any way of avoiding that edge and get

as one would expect from a square lattice?

Edit: As noticed in the comment section, some of the polygons seem to have sharing edges that are single points, which is enough for them to be considered neighbouring cells. This effect is unchanged with the size of the lattice. If I consider, for example, the points

pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1];

I get

Any ideas on how to solve this? Maybe omit the extra edge in a way that doesn't this or other non-square meshes. For example, considering a random VoronoiMesh, nothing seems to wrong, though it could, theoretically, go

• Something somewhat strange... faces 3 and 4 have 5 sides: In[52]:= MeshCells[mesh, 2] Out[52]= {Polygon[{4, 1, 3, 6}], Polygon[{5, 1, 2, 9}], Polygon[{7, 3, 1, 1, 5}], Polygon[{8, 2, 1, 1, 4}]}. But notice 1 is repeated twice...so structurally they share an edge, but that 'edge' is really just a point. Jan 15, 2020 at 21:57
• That's right. Would it be possible to delete that 1 in a reasonably natural manner? So that it wouldn't affect other possible meshes? Jan 15, 2020 at 22:07
• The problem persists with bigger lattices. Please see edit section. Jan 15, 2020 at 22:22
• IGraph/M handles this well. Did you try it? IGMeshCellAdjacencyGraph[mesh, 2]. You may also want to add VertexCoordinates -> Automatic Jan 15, 2020 at 22:26
• Well, it's open-source so you can check ... It's based on Henrik's answer in the linked question. Jan 16, 2020 at 8:05

We can delete the rows in our incidence matrix that correspond to these edges of length 0.

pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1];

mesh = VoronoiMesh[pts, ImageSize -> Medium];
conn = mesh["ConnectivityMatrix"[1, 2]];

lens = PropertyValue[{mesh, 1}, MeshCellMeasure];
$$threshold = 0.; keep = Pick[Range[MeshCellCount[mesh, 1]], UnitStep[Subtract[$$threshold, lens]], 0];
conn = conn[[keep]];

centers = PropertyValue[{mesh, 2}, MeshCellCentroid];

Show[mesh, g]

You can delete the unwanted edges using EdgeDelete:

Show[mesh, EdgeDelete[g, UndirectedEdge[a_, b_] /;
(FreeQ[0][Chop[Differences[PropertyValue[{g, #}, VertexCoordinates] & /@ {a, b}]]])]]

For g generated using pts = Flatten[Table[{i, j}, {i, 7}, {j, 5}], 1]; we get

L1 = 2; L2 = 2;
mesh = VoronoiMesh @ Tuples[Range /@ {L1, L2}];
centers = Rationalize @ PropertyValue[{mesh, 2}, MeshCellCentroid];

g1 = VertexReplace[GridGraph[{L2, L1}, PlotTheme -> "Scientific",
VertexCoordinates -> centers[[Ordering @ centers]],
{v_ :> Ordering[centers][[v]]}];

Show[mesh, g1]

For L1 = 7; L2 = 5; the same approach gives