给定一组三角形顶点和面，分离对象并形成单独的网格
Given a set of triangle vertices and faces, separate objects and form separate meshes
编辑：我已经写了这个问题的更简洁的版本 但我保留这个 post 因为它是一个完整的解释。
给定一个 3D numpy 数组，marching cubes can form a 3D object 在某个阈值附近。
import numpy as np
from skimage import measure
A = np.zeros((12,12,12))
#A[A<1] = -1
for i in np.arange(1,2):
for j in np.arange(1,2):
for k in np.arange(1,2):
A[i,j,k] = 10
for i in np.arange(8,9):
for j in np.arange(8,9):
for k in np.arange(8,9):
A[i,j,k] = 10
verts, faces, normals, values = measure.marching_cubes_lewiner(A,1)
# which returns
verts = [[0.1, 1., 1. ] [1., 1., 0.1] [1., 0.1, 1. ] [1., 1., 1.9] [1., 1.9, 1. ]
[1.9, 1., 1. ] [7.1, 8., 8. ] [8., 8., 7.1] [8., 7.1, 8. ] [8., 8., 8.9]
[8., 8.9, 8. ] [8.9, 8., 8. ]]
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] [ 8, 7, 6] [ 6, 9, 8] [ 7, 10, 6] [ 6, 10, 9]
[11, 7, 8] [ 9, 11, 8] [11, 10, 7] [10, 11, 9]]
这可以绘制：
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
from mpl_toolkits.mplot3d import Axes3D
mesh = Poly3DCollection(verts[faces])
mesh.set_edgecolor('k')
mesh.set_facecolor('b')
ax.set_xlim(0,10)
ax.set_ylim(0,10)
ax.set_zlim(0,12)
返回这个可爱的 3D 图像：
我使用我自己的代码（见下文）使用一种算法来分离这些对象并得到：
graph1 = {(1.0, 1.0, 0.10000000149011612), (1.899999976158142, 1.0, 1.0), (0.10000000149011612, 1.0, 1.0), (1.0, 1.899999976158142, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.0, 1.899999976158142)}
graph2 = {(8.899999618530273, 8.0, 8.0), (8.0, 8.899999618530273, 8.0), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 7.099999904632568), (8.0, 7.099999904632568, 8.0), (8.0, 8.0, 8.899999618530273)}
现在的问题是，即使我找到了组成每个图形的顶点，我也不再有为每个对象创建单独的 3D 网格的简单方法。而之前，verts[faces] 用于创建网格，如何将每个 graph 与 faces 相关联以创建三角形网格并不明显。我试图解决这个问题，但没有成功。例如：
verts1 = verts[0:6]
faces1 = faces[0:6]
mesh = Poly3DCollection(verts1[faces1])
这不起作用。我认为关键是找到与每个对象对应的面孔。如果这样做了，它可能会奏效。例如，我们的第一个图仅包含顶点 1 到 6。因此我们只需要引用这些顶点的 faces。作为演示，第一个图 graph1 可以使用以下方法重现（没有图 2）：
faces1 = faces[0:8]
mesh = Poly3DCollection(verts[faces1])
# and plot like above
如果我不仅可以记录顶点，还可以记录它们的索引，那么我也许可以对引用该对象的那些进行排序 faces。我会解释。第一个问题，我没有索引。这是我对对象进行排序的方式。我们首先创建一个 linelist（或 edgelist），然后我们将它们制成元组，然后使用 networkx 查找连接的组件。
# create linelist
linelist = []
for idx, vert in enumerate(faces):
for i,x in enumerate(vert):
l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])] # connect the verts of the triangle
linelist.append(l) # add to the line list
# Creates graph
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
for idx, graph in enumerate(sorted(nx.connected_components(graph),key = len, reverse = True)):
graphs.append((graph))
print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))
i+=1
我看不出networkx怎么还能记录每个顶点的索引。
其次，指向每个对象的 faces 可能是不相交的，即它可能是 faces[0:4] + faces[66] + faces[100:110]。但是，这很可能会被克服。
假设我们可以为每个图生成一个索引列表，主要问题是找到一种有效的方法来发现哪些面引用这些顶点。我的解决方案适用于这组对象，但不适用于更复杂的安排（我可以提供）。它也非常慢。不过，这里是：
objects = []
obj = []
i = 0
for idx, face in enumerate(M):
if i == 0:
obj.append(face)
i = i + 1
else:
if np.isin(face,obj).any():
obj.append(face)
else:
objects.append(obj.copy())
obj = []
obj.append(face)
i = 0
if idx == len(M)-1:
objects.append(obj.copy())
如果您已经读到这里，我对这个社区印象深刻。我认为可能使用 networkx 有一种有效的方法可以做到这一点，但我还没有找到它。
期望输出：我想像对顶点排序一样将面排序为连接的组件。 graph1 = faces[x1] + faces[x2] + ... + faces[xn].
编辑：如果有人可以帮助我进行编码，我确实有一个想法（部分感谢@Ehsan）。在分离成连通分量并找到图后，可以对每个顶点进行散列以找到原始索引。然后，可以搜索 faces，其中至少包含这些索引之一（因为如果它包含一个顶点，则它必须是 graph 的一个面）。我不确定这会有多有效。如果有一个快速的 networkx 解决方法，我会很高兴。
@Paul Broderson 回答了这个问题
为了美观，我把它放在这里：
#!/usr/bin/env python
"""
Given a list of triangles, find the connected components.
"""
import itertools
import networkx as nx
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], [ 8, 7, 6], [ 6, 9, 8], [ 7, 10, 6], [ 6, 10, 9],
[11, 7, 8], [ 9, 11, 8], [11, 10, 7], [10, 11, 9]]
#create graph
edges = []
for face in faces:
edges.extend(list(itertools.combinations(face, 2)))
g = nx.from_edgelist(edges)
# compute connected components and print results
components = list(nx.algorithms.components.connected_components(g))
for component in components:
print(component)
# {0, 1, 2, 3, 4, 5}
# {6, 7, 8, 9, 10, 11}
# separate faces by component
component_to_faces = dict()
for component in components:
component_to_faces[tuple(component)] = [face for face in faces if set(face) <= component] # <= operator tests for subset relation
for component, component_faces in component_to_faces.items():
print(component, component_faces)
# (0, 1, 2, 3, 4, 5) [[2, 1, 0], [0, 3, 2], [1, 4, 0], [0, 4, 3], [5, 1, 2], [3, 5, 2], [5, 4, 1], [4, 5, 3]]
# (6, 7, 8, 9, 10, 11) [[8, 7, 6], [6, 9, 8], [7, 10, 6], [6, 10, 9], [11, 7, 8], [9, 11, 8], [11, 10, 7], [10, 11, 9]]
编辑：我已经写了这个问题的更简洁的版本
给定一个 3D numpy 数组，marching cubes can form a 3D object 在某个阈值附近。
import numpy as np
from skimage import measure
A = np.zeros((12,12,12))
#A[A<1] = -1
for i in np.arange(1,2):
for j in np.arange(1,2):
for k in np.arange(1,2):
A[i,j,k] = 10
for i in np.arange(8,9):
for j in np.arange(8,9):
for k in np.arange(8,9):
A[i,j,k] = 10
verts, faces, normals, values = measure.marching_cubes_lewiner(A,1)
# which returns
verts = [[0.1, 1., 1. ] [1., 1., 0.1] [1., 0.1, 1. ] [1., 1., 1.9] [1., 1.9, 1. ]
[1.9, 1., 1. ] [7.1, 8., 8. ] [8., 8., 7.1] [8., 7.1, 8. ] [8., 8., 8.9]
[8., 8.9, 8. ] [8.9, 8., 8. ]]
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] [ 8, 7, 6] [ 6, 9, 8] [ 7, 10, 6] [ 6, 10, 9]
[11, 7, 8] [ 9, 11, 8] [11, 10, 7] [10, 11, 9]]
这可以绘制：
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
from mpl_toolkits.mplot3d import Axes3D
mesh = Poly3DCollection(verts[faces])
mesh.set_edgecolor('k')
mesh.set_facecolor('b')
ax.set_xlim(0,10)
ax.set_ylim(0,10)
ax.set_zlim(0,12)
返回这个可爱的 3D 图像：
我使用我自己的代码（见下文）使用一种算法来分离这些对象并得到：
graph1 = {(1.0, 1.0, 0.10000000149011612), (1.899999976158142, 1.0, 1.0), (0.10000000149011612, 1.0, 1.0), (1.0, 1.899999976158142, 1.0), (1.0, 0.10000000149011612, 1.0), (1.0, 1.0, 1.899999976158142)}
graph2 = {(8.899999618530273, 8.0, 8.0), (8.0, 8.899999618530273, 8.0), (7.099999904632568, 8.0, 8.0), (8.0, 8.0, 7.099999904632568), (8.0, 7.099999904632568, 8.0), (8.0, 8.0, 8.899999618530273)}
现在的问题是，即使我找到了组成每个图形的顶点，我也不再有为每个对象创建单独的 3D 网格的简单方法。而之前，verts[faces] 用于创建网格，如何将每个 graph 与 faces 相关联以创建三角形网格并不明显。我试图解决这个问题，但没有成功。例如：
verts1 = verts[0:6]
faces1 = faces[0:6]
mesh = Poly3DCollection(verts1[faces1])
这不起作用。我认为关键是找到与每个对象对应的面孔。如果这样做了，它可能会奏效。例如，我们的第一个图仅包含顶点 1 到 6。因此我们只需要引用这些顶点的 faces。作为演示，第一个图 graph1 可以使用以下方法重现（没有图 2）：
faces1 = faces[0:8]
mesh = Poly3DCollection(verts[faces1])
# and plot like above
如果我不仅可以记录顶点，还可以记录它们的索引，那么我也许可以对引用该对象的那些进行排序 faces。我会解释。第一个问题，我没有索引。这是我对对象进行排序的方式。我们首先创建一个 linelist（或 edgelist），然后我们将它们制成元组，然后使用 networkx 查找连接的组件。
# create linelist
linelist = []
for idx, vert in enumerate(faces):
for i,x in enumerate(vert):
l = [np.ndarray.tolist(verts[faces[idx][i]]), np.ndarray.tolist(verts[faces[idx][(i+1)%len(vert)]])] # connect the verts of the triangle
linelist.append(l) # add to the line list
# Creates graph
tmp = [tuple(tuple(j) for j in i) for i in linelist]
graph = nx.Graph(tmp)
graphs = []
i=0
for idx, graph in enumerate(sorted(nx.connected_components(graph),key = len, reverse = True)):
graphs.append((graph))
print("Graph ",idx," corresponds to vertices: ",graph,'\n\n',file=open("output.txt","a"))
i+=1
我看不出networkx怎么还能记录每个顶点的索引。
其次，指向每个对象的 faces 可能是不相交的，即它可能是 faces[0:4] + faces[66] + faces[100:110]。但是，这很可能会被克服。
假设我们可以为每个图生成一个索引列表，主要问题是找到一种有效的方法来发现哪些面引用这些顶点。我的解决方案适用于这组对象，但不适用于更复杂的安排（我可以提供）。它也非常慢。不过，这里是：
objects = []
obj = []
i = 0
for idx, face in enumerate(M):
if i == 0:
obj.append(face)
i = i + 1
else:
if np.isin(face,obj).any():
obj.append(face)
else:
objects.append(obj.copy())
obj = []
obj.append(face)
i = 0
if idx == len(M)-1:
objects.append(obj.copy())
如果您已经读到这里，我对这个社区印象深刻。我认为可能使用 networkx 有一种有效的方法可以做到这一点，但我还没有找到它。
期望输出：我想像对顶点排序一样将面排序为连接的组件。 graph1 = faces[x1] + faces[x2] + ... + faces[xn].
编辑：如果有人可以帮助我进行编码，我确实有一个想法（部分感谢@Ehsan）。在分离成连通分量并找到图后，可以对每个顶点进行散列以找到原始索引。然后，可以搜索 faces，其中至少包含这些索引之一（因为如果它包含一个顶点，则它必须是 graph 的一个面）。我不确定这会有多有效。如果有一个快速的 networkx 解决方法，我会很高兴。
@Paul Broderson 回答了这个问题
为了美观，我把它放在这里：
#!/usr/bin/env python
"""
Given a list of triangles, find the connected components.
"""
import itertools
import networkx as nx
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], [ 8, 7, 6], [ 6, 9, 8], [ 7, 10, 6], [ 6, 10, 9],
[11, 7, 8], [ 9, 11, 8], [11, 10, 7], [10, 11, 9]]
#create graph
edges = []
for face in faces:
edges.extend(list(itertools.combinations(face, 2)))
g = nx.from_edgelist(edges)
# compute connected components and print results
components = list(nx.algorithms.components.connected_components(g))
for component in components:
print(component)
# {0, 1, 2, 3, 4, 5}
# {6, 7, 8, 9, 10, 11}
# separate faces by component
component_to_faces = dict()
for component in components:
component_to_faces[tuple(component)] = [face for face in faces if set(face) <= component] # <= operator tests for subset relation
for component, component_faces in component_to_faces.items():
print(component, component_faces)
# (0, 1, 2, 3, 4, 5) [[2, 1, 0], [0, 3, 2], [1, 4, 0], [0, 4, 3], [5, 1, 2], [3, 5, 2], [5, 4, 1], [4, 5, 3]]
# (6, 7, 8, 9, 10, 11) [[8, 7, 6], [6, 9, 8], [7, 10, 6], [6, 10, 9], [11, 7, 8], [9, 11, 8], [11, 10, 7], [10, 11, 9]]