查找连接到顶点的面

Question

假设我有一个由三角形(或面(组成的四边形，每个三角形包含三个顶点。tetraeder表示如下：

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

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

例如："；返回连接到具有索引1"的顶点的面的面索引；应该看起来像：

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

答案应该是[0,2,3]，因为索引为1的顶点([0。[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和下面的帖子，我找到了一种非常有效的方法。

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)

结果是一个字典，其中顶点索引和值是连接面的索引。如果顶点索引已经存在于dictionary中，则将面索引添加到面列表中；如果顶点索引还不存在，则使用仅具有该面索引值的列表生成新键。

例如：

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

建造dictionary需要一些时间(对于一个有55000个面的网格来说需要180毫秒(，但之后的请求几乎是即时的。而@bb1的功能在我的机器上只花了7毫秒就完成了一个请求。