Я смог ответить на это другим подходом. Это долго, потому что мне нужно включить дополнительные части. В общем, я решил эту проблему, используя faces, который определяет каждый треугольник с индексами его вершин. faces говорит мне, какие вершины связаны. Это позволило мне построить список строк, который содержит все связи между вершинами.
# using faces and verts in original post
linelist = []
for idx, vert in enumerate(faces):
print(vert)
for i,x in enumerate(vert):
l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])]
linelist.append(l)
Который дает такие элементы, как:
[[1.0, 0.10000000149011612, 1.0], [1.0, 1.0, 0.10000000149011612]]
Редактировать: обнаружен более быстрый метод:
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
open('output.txt','w').close()
for idx, graph in enumerate(nx.connected_components(graph)):
graphs.append(graph)
print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))
i+=1
Эти точки связаны. Затем я использовал чужой код для создания словаря, в котором каждый ключ - это вершина, а каждое значение - это связанная вершина. А потом я использовал поиск по дыханию в этом словаре. См. Класс ниже.
class MS_Graph():
def __init__ (self, linelist=None, vertices=None):
self.linelist = linelist if linelist is not None else None
self.vertices = vertices if vertices is not None else None
def getGraph(self):
'''
Takes self.linelist and converts to dict
'''
linelist = self.linelist
# edge list usually reads v1 -> v2
graph = {}
# however these are lines so symmetry is assumed
for l in linelist:
v1, v2 = map(tuple, l)
graph[v1] = graph.get(v1, ()) + (v2,)
graph[v2] = graph.get(v2, ()) + (v1,)
return graph
def BFS(self, graph):
"""
Implement breadth-first search
"""
# get nodes
#nodes = list(graph.keys()) # changed 4/16/2020
nodes = list(graph)
graphs = []
# check all nodes
while nodes:
# initialize BFS
toCheck = [nodes[0]]
discovered = []
# run bfs
while toCheck:
startNode = toCheck.pop()
for neighbor in graph.get(startNode):
if neighbor not in discovered:
discovered.append(neighbor)
toCheck.append(neighbor)
nodes.remove(neighbor)
# add discovered graphs
graphs.append(discovered)
self.graphs = graphs
return graphs
И, приводя его в целом:
Graph = MS_Graph(linelist)
graph = Graph.getGraph()
graphs = Graph.BFS(graph)
print(len(graphs))
# output: 3
print(graphs)
# output:
[[(1.0, 1.0, 0.10000000149011612), (0.10000000149011612, 1.0, 1.0), (1.0, 1.0, 1.899999976158142), (1.899999976158142, 1.0, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.899999976158142, 1.0)],
[(4.0, 1.0, 3.0999999046325684), (3.0999999046325684, 1.0, 4.0), (4.0, 1.0, 4.900000095367432), (5.0, 1.0, 3.0999999046325684), (5.0, 0.10000000149011612, 4.0), (4.0, 0.10000000149011612, 4.0), (5.0, 1.0, 4.900000095367432), (5.900000095367432, 1.0, 4.0), (5.0, 1.899999976158142, 4.0), (4.0, 1.899999976158142, 4.0)],
[(8.0, 8.0, 7.099999904632568), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 8.899999618530273), (8.899999618530273, 8.0, 8.0), (8.0, 7.099999904632568, 8.0), (8.0, 8.899999618530273, 8.0)]]
Тем не менее, мне интересно, есть ли более быстрый метод.
Редактировать: Там может быть более быстрый путь. Поскольку faces содержит вершины каждого отдельного треугольника, все треугольники, которые принадлежат одному объекту, будут иметь непрерывную цепочку. т.е. множество вершин, составляющих объект 1, будет отличаться от множества вершин, составляющих любой другой объект.
Например, набор граней для каждого объекта:
object_1_faces =
[ 2 1 0]
[ 0 3 2]
[ 1 4 0]
[ 0 4 3]
[ 5 1 2]
[ 3 5 2]
[ 5 4 1]
[ 4 5 3]
object_2_faces =
[ 8 7 6]
[ 6 9 8]
[ 7 10 6]
[ 6 10 9]
[11 7 8]
[ 9 11 8]
[11 10 7]
[10 11 9]
object_1_vertices = {0,1,2,3,4,5}
object_2_vertices = {6,7,8,9,10,11}
Я думаю, это означает, что есть более быстрый способ, чем поиск всех линий.