CODEWITHSUNDEEP
pythongraphcoordinatesmeshadjacency-list
Optical_flow_lover
Optical_flow_lover

Reputation: 129

Finding quad faces in a planar graph / 2D mesh

Description:

I have a set of coordinate points and an adjacency list that describes how each point (node) is connected to other points. Using these, I plotted a graph using NetworkX in Python.

Here are the points and the adjacency list:

points = [
    [1449, 1427], [1568, 1349], [1828, 1262], [1054, 1294], [1236, 1186],
    [1432, 1124], [1754, 1032], [2122, 968], [2591, 953], [790, 957],
    [1069, 881], [1720, 738], [2183, 691], [2633, 723], [557, 495],
    [878, 465], [1238, 433], [1690, 412], [2229, 395], [2705, 368],
    [432, 116], [772, 74], [1234, 27], [1680, 0], [2267, 21]
]

adjacency_list = [
    [2,5], [1,3,6], [2,7], [5,10], [1,4,6,11], [2,5,7], [3,6,8,12],
    [7,9,13], [8,14], [4,11,15], [5,10,16], [7,13,18], [8,12,14,19],
    [9,13,20], [10,16,21], [11,17,15,22], [16,18,23], [12,17,19,24],
    [13,18,20,25], [19,14], [15,22], [21,16,23], [17,22], [18,25], [19,24]
]

I used the following Python code to visualize the graph:

import matplotlib.pyplot as plt
import networkx as nx

# Create a new graph
G = nx.Graph()

# Add nodes with positions
for i, point in enumerate(points):
    G.add_node(i + 1, pos=point)

# Add edges
for i, connections in enumerate(adjacency_list):
    for j in connections:
        G.add_edge(i + 1, j)

# Get node positions
pos = nx.get_node_attributes(G, 'pos')

nx.draw(G, pos, with_labels=True, node_color='green', node_size=300, font_size=8, font_color='white')

plt.axis('off')
plt.show()

The resulting graph is shown below:

graph

Objective:

I want to determine which faces are formed by the nodes in this graph. Specifically, I'm only interested in the faces that are quadrilaterals (i.e., faces formed by exactly 4 nodes/vertices).

For example, face 1 marked in the image is represented by the nodes [1, 2, 5, 6]. So, for this example, the output should be:

faces = [
    [1,2,6,5], [2,3,7,6], [4,5,11,10], [7,8,13,12], [8,9,14,13], [10,11,16,15], [12,13,19,18],
   [13,14,20,19], [15,16,22,21], [16,17,23,22], [18,19,25,24]

]

Considerations:

Face 1 (and similarly for the others) can be any of the valid faces (I chose this order to make it consistent with the image).

Note that adjacency_list does not necessarily list the nodes in a particular order (clockwise or counterclockwise).

Upvotes: 1

Views: 123

Answers (2)

Optical_flow_lover
Optical_flow_lover

Reputation: 129

Using Cincinnatus ideas I created this code:

from itertools import combinations

def find_quadrilateral_faces(G):
    faces = set()
    for node in G.nodes():
        neighbors = list(G.neighbors(node))
        for i, j in combinations(neighbors, 2):
            common_neighbors = set(G.neighbors(i)) & set(G.neighbors(j)) - {node}
            for common_neighbor in common_neighbors:
                face = frozenset([node, i, j, common_neighbor])
                faces.add(face)
    return list(faces)

def sort_face_points(face, points):
    # Convert to numpy array 
    pts = np.array([points[i] for i in face])
    
    # Find centroid
    cent = pts.mean(axis=0)
    
    # Sort points based on their angle from centroid
    sorted_pts = sorted(face, key=lambda p: np.arctan2(*(np.array(points[p]) - cent)[::-1]))
    
    return sorted_pts

# Find all quadrilateral faces
quadrilateral_faces = find_quadrilateral_faces(G)

# Sort the points in each face
quadrilateral_faces = [[int(node) for node in face] for face in quadrilateral_faces]
quadrilateral_faces = [sort_face_points(face, P) for face in quadrilateral_faces]

Upvotes: 0

el_grezeq
el_grezeq

Reputation: 133

If I understand well, you are trying to find all simple cycles of size 4 in your graph.

It is quite straightforward with NetworkX:

for c in nx.simple_cycles(G):
    if len(c)==4: print(c)

You may need to know a bit more about graph theory (and specifically cycles) or check the NetworkX documentation on Cycles.

Cheers!

Upvotes: 0

Related Questions