2026, Jan 08 17:00
Topology-First Grid Indexing: Recover a Regular Lattice from a Warped Quadrilateral Mesh via 4-Cycle Faces
Reconstruct a regular grid from an unordered adjacency list using 4-cycles on a quadrilateral mesh. Topology-based face assembly yields robust (i,j) indexing.
Reconstructing a regular grid from an unordered adjacency list is a classic case where the geometry is misleading but the topology is enough. The raw plot may look like a distorted mesh, yet the graph encodes all we need to index nodes on a structured 2D lattice. The key is to stop thinking in terms of angles and distances on a deformed picture and instead work with faces. For a quadrilateral mesh with nodes of degree two, three, or four, and no edge crossings, cycles of length four are the right abstraction. Once faces are identified, grid indices fall out deterministically up to rotation and reflection.
Problem setup
The input is an unordered adjacency list and an array of node coordinates. If you scatter-plot using the coordinates, the result looks like a warped grid. What’s missing is a consistent mapping from node IDs to their (i, j) positions on a regular lattice.
# Unordered adjacency (graph connectivity)
nbrs_map = [[1, 4], [0, 2, 5], [1, 3, 7], [2, 6, 12],
[5, 0, 11], [4, 1, 7, 13], [3, 15, 8],
[2, 5, 12, 14], [6, 9, 16], [8, 10, 17],
[9, 19], [4, 13, 18], [7, 15, 3], [5, 11, 14, 20],
[7, 13], [6, 12, 16], [8, 15, 17], [16, 9, 19, 22],
[11, 20, 21], [10, 17, 24], [13, 18, 23], [18, 23, 27],
[17, 24, 28], [20, 21, 25, 30], [19, 22, 31],
[23, 26, 32], [25, 29, 34], [21, 30, 35], [22, 31, 36],
[26, 33, 37], [23, 27, 32, 38], [24, 28, 39],
[25, 30, 34, 40], [29, 36, 41], [26, 32, 37, 42],
[27, 38], [33, 43, 39, 28], [29, 34, 41, 44],
[30, 35, 40], [31, 36, 45], [32, 38, 42],
[33, 37, 43, 46], [34, 44, 40], [36, 41, 45],
[46, 37, 42], [39, 43], [41, 44]]
# 2D coordinates (used only to fix face orientation)
coords = [(1023, 763), (902, 742), (776, 718), (629, 681),
(1041, 673), (924, 651), (479, 643), (799, 625),
(329, 620), (180, 599), (41, 581), (1051, 580),
(653, 580), (937, 556), (810, 529), (498, 529),
(340, 509), (188, 491), (1059, 490), (47, 470),
(943, 463), (1059, 393), (195, 386), (941, 365),
(54, 361), (814, 339), (663, 311), (1055, 294),
(201, 286), (509, 285), (933, 262), (62, 256),
(806, 234), (357, 232), (657, 199), (1043, 189),
(210, 185), (507, 167), (925, 157), (74, 149),
(798, 128), (360, 122), (652, 88), (219, 79),
(507, 53), (87, 41), (364, 11)]
The goal is to recover a regular grid indexing for nodes, such that each node’s neighbors align with consistent east–west and north–south relations. Relying on metric heuristics like distances or angles is intentionally avoided, since the mesh may be strongly distorted.
Why the plot looks deformed and why that’s fine
The geometry is incidental; the structure is what matters. Each face is a quadrilateral, interior nodes have four neighbors, edge nodes three, and corners two. There are no edge crossings, and there may be interior gaps whose boundary still conforms to these quadrilateral constraints. Under these conditions, faces can be detected as cycles of length four, and a consistent lattice can be established by walking those faces. The resulting indexing is unique only up to rotation and reflection, which is expected because the grid has no absolute orientation without a reference.
Solution: build faces first, then index the grid
The approach proceeds in four steps. First, enumerate all quadrilateral faces by finding 4-cycles and use the coordinates only to fix a consistent anticlockwise order. Second, iteratively place those faces onto a grid by matching shared edges and rotating them into a common orientation as needed. Third, propagate face indices to vertex indices. Finally, apply a global rotation or reflection to match the intended orientation. The coordinates affect only the orientation of each face; the actual lattice comes purely from connectivity.
def collect_quads(neigh, pts):
"""
Build the set of quadrilateral faces as lists of 4 vertex IDs, ordered anticlockwise.
Each face is indexed from its smallest vertex ID, which plays the role of the
bottom-left corner in that local orientation.
"""
n_nodes = len(neigh)
faces = []
for a in range(n_nodes):
for b in neigh[a]:
for c in neigh[b]:
for d in neigh[c]:
if a in neigh[d] and a < min([b, c, d]) and a != c and b != d:
ccw = (pts[c][0] - pts[a][0]) * (pts[d][1] - pts[b][1]) - \
(pts[c][1] - pts[a][1]) * (pts[d][0] - pts[b][0]) > 0
if ccw:
faces.append([a, b, c, d])
return faces
###############################################################################
def index_quads(faces):
"""
Assign integer grid coordinates (I, J) to the quadrilateral faces by attaching
them via shared edges. While attaching, rotate each candidate so that shared
edges align in a common orientation.
"""
n_faces = len(faces)
face_i = [n_faces] * n_faces
face_j = [n_faces] * n_faces
face_i[0] = 0
face_j[0] = 0
attached = 1
while attached < n_faces:
for p in range(n_faces):
if face_i[p] < n_faces:
for q in range(n_faces):
if q == p:
continue
if faces[p][0] in faces[q] and faces[p][1] in faces[q]:
pos = faces[q].index(faces[p][0])
rot = [3, 2, 1, 0][pos]
faces[q] = faces[q][-rot:] + faces[q][:-rot]
face_i[q] = face_i[p]
face_j[q] = face_j[p] - 1
attached += 1
if faces[p][1] in faces[q] and faces[p][2] in faces[q]:
pos = faces[q].index(faces[p][1])
rot = [0, 3, 2, 1][pos]
faces[q] = faces[q][-rot:] + faces[q][:-rot]
face_i[q] = face_i[p] + 1
face_j[q] = face_j[p]
attached += 1
if faces[p][2] in faces[q] and faces[p][3] in faces[q]:
pos = faces[q].index(faces[p][2])
rot = [1, 0, 3, 2][pos]
faces[q] = faces[q][-rot:] + faces[q][:-rot]
face_i[q] = face_i[p]
face_j[q] = face_j[p] + 1
attached += 1
if faces[p][3] in faces[q] and faces[p][0] in faces[q]:
pos = faces[q].index(faces[p][3])
rot = [2, 1, 0, 3][pos]
faces[q] = faces[q][-rot:] + faces[q][:-rot]
face_i[q] = face_i[p] - 1
face_j[q] = face_j[p]
attached += 1
imin = min(face_i)
jmin = min(face_j)
for t in range(n_faces):
face_i[t] -= imin
face_j[t] -= jmin
return faces, face_i, face_j, max(face_i) + 1, max(face_j) + 1
###############################################################################
# Input data reused here for a runnable snippet
nbrs_map = [[1, 4], [0, 2, 5], [1, 3, 7], [2, 6, 12],
[5, 0, 11], [4, 1, 7, 13], [3, 15, 8],
[2, 5, 12, 14], [6, 9, 16], [8, 10, 17],
[9, 19], [4, 13, 18], [7, 15, 3], [5, 11, 14, 20],
[7, 13], [6, 12, 16], [8, 15, 17], [16, 9, 19, 22],
[11, 20, 21], [10, 17, 24], [13, 18, 23], [18, 23, 27],
[17, 24, 28], [20, 21, 25, 30], [19, 22, 31],
[23, 26, 32], [25, 29, 34], [21, 30, 35], [22, 31, 36],
[26, 33, 37], [23, 27, 32, 38], [24, 28, 39],
[25, 30, 34, 40], [29, 36, 41], [26, 32, 37, 42],
[27, 38], [33, 43, 39, 28], [29, 34, 41, 44],
[30, 35, 40], [31, 36, 45], [32, 38, 42],
[33, 37, 43, 46], [34, 44, 40], [36, 41, 45],
[46, 37, 42], [39, 43], [41, 44]]
coords = [(1023, 763), (902, 742), (776, 718), (629, 681),
(1041, 673), (924, 651), (479, 643), (799, 625),
(329, 620), (180, 599), (41, 581), (1051, 580),
(653, 580), (937, 556), (810, 529), (498, 529),
(340, 509), (188, 491), (1059, 490), (47, 470),
(943, 463), (1059, 393), (195, 386), (941, 365),
(54, 361), (814, 339), (663, 311), (1055, 294),
(201, 286), (509, 285), (933, 262), (62, 256),
(806, 234), (357, 232), (657, 199), (1043, 189),
(210, 185), (507, 167), (925, 157), (74, 149),
(798, 128), (360, 122), (652, 88), (219, 79),
(507, 53), (87, 41), (364, 11)]
# Build faces, assign face grid indices, then propagate to vertex indices
faces = collect_quads(nbrs_map, coords)
faces, fi, fj, nx, ny = index_quads(faces)
n_nodes = len(nbrs_map)
node_i = [-1] * n_nodes
node_j = [-1] * n_nodes
for k in range(len(faces)):
node_i[faces[k][0]] = fi[k]; node_j[faces[k][0]] = fj[k]
node_i[faces[k][1]] = fi[k] + 1; node_j[faces[k][1]] = fj[k]
node_i[faces[k][2]] = fi[k] + 1; node_j[faces[k][2]] = fj[k] + 1
node_i[faces[k][3]] = fi[k]; node_j[faces[k][3]] = fj[k] + 1
# Optional global reflection to match a preferred orientation
for u in range(n_nodes):
node_i[u] = nx - node_i[u]
print("Node --> i, j")
for u in range(n_nodes):
print(u, " --> ", node_i[u], node_j[u])
Running this yields the lattice coordinates for every node. The mapping aligns with a hand-annotated regular grid, modulo a simple reflection as shown by the final transformation.
Node --> i, j
0 --> 7 0
1 --> 6 0
2 --> 5 0
3 --> 4 0
4 --> 7 1
5 --> 6 1
6 --> 3 0
7 --> 5 1
8 --> 2 0
9 --> 1 0
10 --> 0 0
11 --> 7 2
12 --> 4 1
13 --> 6 2
14 --> 5 2
15 --> 3 1
16 --> 2 1
17 --> 1 1
18 --> 7 3
19 --> 0 1
20 --> 6 3
21 --> 7 4
22 --> 1 2
23 --> 6 4
24 --> 0 2
25 --> 5 4
26 --> 4 4
27 --> 7 5
28 --> 1 3
29 --> 3 4
30 --> 6 5
31 --> 0 3
32 --> 5 5
33 --> 2 4
34 --> 4 5
35 --> 7 6
36 --> 1 4
37 --> 3 5
38 --> 6 6
39 --> 0 4
40 --> 5 6
41 --> 2 5
42 --> 4 6
43 --> 1 5
44 --> 3 6
45 --> 0 5
46 --> 2 6
What makes this reliable
This method avoids brittle heuristics tied to Euclidean geometry. It uses only the planar connectivity and the quadrilateral nature of faces, so even strong distortions or angles greater than forty-five degrees do not affect the outcome. The coordinates serve merely to ensure a consistent anticlockwise ordering within each face, which lets shared edges be recognized unambiguously as faces are attached. As with any grid lacking an absolute frame, the final indexing is determined only up to a rotation and a reflection, which can be applied at the end to match a desired orientation.
Takeaways
When reconstructing a regular lattice from a warped quadrilateral mesh, treat faces as the primary object. Detect 4-cycles, impose a consistent orientation using the provided coordinates, assemble faces by shared edges, and then lift the face indices to vertex indices. This keeps the logic robust in the presence of distortion, respects the graph’s planarity, and yields the structured (i, j) mapping you need for downstream processing. If you want a specific orientation, apply a final global rotation or reflection without touching the connectivity.