Expanding boundaries to evenly fill space

[stu92]

I have a series of non-intersecting planar boundaries that I would like to be able to expand towards one another and evenly absorb the space between them, as is in the sketch attached. Does anyone have any ideas of how to achieve this? I had thought that it may be possible to create lines from the end points of each edge, find the midpoint and join these points to create new boundary edges, but as soon as the starting geometry becomes not parallel or differ in the number of edges they have this doesn’t work too well. Voronoi was something else I had thought of, but I don’t really know the possibilities of this tool well enough to think of a process.

Any other suggestions?

[laurent_delrieu]

Something with Medial Axis could help

medial axis sepration.gh (12.1 KB)

The usage on this forum is to post data, it helps not reconstructing something from text or pictures. “The devil is in the detail”

[stu92]

This is a nice solution, thanks! I’ve never fully understood Voronoi before so this was quite a beneficial question for me to ask.

Is there a way to get rid of the ‘curved’ corners? This will be applied largely to orthogonal shapes and so I would like the new boundaries to more or less be parallel to the original shapes. The left pic is using the standard Voronoi component, the pic on the right has had the OrthoVoronoi component swapped in. I was hoping this would resolve the issue but all it seems to do is create lots of little steps where a curve would exist.

Any thoughts? Again sorry for not posting code for others to look at, I would do that if I knew what to do myself!

[stu92]

I’ve just been reading through this thread, it looks like this is something you’ve talked about before! I’m a relative novice at grasshopper never mind C# etc, is what I’m trying to achieve something that is beyond my abilities?

Straight Skeleton "Implementation"

There is a modified implementation of Felkel & Obdrzalek’s algorithm ported from Java to C# here: https://github.com/reinterpretcat/csharp-libs/tree/master/straight_skeleton. One thing to note is that a robust implementation of Straight Skeleton calculation is quite a complicated algorithm and has a lot of edge cases (as Tom Kelley (“twak”) demonstrates) I’ve used the C# code in Rhino/GH by rebuilding Rhino Polylines into the library’s own geometry primitives – see code below. Because this algo…

[stu92]

Me again, sorry for the conversation with myself…

I saw this animation below and it’s sort of what I’m trying to achieve. I want to be able to offset the curves outwards evenly until they touch one another. That would prevent me having the curved/staggered geometry. I guess I almost want to treat each curve as a cell rather than creating a series of points along the curve the generate the cells.

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/Voronoi_growth_euclidean.gif/220px-Voronoi_growth_euclidean.gif

[HS_Kim]

It’s doable with native Voronoicomponent. It has the Radius input…

[laurent_delrieu]

Hello
transforming curve to curve oriented just in 2 directions, X and Y is surely doable. You can use this or something like this.

Manhattan and Chebyshev

[stu92]

@HS_Kim I am not sure how to achieve the offset of a curve using the Voronoi component and the radius input. The script Laurent posted earlier used Voronoi to create the medial axis by creating a series of points along the curve, I want to offset the curve itself until it hits another offset curve much like an expanding Voronoi cell would stop expanding when it hits another expanding Voronoi cell. Any ideas?

@laurent_delrieu Manhattan is closer to what I am trying to achieve, but it unfortunately only gives me one right turn (unless I’m doing something wrong!). I would like to be able to control the number of right turns in some way, for example in my screenshot below where there are clear bends in the curve. I tried looking at the FitLine component but it doesn’t work with polylines, I can only obtain a best fit line through all points and not just ones in a predominately x- or y-axis orientation.

190716 - Straighten Curve WIP.gh (43.3 KB)

[laurent_delrieu]

Here a simple way to do that with mesh (here quad mesh), you just have to use the slider.
I put a little C# to put data in Branch, there is surely a component but as I mostly program in C# it is more simple for me

190716 - Straighten Curve WIP_LD.gh (48.4 KB)

[stu92]

This looks just what I am looking! The only issue there appears to be is with the ‘Brep Closest Point’ component, I guess this is what you added C# to? It won’t load for me to test and explore

Could you explain briefly what it was you tweaked to get this effect?

[laurent_delrieu]

I put the old Brep closest point from Rhino 5 so it must now work for you.
The logic is simple

