How can I find connected points on a graph in 3D?-CodePudding

I have a 1000 set of x, y and z coordinates and I want to find how they cluster. I'd like to set a maximum distance that will specify that points belong in the same cluster i.e. if the point has a Euclidean distance of less than 1 from another point, the algorithm will cluster them together. I've tried to brute force this on python with little success, does anyone have any ideas or a pre-established algorithm that does something similar?

Thanks in advance

CodePudding user response：

You can find quite a few clustering algorithms in module scikit-learn: https://scikit-learn.org/stable/modules/clustering.html

With your particular definition of clusters, it appears that sklearn.cluster.AgglomerativeClustering(n_clusters=None, distance_threshold=1) is exactly what you want.

import numpy as np
from sklearn.cluster import AgglomerativeClustering

N = 1500
box_size = 10

points = np.random.rand(N, 2) * box_size
# array([[5.93688935, 6.63209391], [2.6182196 , 8.33040083], [4.35061433, 7.21399521], ..., [4.09271753, 2.3614302 ], [5.69176382, 1.78457418], [9.76504841, 1.38935121]])

clustering = AgglomerativeClustering(n_clusters=None, distance_threshold=1).fit(points)

print('Number of clusters:', clustering.n_clusters_)
# Number of clusters: 224

An alternative approach would have been to build a graph, then get the connected components of the graph, using for instance module networkx: networkx.algorithms.components.connected_components