python 在具有三个元素的 3D 图形/元组中找到连接的组件？

Question

我有一个二进制 3D numpy 数组，我想为它找到连接的组件，i.d.值为 1 的相邻元素。

data = np.random.binomial(1, 0.4, 1000)
data = data.reshape((10,10,10))

或者，我可以获得每个值为 1 的元素的坐标，并获得一组包含三个元素的列表，我可以获得相邻的簇

coordinates = np.argwhere(data > 0)

connected_elements = []
for node in coordinates:
  neighbors = #Get possible neighbors of node
  if neighbors not in connected_elements:
    connected_elements.append(node)
  else:
    connected_elements.index(neighbor).extend(node)

我该怎么做，或者如何为 3D 设置实现 2D connected_components 函数？

Answer 1

就像问题中建议的那样，我们首先生成数据并找到坐标。

然后我们可以使用k-d树cKDTree使用 query_pairs 查找距离为 1 的邻居并将它们用作图的边，这实质上将问题简化为标准的图连通分量搜索。

然后我们用 from_edgelist 从这些边创建 networkx 图并运行 connected_components找到连接的组件。

最后一步是可视化。

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial.ckdtree import cKDTree
from mpl_toolkits.mplot3d import Axes3D

# create data
data = np.random.binomial(1, 0.1, 1000)
data = data.reshape((10,10,10))

# find coordinates
cs = np.argwhere(data > 0)

# build k-d tree
kdt = cKDTree(cs)
edges = kdt.query_pairs(1)

# create graph
G = nx.from_edgelist(edges)

# find connected components
ccs = nx.connected_components(G)
node_component = {v:k for k,vs in enumerate(ccs) for v in vs}

# visualize
df = pd.DataFrame(cs, columns=['x','y','z'])
df['c'] = pd.Series(node_component)

# to include single-node connected components
# df.loc[df['c'].isna(), 'c'] = df.loc[df['c'].isna(), 'c'].isna().cumsum() + df['c'].max()

fig = plt.figure(figsize=(10,10))
ax = fig.add_subplot(111, projection='3d')
cmhot = plt.get_cmap("hot")
ax.scatter(df['x'], df['y'], df['z'], c=df['c'], s=50, cmap=cmhot)

输出:

注意事项:

• 在生成节点时，我将二项式分布的概率从 0.4 降低到 0.1，以使可视化更“可读”
• 我没有显示仅包含单个节点的连接组件。这可以通过取消注释 # to include single-node connected components comment
下面的行来完成
• DataFrame df 包含坐标x、y 和z 以及连通分量索引c对于每个节点:

print(df)

输出:

     x  y  z     c
0    0  0  3  20.0
1    0  1  8  21.0
2    0  2  1   6.0
3    0  2  3  22.0
4    0  3  0  23.0
...

• 基于 DataFrame df，我们还可以检查一些有趣的东西，例如找到的最大连通分量的大小(以及连通分量编号):

df['c'].value_counts().nlargest(5)

输出:

4.0    5
1.0    4
7.0    3
8.0    3
5.0    2
Name: c, dtype: int64