1. Divide the surface with curves (it allows to suppress part of curves not linked)
2. Make a division of the surface (here a mesh) on the surface
3. For each division (face of the mesh) search the distance from the surface division
4. Make a index for each surface (with series component)
5. Order the distance and index
6. Take the first distance/index, so the closest surface division from mesh face
7. Put each face in a branch of tree (use of the C#, but I am sure there is a component for that)
8. Join the faces on each branch so it becomes a mesh
9. Extract the edges of the meshes

There are others strategies :

• populate each surface division with mesh faces, make each “island” grow. I have a script for that but I don’t want to share it (Mesh clustering)
• Make a program that takes the curves and simplify them

[stu92]

Amazing, thanks a lot. I’m going to try and reconstruct this myself to learn the process better, your explanation of the logic was very useful!

[stu92]

I stumbled across the below thread with @laffarguee and @anikolo by chance earlier, and it has got me thinking about how to go about this task for non-rectilinear starting boundaries.

Voronoi curve trim with surface

Region intersection between voronoi cells and borders. For more help pls upload file with internalized geometry. (at least a sample)

It appears that the pink curves have been used to form the regions, but how would one go about generating this pink centreline if the regions were the starting point? The starting boundaries may not always be equidistant apart as in this example, but would you be able to easily create a centreline for non-parallel lines in a similar way to before?

[laurent_delrieu]

What is the difference with that ?

Expanding boundaries to evenly fill space

Something with Medial Axis could help [image] medial axis sepration.gh (12.1 KB) The usage on this forum is to post data, it helps not reconstructing something from text or pictures. “The devil is in the detail” [image]

[stu92]

I guess that actually is what I was looking for!

The issue was that the regions were very close together and the medial axis wasn’t generating, but once I increased the number of division points sufficiently it seemed to work better. Thanks!

[laurent_delrieu]

The problem you mention is also a good reminding that it is always better to post YOUR data and script.

[stu92]

So I am still playing about with this and trying to figure out how this works.

I am trying to achieve this without using meshes or c#, mainly because I want to learn to walk before running! I have started with a similar approach as before (create grid, divide surface, etc) but am not great with trees! Can you elaborate a little more on putting faces into branches of a tree please?

An alternative approach I thought of was to divide the boundary curves and then pull these points to the closest grid line. I could then dispatch all lines that had a point on them and use those curves to split the original surface. I think this will probably cause a few issues where the bends in the curve are only picked up by one edge rather than two, etc, but how would I go about testing for a point/line intersection? Does this approach have any mileage in it do you think?

Sorry for still going on with this, but I want to try and learn!

190725 - Boundary Expansion - WIP.gh (31.3 KB)

[jasongberger (JB)]

I’ve been following this thread and have actually enjoyed trying the challenge, teaching myself a few things along the way. I’ve been working on another method independent of Voronoi, but it still needs some work and inspiration. In the meantime, I have a few responses…

@laurent_delrieu

I put a little C# to put data in Branch, there is surely a component but as I mostly program in C# it is more simple for me

@laurent_delrieu and @stu92, I put together an alternative to using the C# code, see attached. I couldn’t think of a component alternative to your code, so I took a slightly different route. I thought the sorting of the Series is a pretty interesting technique. Personally, I like to avoid meshes unless necessary, but it seems to be pretty useful here.
190716 - Straighten Curve WIP_LD_NoC#.gh (65.0 KB)

---

@stu92 Here are some notes I took when looking over your file:
190725 - Boundary Expansion - WIP-Comment 190725.gh (42.0 KB)

I like what you did with the sorting the two offset curves by length and choosing the longest side. Alternatively, I’d use the flip C (component) using a GH constructed circle as the guide.

The reason why @laurent_delrieu sorts the point distances is to select the closest point in the brep, which becomes the first point in the path, and then translates it into something his C# code could work with. When you grafted the four regions, the BrepCP stopped analyzing each point by all four regions and paired them off, analyzing the first of each list, then the second, and so on (see the image). I hope this answers your first question.

I’m not certain I follow your logic in the second question, but you can use ‘Curve Closest Point’ for the point/line intersection and test for which points have a 0 distance. Hope that helps.

Btw, not to be ‘that guy,’ but “tree?” is not a question!

---

If I can’t finish or make any progress in my version in a week or so, I’ll share it and see if anyone here has any ideas to make it work.

[stu92]

Wow, that was really helpful. I think I have understood this a bit more as a result of there being no c# and I follow your logic. I’ll be taking it apart and putting back together now to really test my understanding!

If I’m being honest I still don’t fully understand how to use trees to my benefit but am working on it. I hate to be ‘that guy’ also, what it really should have said was “I then believe there to be some sort of process involving sorting data in trees, but I haven’t a clue where to begin”!

My logic on the second point is flawed the more I investigate. The issue comes where there is a bend in the curve, and only one edge of the grid surface is selected as opposed to the two required for a 90 degree angle. Back to the drawing board on that one!

[jasongberger (JB)]

Well, I’m spent. I was hoping to figure it out myself, but it’s distracting (and draining) me too much . I hope some of the geniuses out there can fill in the gaps…if anything, I may learn a new trick.

190730 - Expanding Boundaries.gh (82.9 KB)

-The first step was to divide the inner boundary into rectangles.
-The second (missing) step is to combine these small rectangles into ‘parent,’ overlapping rectangles.
-Third step is to make and split lines that run between those parent rectangles.
-The fourth (missing) step is to filter out the unwanted split lines to get the desired paths.

For the second step, I was thinking we could make every rectangle combination possible and deduct the rectangles that are completely within another, but when I tried it, I was still getting intersection results between the child and parent rectangles (maybe we could dispatch based on more-than-1 intersection curves?). I was also wondering if there could be a method using mesh components, something that could test for rectangles that are adjacent to one another.

For the fourth step, I was thinking that of among the parallel segments, we can choose the one that has the highest ratio of their body in their respective rectangular areas (maybe place points along each segment and choose the one with the most points in each parent rectangle?). Also, I was thinking we could at least filter out any segments that are only intersected by another segment once.

For a little something extra, a filter can be added for paths that lead out to the boundary, or remove paths that lie between the plots and boundary.

---

Is this the sort of solution you were looking for @stu92?

Can’t wait to see if anyone can fill in the missing steps!