How to get boundary curves for Curve.CreateBooleanRegions?

Hi,

Is it possible to get original curves linked with created boundary curve when using Curve.CreateBooleanRegions?

I want to to use boundary curves to create hatches with the same color as the original curves forming the boundary (please see the picture below). Is there an efficient way how to achieve this? I want to avoid reversely searching for the curves by checking the intersections with the boundary curve if possible…

CurveBooleanRegions Class

Thanks for help or clue!

Michal

This requires a medium level of coding skills (and a full knowledge of connectivity matters). That said there’s various ways to do it but the fastest - by far - is done in 2 steps:

  1. First get all the segments (and their connectivity [notably VV, EV]) derived from crv/crv ccx events.
  2. Then using solely the connectivity Trees find [I would suggest recursion] the primary closed cirquits, sample the related segments in a tree and then join them into a closed Curve (and/or make a planar Brep out of that). This approach is kinda similar with finding islands in Graphs using solely the VV connectivity.

The 1st is rather easy. The 2nd is a bit tricky (and anything related with cirquits/islands is strictly internal to the practice).

But I could provide a hint or two if you post some WIP C#.


Note that the 2d case as above is in fact a subset of the general case and it can been solved by splitting the BrepFaces (but requires using 2 Crv Lists and is rather slow).

1 Like

Thanks for the reply Peter! Medium level of coding skill is ok. Knowledge of connectivity is none,) I will do some research on that matter. So far I managed to make it work with curve intersections but it is obviously very inefficient for large dataset. I thought optimize that with RTree search. I’ll look at it and come back here with some examples. Thanks!

Hard to see the point unless you really deal with lot’s of Curves.

Anyway: In a nested loop … for each (valid and planar) Curve (say: the current) in the crvList you should get the ccx events (say: double[ ] t) VS the rest, sample t’s in a tList split the current Curve (using the tList) and add the pieces to a pieces curves List. At the same time you should deal with the pieces connectivity since this is critical for recursively find the cirquits. That said … given the connectivity that part is almost real-time fast since we are talking solely int ops.

But first take a break and get the gist of connectivity. Given 2 Lists of things connectivity is a DT (of type int) [or an int[ , ] array] where the last path dim is the index of the item in the 1st List and the content are indices of the items in the 2nd List. That way we correlate, say, vertices to edges. In real-life connectivity Trees have at least 2 dimensions (for instance: get a List of Meshes and do the CT’s where the 1st dim is the index of the Mesh in the List).

Note : same If the 2 Lists are just 1 List (say vertices to vertices).

Note: a good challenge to master connectivity is to get a Mesh and try to do the 9 connectivity Trees that correlate TopologyVertices, TopologyEdges and Faces (3 classes of objects: meaning 3*3 = 9 possible combos).

An other break MAY be the one required for the recursion: what is, why to use, what are the pros/cons etc etc.

BTW: If you are in the AEC market sector and the scope is to create some sort of facade … then cirquits are 1% of the problem because you’ll need a packing solution (otherwise the pieces - hydro/laser cut from a sheet - may cost an arm and a leg due to the wasted material [unless they are custom tiles]).

BTW: Using another C# (far better optimized for the task) for ~600 cirquits Rhino needs 2.5X the time required for the solution in order to make the BrepFaces (compare Elapsed for the 3 result options [just Solve, Join, make BrepFaces]).



BTW: A rather inefficient way to deal with this is to create a concave hull from the ccx pts , get the BrepFace and then split the thing using the curves: this takes a million years to finish.

Hi Michal,

Yes, what you’re looking for is a doubly-connected edge list, a data structure that represents a graph of nodes and their connections, and thus provides simple ways of extracting topological information, such as vertices, edges and faces. In your case, you’re looking for the faces.

Here’s a demo of a Python implementation, I did a while ago and use all the time.
It’s truly an amazing data structure and very useful for many things!

There is lots of material and sample code online about doubly-connected edge lists.
If you want to dive in deep, I’d recommend chapter 2.2 The Doubly-Connected Edge List from Computation Geometry - Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.

In a first implementation, I’d do it without rtree, since it’s one more thing you need to wrap your head around, even if it’s pretty straightforward to use with RhinoCommon.
It’s only needed to evaluate edges connected to other edges, while constructing the doubly-connected edge list. This can also be done, by simply comparing distances. It’s slower, yes, but the benefits of the rtree won’t manifest, unless you’re dealing with examples of more than a couple of hundred lines to start from.

Thanks a lot for the references and your help! I have made a script with the approach I mention in my first post - checking intersection between closed curves and open curve network optimized with RTree. This reflects my current knowledge. It’s not perfect and has it’s flaws. Example attached…

HatchWithColors.3dm (383.8 KB)
HatchWithColors.gh (28.4 KB)

I am keen to learn using doubly-connected edge list approach. Once I will make some progress I’ll come back here. The book reference is very useful!

This is a very old/slow/outdated/useless way to cut the mustard. Re-invents the wheel as well since the only thing that you really need is to get the ccx VV, VE connectivity from phase 1. See a demo on VV, VE (where V [vertices] is the List of ccx Pts and E [edges] the List of the Curve pieces due to crv/crv ccx events).


BTW: If you are in the broad AEC market sector and since geometry is nothing while connectivity is everything … well … I do hope that you get the gist of my message,

