0

Say I have a tetraeder which is built up out of triangles (or faces), each triangle contains three vertices. The tetraeder is represented as follows:

vertices = [[0. 0. 0.] [0. 1. 1.] [1. 0. 1.] [1. 1. 0.]]
faces = [[0 1 2] [0 2 3] [0 1 3] [1 2 3]]

I would like to have a structure that I can give a vertex index and can return me the faces that contain this vertex in an efficiënt way. It needs to be efficiënt as I need to find the faces connected to for example 1000 vertices in a file with 20 000 faces. It should thus be some sort of data structure where an element of the structure is a list of faces and the index of that element equals the vertex index that is connected with those faces.

For example: "return the face indices of the faces connected to the vertex with index 1" should look like:

vertex_index = 1
find_connected_faces[vertex_index] --> [0,2,3]

The answer should be [0,2,3] because the vertex with index 1 ([0. 1. 1.]) is present in these faces. I'm struggling with a way to solve this problem efficiently. I thought about graphs using the networkx library, but haven't quite found the best approach. I found a lot of solutions to find two faces that are connected by an edge, but as you can see this is not exactly what I am looking for.

ThaNoob
  • 520
  • 7
  • 23

2 Answers2

1

Here is one way to do it:

def find_connected_faces(vertex_index, faces):
    return [faces.index(f) for f in faces if vertex_index in f]

Similarly, using numpy:

import numpy as np

def find_connected_faces(vertex_index, faces):
    return np.nonzero(np.array(faces) == vertex_index)[0]
bb1
  • 7,174
  • 2
  • 8
  • 23
  • Thanks for the reply @bb1, it is a very elegant solution as a one time function. However, imagine I have to look up thousands of points, then for each look up it has to run through all the faces. I was actually thinking of a method where the code runs once through all the faces and creats a list-like structure where the index represents the vertex index and the item in that list for that index contains the indices of the faces where that vertex is present. – ThaNoob Apr 02 '21 at 07:04
  • I edited the question so that the question reflects what I mentioned in the previous comment – ThaNoob Apr 02 '21 at 07:15
0

I found a way to do it quite efficiëntly thanks to @bb1 and the following post.

faces_connected_to_vertex = {}
vertices = [[0, 0, 0],[0, 1, 1], [1, 0, 1], [1, 1, 0]]
faces = [[0, 1, 2], [0, 2, 3], [0, 1, 3], [1, 2, 3]]
for face_index,face in enumerate(faces):
    for vertex_index in face:
        faces_connected_to_vertex.setdefault(vertex_index,[]).append(face_index)

The result is a dictionnary with as keys the vertex indices and values the indices of the connected faces. If the vertex index already exists in the dictionnary then the face index is added to the list of faces, if it does not exist yet then a new key is made with a list with as only value that face index.

For this example:

faces_connected_to_vertex[1] --> [0,2,3]

Building the dictionnary takes some time (180ms for a mesh with 55 000 faces) but requests afterwards are almost instant. Whereas @bb1's function took 7ms on my machine for one request.

ThaNoob
  • 520
  • 7
  • 23