Minimal Spanning Tree with Clustering

calendar_today

15.04.2023

label

Modeling, Python

mouse

Houdini 19.5

Description

A subtractive method of creating minimal spanning tree networks with optional hierarchical clustering.

1 File

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.

2 Source

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

3 Python Numpy

PYTHON
        # 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
    

4 Python Scipy

PYTHON
        # 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
    
download

Downloads

smart_display

Videos

Graph Theory for Visual Learners

link

Related articles

favorite

398

label

Modeling

Adaptive Resampling of Curves

favorite

480

label

Modeling

Applying Scales to Mesh Surfaces

favorite

460

label

Modeling

Approximating Subdivision Surfaces

favorite

82

label

Modeling

Copying Barb Wire along Curve

favorite

397

label

Modeling

Blending COPs SDFs into 3D Volume

favorite

542

label

Modeling

Branching Subdivision Curves