2 Likes

Hi @PeterFotiadis ,

interesting stuff as always.

I was trying to recreate the first step. Putting each curve segment on a branch that share an intersection vertex.

My poor attempt so far is in the attachment using the IndexOf method:
20210929_CurveBoundary_SardinesStillFarAway.gh (18.8 KB)

Maybe the dark lord could give a pointer? It seems to be about the order after splitting the curves with the tList if I am not wrong.

Well … I’ll see what I can trim from the real thing (in order to make it public).

But have in mind that moral is low: due to a collection of unspeakable actions from Red Bull (lot’s of under the table zillions to the right people etc etc) 2021 F1 championship … blah, blah. Look for instance what happened in Spa (Points for the “winner” after 2 laps behind the SC ??? hideous even by F1 corruption standards).

Moral: life sucks (and forza Lewis).

That’s nice-thanks! The first step would be great to see.
As I understand you fill up connectivity tree while splitting:

Or do you first split all curves and later seaching for which endpoint touches which intersection vertex?

I am sorry about what happened in Belgium, I hope you were’t there.

I’m not near a computer right now so I can’t recall the exact strategy used.

For the other thing the most amazing fact is how the Mighty Empire (Mercedes) caught with pants down: DAS ban, engine maps, budget ceiling, engine development freeze, “proper” aero regulations targeting high rake cars and numerous other things (including “honest” stewards) masterminded by the “right people” for the right people.

Moral: cash is King.

Now I am quite sure it is possible filling the tree up after splitting, without comparing the vertices.
Got a working version, on other curve networks it fails. But I think it might be a proof of concept and I will keep trying.

You are a man devoted to FindTheTruthOutThere_V2 (Is this a good thing? You tell me).


I hear you: what about the full UpdateConnectivity thingy? Well … can I have the next question?

BTW: A few drops of rain did the trick in Russia: Max went from zero to hero and Lewis just won his 100th GP. Since Lewis will need a 4th (or even a 5th) engine soon … you can imagine what follows. It’s reasonably to assume that even Toto he’s in Red Bull’s pay list.

Moral: life sucks.

1 Like

Thanks a lot Peter!
Reparameterizing the Curve and sorting the intersectionVertexIndices based on the t-values(array) did the trick.
Obviously your soloution is way more sophisticated and works for closed crvs etc.
That’s gonna be a next step. First I will try to implement the cycle detection from geeksforgeeks
Here my cheap attempt:

 private void RunScript(List<Curve> crvs, ref object Pts, ref object Paths, ref object Splitted)
  {
    var pts = new List<Point3d>();
    var crvsO = new List<Curve>();
    var VET = new DataTree<int>(); 

    for (int i = 0; i < crvs.Count; i++)
    {
      Curve actual = crvs[i]; actual.Domain = new Interval(0, 1);
      var paths = new HashSet<int>();
      var tList = new HashSet<double>();
      for (int j = 0; j < crvs.Count; j++)
      {
        if(i == j)continue;
        Curve next = crvs[j];
        var ie = Rhino.Geometry.Intersect.Intersection.CurveCurve(actual, next, 0.01, 0.01);

        for (int k = 0; k < ie.Count; k++)
        {
          Point3d pt = ie[k].PointA;
          pt = new Point3d(Math.Round(pt.X, 3), Math.Round(pt.Y, 3), Math.Round(pt.Z, 3));
          if(!pts.Contains(pt))pts.Add(pt);
          double t = ie[k].ParameterA;
          paths.Add(pts.IndexOf(pt));
          tList.Add(t);
        }
      }
      var splitted = actual.Split(tList);

      //Sort the paths(vertices) based on the t value-> really important!
      int[] PAL = paths.ToArray();
      double[] TAL = tList.ToArray();
      Array.Sort(TAL, PAL);

      for (int s = 0; s < splitted.Length; s++)
      {
        //if it is between two vertices put both paths on the tree
        if(s > 0 && s < splitted.Length - 1)
        {
          VET.Add(crvsO.Count, new GH_Path(PAL[s - 1]));
          VET.Add(crvsO.Count, new GH_Path(PAL[s]));
          crvsO.Add(splitted[s]);
        }
        //the first line just has one intersectionvertex
        if(s == 0)
        {
          VET.Add(crvsO.Count, new GH_Path(PAL[0]));
          crvsO.Add(splitted[s]);
        }
        //the last line just has one intersectionvertex
        if(s == splitted.Length - 1)
        {
          VET.Add(crvsO.Count, new GH_Path(PAL[s - 1]));
          crvsO.Add(splitted[s]);
        }
      }
    }
    Paths = VET;
    Pts = pts;
    Splitted = crvsO;
  }

Always go for the general case (at any cost)

Yes you can with Curve.CreateBooleanRegions

RegionColors_.gh (23.3 KB)

1 Like

Nice! Thanks ! I wasn’t aware there is a RhinoCommon method. And it is really fast!Can’t see if it was added recently.Definitely will be part of my office tools!
There is no vanilla GH-Component doing this, right?

No there is no components for this like many other tools.
I create 2 python components with other features like multi offset.

1 Like

i dont remember that quote from the book, are you sure?

Indeed there’s some dispute by historians about the 36 stratagems … but several blame the greatest strategist ever for that one.

1 Like