Voronoi Dynamo

, ,
1

Isn’t “Voronoi.ByParameterOnSurface“ different from the original definition of Voronoi?

Is there a way to create a Voronoi diagram without using Voronoi.ByParameterOnSurface?

I am trying to create a model using random points placed on a surface as seed points.

2

You can use Python but the result is almost exactly the same

alt_voronoi
alt_voronoi2946×936 224 KB

import numpy as np
from scipy.spatial import Voronoi

points = list(zip(*IN[0]))

vor = Voronoi(points)

# Code from Scipy
# https://github.com/scipy/scipy/blob/main/scipy/spatial/_plotutils.py#L138

center = vor.points.mean(axis=0)
ptp_bound = np.ptp(vor.points, axis=0)

finite_segments = []
infinite_segments = []
for pointidx, simplex in zip(vor.ridge_points, vor.ridge_vertices):
    simplex = np.asarray(simplex)
    if np.all(simplex >= 0):
        finite_segments.append(vor.vertices[simplex])
    else:
        i = simplex[simplex >= 0][0]  # finite end Voronoi vertex

        t = vor.points[pointidx[1]] - vor.points[pointidx[0]]  # tangent
        t /= np.linalg.norm(t)
        n = np.array([-t[1], t[0]])  # normal

        midpoint = vor.points[pointidx].mean(axis=0)
        direction = np.sign(np.dot(midpoint - center, n)) * n
        if (vor.furthest_site):
            direction = -direction
        aspect_factor = abs(ptp_bound.max() / ptp_bound.min())
        far_point = vor.vertices[i] + direction * ptp_bound.max() * aspect_factor

        infinite_segments.append([vor.vertices[i], far_point])

OUT = finite_segments

p.s. they probably both use the same library from qhull.org

1 Like
3

Thank you for the advice.

Will the line segments generated using this node be perpendicular bisectors of each generating point?

When using “Voronoi.ByParameterOnSurface“, there are some places that do not seem to be perpendicular bisectors.

image
image1214×683 71.8 KB

4

I’m not sure, from the Qhull documentation

Qhull computes the Voronoi diagram via the Delaunay triangulation. Each Voronoi vertex is the circumcenter of a facet of the Delaunay triangulation

5

It’s always been by UVs @n-nomi - just convert the points to UV using Surface.UVParameterAtPoint.

The Dynamo team is tracking a bug for handling of edge conditions, but it’s been a lower priority for quite awhile now.