A better approach replicating 'Curves in Curves'

Okay it looks like your C# is ~2x faster :sweat_smile: ( as expected )
I wonder if there’s a performance difference between using RTree.Search versus RTree.SearchOverlaps due to overhead from all the callbacks…

Math.Pow(hmm,hmm) … that’s for the P thingy (what about the Truth Out There ?, he he)

This thread started as any other thread and heads towards other things I confess.

Must clear my mind from doing Panigale custom maps (a useless thing considering the ponies available as standard) and fucus to the Truth Out There (a WIP thread exploiting the truth out there).

Screen%20Shot%20104

2 Likes

Great example there, bookmarked :clap:

Another improvement in special case when we know that curves do not intersect will be to check if curveB.PointAtStart is inside curveA.
Code inside tree.Search would look like:

  tree.Search(bboxA, (to, ta) =>
    {
    int j = ta.Id;
    if (i != ta.Id && !sampled[j])
    {
      Curve crvB = cList[j];
      Point3d ptStart = crvB.PointAtStart;
      var pointContainment = crvA.Contains(ptStart);
      if (pointContainment == PointContainment.Inside)
      {
        if (!sampled[i]) UpdateTrees(crvA, ref curveClustersLocal, ref connClustersLocal, ref sampled, i, branch, true);
        if (!sampled[j]) UpdateTrees(crvB, ref curveClustersLocal, ref connClustersLocal, ref sampled, j, branch, true);
      }
    }
    });

This will shorten time of execution almost to half.

It’s a question of trust the data (as always). But other than that I see that you are a man who walks the walk (as Gythium … if we forget that little detail, he he) > bravo again.

Clusters_CurveContainment_V2B.gh (341.3 KB)

BTW: It’s funny that even a primitive data validation check increases the Elapsed time about 10-15%

You know what? In fact we don’t need a RTree at all. Just BBoxes and some canditate BBox questions (but that is what a RTree does anyway [pluts the fact that does N*N comparisons]). Rounding the BBox domains (user controlled option: say in 2 decimals etc helps as well).

See : Mesh Inclusion Error and the useBox magic option. Not 100% the same thing but close. In fact I was ready to use a trick like this … but then you did the RTree thingy and the rest are history.

More in V3 (and some // stuff) … provited that Valentino could deliver some decent results in the Texas MotoGP (for inspiration) . V4 in the mean time would answer the following critical question: given 1M plates full with Swiss cheese and 1Z rats circling around how we can cluster the clouds in the sky on a per rat color basis?

Screen%20Shot%20110

This entire thread:

2 Likes

I tried some boxMagic things and with help of mice sudenly I got some code that is permormig well.
Litle bit of some sortings, up-sortings, right-sorting… re-sortings and rememberings what I was just sorting … with assumption that curveA contains curveB only and only if bboxA contains bboxA what should be still valid in this universe. Or maybe not?

Clusters_CurveContainment_v42.gh (5.7 MB)

1 Like

Indeed the magic this (and magic that) can cut the mustard rather well.

Me? Well … Valentino finished a miserable 4th in Texas (IM miles behind that man, even Iannone got a podium place) meaning that I have absolutely no will for C,D,E … Z# : In fact if I was a real man I should commit seppuku ASAP.

Hi, I was wondering what would be the test condition for the case when the edge of an Inner-Curve overlaps with the edge of the Outer-Curve. Something like this:

In this case the result should give: A{1,3}, B{0,3,4}, C{0,2}.

Interesting, especially A which seems to be a typical Minkowski Sum problem in which A can be numerically solved in almost no time (collision detection).

A simplified algorithm for the initial collision test is presented by Casey Muratori in the following talk (link below) where he addresses three topics, implicit surfaces, quaternions and finally, Minkowski Sums (collisions test) giving “hands on” examples for implementation strategies for the latter. Link directly to the Minkowski part:

Youtube link:

// Rolf

Just saw this post, and I’ve seen it has evolved into an adult discussion about intersections and coding, so take this as a parenthesis:

IF it is a given that the curves don’t intersect, and IF you are not using coding, a -relatively- fast method is to check the inclusion of just a point on the curves.
In my system it took 3 secs to calculate for 1300 rectangles.
curveInCurve.gh (83.6 KB)

1 Like

Nice solution for world-aligned rectangles.

// Rolf

If we’re going for pure performance… Here’s a shot using Impala to speed parts of it up. First finding the neighborhood of all nearby curves (curves with a centrepoint within the ‘radius’ of the largest point in the set) and then doing containment testing. All of this is parallel and comes out to just over a hundred milliseconds all told… it’s the boundary surfacing to preview at the end that takes the time :slight_smile:


curveInCurve_2.gh (100.3 KB)

4 Likes

milliseconds? amazing! downloaded your code to analyze it immediately!
(also: I didn’t know about impala, is it that effective?)

Proper code will do it faster. On 4cores/8threads PC attached algorithm will do it in 6 milliseconds, the rest of time is spend for data reading/casting…
curveInCurve_Compare42.gh (86.6 KB)

3 Likes

Hi

I am actually looking to find the biggest rectangle I can fit in an organic closed curve. I was wondering if you have any solution for this.

thank you

See this discussion under grasshopper:

" Find the largest possible rectangle inside an irregular closed curve"

I have a real-time C# that does that (in 2d/3d) but the practice is closed for the moment. In the mean time see the thread in the link above.

PS the approach is recursive and is “based” on Matrix classic problems like this:


OMG! this is amazing!