A subtractive method of creating minimal spanning tree networks with optional hierarchical clustering.
The example file below is sequentially removing edges from a voronoi graph until no more edge can be removed without splitting the tree in separate parts.
Entagma released a tutorial series on 'Clustering' by Jeroen Claus showing an additive procedure:
https://entagma.com/courses/advanced-setups/advanced-setups-21-jeroen-claus-hdbscan
# Add code to modify contents of geo.
geo = kwargs['inputs'][0].freeze()
import numpy as np
points_list = [p.position() for p in geo.points()]
n = len(points_list)
if n > 1:
pts = np.array(points_list)
dist = np.sqrt(np.sum((pts[:, None, :] - pts[None, :, :])**2, axis=-1))
selected = np.zeros(n, dtype=bool)
selected[0] = True
min_weight = dist[0].copy()
min_weight[0] = np.inf
parent = np.zeros(n, dtype=int)
for _ in range(n - 1):
masked_weight = np.where(selected, np.inf, min_weight)
u = np.argmin(masked_weight)
selected[u] = True
p0 = geo.point(int(parent[u]))
p1 = geo.point(int(u))
prim = geo.createPolygon()
prim.addVertex(p0)
prim.addVertex(p1)
mask = ~selected & (dist[u] < min_weight)
min_weight[mask] = dist[u][mask]
parent[mask] = u
return geo
# Add code to modify contents of geo.
geo = kwargs['inputs'][0].freeze()
import numpy as np
from scipy.spatial import distance_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
points_list = [p.position() for p in geo.points()]
n = len(points_list)
if n > 1:
pts = np.array(points_list)
dist = distance_matrix(pts, pts)
mst = minimum_spanning_tree(dist)
rows, cols = mst.nonzero()
for u, v in zip(rows, cols):
p0 = geo.point(int(u))
p1 = geo.point(int(v))
prim = geo.createPolygon()
prim.addVertex(p0)
prim.addVertex(p1)
return geo