python在一个包含三个元素的3D图形/元组中查找连接的组件?

1. 你说的是一个节点的6个可能邻居 (i, j, k) 在三维图形中,用“邻接”表示邻接节点和相邻节点之间的距离为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

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

cKDTree 在1的距离内找到邻居 query_pairs

然后我们用这些边创建networkx图 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
• 数据帧 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
...

• 基于数据帧 数据框

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

查找连接组件的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. 组成部分)
2. 3. 如果没有访问该点,则从该点开始启动一个DFS

DFP公司: (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]]]

可视化:

两个相对的边是两个不同的连接组件

[[[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()