Python如何在3D图中找到连通组件？（元组有三个元素）

Question

我有一个二进制的3D numpy数组，想要找到连通组件，即相邻元素的值为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函数？

- hirschme

---

你只能沿着轴移动以查找连接组件，还是可以横跨移动？ - mujjiga

Answer 1

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

然后我们可以使用 k-d 树cKDTree通过 query_pairs 在距离为 1 的范围内查找邻居，并将它们用作图的边缘，这实际上将问题简化为标准图连接组件搜索。

然后我们使用 from_edgelist 创建网络图，并使用 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可以实现。
• 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

- perl

Answer 2

使用DFS查找联通分量

最初的回答

import queue
import itertools
n = 10

def DFS(data, v, x,y,z, component):
    q = queue.Queue()
    q.put((x,y,z))
    while not q.empty():
        x,y,z = q.get()
        v[x,y,z] = component

        l = [[x], [y], [z]]

        for i in range(3):
            if l[i][0] > 0:
                l[i].append(l[i][0]-1)
            if l[i][0] < v.shape[1]-1:
                l[i].append(l[i][0]+1)

        c = list(itertools.product(l[0], l[1], l[2]))
        for x,y,z in c:
            if v[x,y,z] == 0 and data[x,y,z] == 1:
                q.put((x,y,z))

data = np.random.binomial(1, 0.2, n*n*n)
data = data.reshape((n,n,n))

coordinates = np.argwhere(data > 0)
v = np.zeros_like(data)

component = 1
for x,y,z in coordinates:
    if v[x,y,z] != 0:
        continue
    DFS(data, v, x,y,z, component)
    component += 1

最初的回答：

主要算法：

1. 将每个点的visited设为0（表示它尚未成为任何连通组件的一部分）
2. 对于所有值等于1的点：
   
   3. 如果该点未被访问，请从该点开始进行深度优先搜索（DFS）

DFP：这是使用队列的传统DFS算法。在3D情况下，唯一不同的是，给定(x,y,z)，我们使用itertools.product计算其所有有效邻居。在3D情况下，每个点都有27个邻居，包括自身（3个位置和3个可能的值-相同、增量、减量，因此有27种方法）。

矩阵v存储从1开始编号的连通组件。

测试用例：

当数据为

 [[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[1 1 1]
  [1 1 1]
  [1 1 1]]]

可视化： 这个算法返回节点v，其中两个相对的边是两个不同的连通分量。

[[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[2 2 2]
  [2 2 2]
  [2 2 2]]]

"最初的回答"

正确的。

可视化： 如可视化所示，绿色表示一个连通分量，蓝色表示另一个连通分量。

可视化代码。

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def plot(data):
    fig = plt.figure(figsize=(10,10))
    ax = fig.gca(projection='3d')

    for i in range(data.shape[0]):
        for j in range(data.shape[1]):
            ax.scatter([i]*data.shape[0], [j]*data.shape[1], 
            [i for i in range(data.shape[2])], 
                   c=['r' if i == 0 else 'b' for i in data[i,j]], s=50)

plot(data)
plt.show()
plt.close('all')
plot(v)
plt.show()

- mujjiga

Answer 3

假设：

1. 你正在讨论一个三维图中节点 (i, j, k) 的6个可能邻居，并且通过“邻居”指的是邻居与节点之间的距离为1； 2. “有效连接组件”意味着节点A和节点B是邻居，且两个值都为1。

那么我们可以有以下函数来获取可能的邻居：

def get_neighbors(data, i, j, k):
    neighbors = []
    candidates = [(i-1, j, k), (i, j-1, k), (i, j, k-1), (i, j, k+1), (i, j+1, k), (i+1, j, k)]
    for candidate in candidates:
        try:
            if data[candidate] == 1:
                neighbors.append(candidate)
        except IndexError:
            pass
    return neighbors

- X. W