2d Voronoi around a set of curves instead of a set of points?

If I have a bunch of circles or closed curves and I want to draw lines that are as close to equidistant from them as possible, how do I do it?

A voronoi diagram made with the 2dvoronoi component does this for curves.

I want to be able to do it for any set of closed curves, including polylines, closed curves with centroids outside of themselves, polycurves with segments that have different degrees, etc. Just any closed curve.

In the drawing below, the red lines are a grasshopper voronoi diagram of the red points.

The blue lines between the blue circles are my eyeball approximation of what lines equidistant from the circles might look like (I think I’m close, but I could be wrong).

How can I use grasshopper to produce the blue voronoi diagram? (or rather, how can I produce a mathematically correct version of my guess?)

Here’s an attempt, probably not very robust. It uses Clipper and the Remove Duplicate Lines from Kangaroo and Mesh Dual. I have no idea at this point whether this component is native GH.

voronoi from curves.gh (16.5 KB)

1 Like

Hello
The theory is quite simple if you look what Voronoi diagram is

You need to make cones pyramid … From your curves then search for the intersection.
Here the script, without intersection calculation, I think Ethan solution will be more robust. He did something near Medial Axis (there are many links)


I also used Clipper as there are some problems offsetting some curves. Instead of offseting then loft you could use Pufferfish “Extrude Tapered PolySurface” but there are also some fails …
voronoi from curves LD.gh (18.2 KB)

4 Likes

Thanks. Late last night I actually found your medial axis definition from last year and tried it.

It worked perfectly visually, but I couldn’t get it to produce closed polycurves reliably, even when I used them to split a rectangle and then used the new surface borders. Because I’m using this to create machining regions in RhinoCAM, I need to output closed, non-self-intersecting curves.

I’ll play with these definitions and see how I do. The cones seem promising because they seem like they’ll avoid the degree2 curves from that old definition, which I think was the reason I couldn’t get closed polylines.

I put a little script to cut the brep and keep upper BREP


It was one of my attempts to make Manhattan Voronoi, it is quite long so I use a Parallel.For
voronoi from curves LD.gh (21.4 KB)


Some data management to keep lower curves
voronoi from curves LD.gh (20.1 KB)

The kangaroo 1 component has a kangaroo 2 equivalent, so that’s easy.

I can’t find the mesh dual component anywhere. Weaverbird has a dual graph component, but it won’t work.

What exactly does mesh dual do?

I guess it’s this old one:

1 Like

The Dual Graph basically takes a graph (mesh) and connects the centers of the faces to give a new graph. For example, the Delaunay mesh is the dual of the Voronoi, and vise-versa. The same idea applies in 3D, where faces become vertices and vertices become faces, so the tetrahedron is the dual of the cube.

I think my version of Mesh Dual came from this page, but i’m just guessing. The dates seem to correspond.

Your algorithm is VERY robust. The number of curve divisions and the “second number” slider only need to be changed from your settings very rarely - mostly when I was trying as hard as I could to break it with odd curves very near each other.

I finally downloaded that mesh dual component. @DanielPiker is correct. It is the one from that blog.
If anyone else needs to do voronoi around curves, here is that component: MeshDual.gha (9.5 KB)

I tweaked your definition a little bit, and created a clustered version. I eliminated Clipper. Instead I use Laurent’s surface split method.

Here is my variation of your Voronoi from Curves: voronoi from curves + clustered version.gh (47.5 KB)

My version requires Pufferfish and Kangaroo 2 in addition to the component above. Pufferfish may be avoidable, but everybody has it anyway, so I left it in.

The one thing that @laurent_delrieu’s algorithm does that yours does not is that it sees overlapping curves as one curve. Yours returns errors. Not sure how one would avoid that, and it’s not an immediate concern for me, I just won’t use that kind of input.

I am still trying to figure out the tree voodoo I need to use in order to shatter the voronoi division lines, reconstruct them as degree 3 spline curves, and maybe add an option for smoothing. I don’t need it for my purposes, but it would be prettier for sure. Once I’ve figured it out, I’ll add to this post.

Thanks for your help everybody!

1 Like

Who knew??? Just curious, what do you plan to do with it?

It’s such a simple thing: I’m going to use it to generate regions for CNC routing.

For freeform curving surfaces, when they have a lot of bumps or hills, a radial machining path can make a lot of sense because it comes very close to carving up and down the hills. This is more efficient than doing a bunch horizontal passes or parallel passes because either of those often require clean up.

So I use voronoi to map the hills. I initially used high points, but that can be quirky and not line up quite right. Using contours in the middle of the hills combined with curve voronoi makes it perfect.