查找连接到顶点的面

Question

假设我有一个由三角形（或面）构成的四边形，每个三角形包含三个顶点。四联体表示如下：

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]]

我想要一个可以给出顶点索引的结构，并且可以 return 以高效的方式包含该顶点的面。它需要高效，因为我需要在具有 20 000 个面孔的文件中找到连接到例如 1000 个顶点的面孔。因此，它应该是某种数据结构，其中结构的元素是面列表，并且该元素的索引等于与这些面连接的顶点索引。

例如：“return 与索引为 1 的顶点相连的面的面索引应如下所示：

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

答案应该是 [0,2,3]，因为索引为 1 ([0. 1. 1.]) 的顶点存在于这些面中。我正在努力寻找有效解决此问题的方法。我考虑过使用 networkx 库的图形，但还没有找到最好的方法。我找到了很多解决方案来找到由一条边连接的两个面，但如您所见，这并不是我要找的。

Answer 1

这是一种方法：

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

同样，使用numpy：

import numpy as np

def find_connected_faces(vertex_index, faces):
    return np.nonzero(np.array(faces) == vertex_index)[0]

Answer 2

感谢@bb1 和以下 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)

结果是一个字典，其中顶点索引作为键，连接面的索引作为值。如果字典中已经存在顶点索引，则将面索引添加到面列表中，如果尚不存在，则使用面索引作为唯一值的列表创建新键。

对于这个例子：

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

构建字典需要一些时间（对于具有 55 000 个面的网格需要 180 毫秒），但之后的请求几乎是即时的。而@bb1 的函数在我的机器上为一个请求花费了 7 毫秒。

查找连接到顶点的面

Find faces connected to vertex

python

mesh