A better approach replicating 'Curves in Curves'

Hi all,

I’m attempting to create a sort of ‘Curve In Curve’ operation. My approach however is not particularly efficient as it relies on an Area calc and ‘Point In Curves’ method.

The Problem: I have several thousand (200K+) closed polylines some of which contain smaller polylines but not all. The goal is to assign a unique colour to all polylines however, I wish for these ‘Internal courtyards’ (inner polylines) to be assigned the same colour as its parent building outline (outer polyline).

The solution I have works but its extremely heavy with so many thousand curves to process. Can anyone advise on a more effective solution.

Much appreciated.

Curve In Curve Test.gh (17.5 KB)

1 Like

You might try using length instead of area. Also using polygon center instead of area centroid.

Thank you Michael - this is a vast improvement!

Looking into the time Profiler… as well as the ‘Point In Curves’ component, the ‘Equals’ component is adding a significant amount of time to the definition, any ideas on replacing this? - I’m simply searching for all points inside the polygon and using the ‘equals’ component to generate a cull pattern.

Thanks again.

Generally speaking, AreaCentroid as well as polygonCenter may be outside of polygon in cases when polygon is not convex:

So, questions are:

  1. Are all of your polygons convex
  2. Are all of your polygons always rectangular
  3. Do they intersect and if so how do you want them to be treated in that case (I guess you do not consider it as “one is inside another”)
    Generally you do n * n comparison, so your algorithm is not going to be fast for large num of objects. There are ways to improve it but it also depends on your answers / definition of problem.

Thanks RadovanG for the comments.

To answer them, not all polygons are convex however an important point is that all “internal” polygons are contained entirely within the outer polygon and do not overlap it’s boundary.

The outer polygon center / centroid is also not too critical as the condition requires the internal polygons to be inside the outer curve and the total length of the outer curve to be greater than any of it’s internal polygons (Which it always is).

The ‘point in curves’ component appears to be a reliable solution… its just a bit slow currently.

This is not true in general, so if you want solution that works for any set of polygons for which you know that they do not intersect than you can not assume that

  1. outside polygon has larger length than inside one

  2. AreaCentroid as well as polygonCenter is inside of polygon

These two conditions are not always true:
Lengths_rg1.gh (8.8 KB)

Probably the most accurate way to test for curve-curve inclusion is to use the built-in Curve.PlanarClosedCurveRelationship()- I don’t think there’s a native Grasshopper component that exposes this function but it’s easy enough to call inside a scripting component.
http://developer.rhino3d.com/api/RhinoCommon/html/M_Rhino_Geometry_Curve_PlanarClosedCurveRelationship.htm

This takes care of all edge cases mentioned above, but will be even slower than point-in-curve testing.

Using the built in RTree structure will reduce the number of checks you have to perform from O(n^2) to roughly O(n), meaning it will scale to thousands of curves much better.
http://developer.rhino3d.com/api/RhinoCommon/html/T_Rhino_Geometry_RTree.htm

But speaking of edge cases: how would you want these curves to be grouped?
image

1 Like

Indeed that Method iis the best way to do that IF your regions are closed (or closable within tolerance) AND coplanar (within tolerance). Shown the R5 SDK ref:

Other than that is a classic Clustering task using the Region Containment as criterium (kinda like ccx events are used for Clustering intersecting curves or Pt to Pt Distance for Clustering points or … etc etc).

That said Clustering can contain more than one criterium meaning endless combos (for intstance you can Cluster crvs that intersect only 2 times and their length is greater than X and they are open and …).

Notify if you want a C# that does that (it’s rather fast as well).

…I see what you mean.

I don’t think I’ve explained what I’m trying to achieve particularly well. I’m basically ordering a very dense urban figure ground. Because I know the majority of the mass is built space I’m also confident that the inner ‘un-built’ spaces will have a smaller curve length.

So… when I said its not too critical I probably should have said its not too critical in this particular scenario. However, I agree that a comparison between outside and inside curve length may throw up issues in other applications.

Thanks Qythium,

This sounds a very promising solution but I have to fess up, I’m only familiar with GH components and have no experience with Rhino Common, is the code complex to write / edit?

The principle is hopefully straight forward… lets say thousands of polygons are randomly assigned different attributes, layer name, colour etc etc… My goal is make sure that all the inner polygons are assigned the same attributes as its parent ‘outer’ polygon. That’s it. They don’t need to be grouped in any other way apart from having the same attributes. So essentially its a (re)ordering exercise.

@qythium and @PeterFotiadis I would be really interested to know if a script component could help here as the GH component route is proving extremely slow for the number of curves i’m currently testing.

So you know, all curves are closed, coplanar and the inner polygons do not intersect with the external polygon.

Curve In Curve Test 2.gh (108.2 KB)

DO NOT attempt to do Clustering without knowledge of coding.

Other than that … the only thing worth considering here is to implement some proper // approach (big N of closed curves etc). It doesn’t matter if there’s some improper data around (they will be rejected).

I’ll prepare a small demo on that matter soon. And given the opportunity maybe I’ll provide some other cases (ccx, distance etc) that outline the whole hard Clustering concept (very common in engineering, mind).

PS: Hard means that any item belongs in exact one Cluster.

Here we are. A classic hard Clustering based in one condition (Region Containment). No proper Curve checks are included mind (meaning that the thing is 100% Academic):

Clusters_CurveContainment_V1.gh (225.8 KB)

The def is WIP since this is another typical case that begs for some // stuff. (try the 857 curves demo: Elapsed time goes to Mars). But what could be the best // approach? Answers: the Lord, District 9, North Pole.

More soon with 3 ways to skin the cat: // for no reason, // with reason, // because hope dies last .

1 Like

Assuming the curve/polyline data isn’t too messy, a simpler approach might be to make boundary surfaces (which essentially handles the grouping for you):

180419_BoundarySurfaces.gh (14.4 KB)

This probably won’t scale too well (i.e. will be slow), but should be fairly predictable/stable.

3 Likes

WHAT AN IDIOT: maybe some espresso (and/or cigar) related thingy, maybe just stupidity

Get the fixed V1 (the // V1A soon).

Clusters_CurveContainment_V1_Fixed.gh (236.6 KB)

Hmm, the boundary surface method does actually seem to scale surprisingly well/fast, at least with this circles data set (as compared to the region containment method I mean, and with this case):


180419_BoundarySurfaces_PerformanceTest_00.gh (242.1 KB)

1 Like

Indeed. But some // methods (WIP) give some signs of hope (time slashed by a factor of 10 [min] - 20 [max] for the moment).

My approach will be to create early exit condition before starting comparing curves for containment condition - see image:

If we consider special case C. then algorithm will be valid for any curve, not only polylines.

Question is if curves are polylines or they can be any arbitrary closed curve?

WIP - to be continued…

1 Like

Indeed that could broaden the usage of the thing (but this check is also expensive).

In the mean time V2 works 100% faster (prior implementing the 3 // Methods mentioned - no time found for that).

BTW cList is of type Curve (not Polyline) but dealing with curvy stuff is obviously slower. For instance and for rather the same N of curves the non curvy collection yields ~3 times faster results (1600 VS 5600 ms).

Clusters_CurveContainment_V2.gh (231.8 KB)

1 Like

Main bottleneck here is NxN checking (number of checks O(n2)).
Using RTree will speed up thing rapidly especially in case of large amount of curves.
Here is update method:
public void MakeClusters(List < Curve > cList, ref DataTree < Curve > curveClusters, ref DataTree < int > connClusters, int singleItemCluster)
{
Plane plane = Plane.WorldXY;

bool[] sampled = new bool[cList.Count];
int branch = 0;
double tol = RhinoDoc.ActiveDoc.ModelAbsoluteTolerance;

//RTree improvment - start
var boundingBoxes = cList.Select((objR, index) => new { index, objR }).ToDictionary(x => x.index, y => y.objR.GetBoundingBox(true));
RTree tree = new RTree();
for (int i = 0; i < boundingBoxes.Count; i++)
{
  tree.Insert(boundingBoxes[i], i);
}
DataTree<Curve> curveClustersLocal = new DataTree<Curve>();
DataTree<int> connClustersLocal = new DataTree<int>();

for (int i = 0; i < cList.Count; i++)
{
  if (sampled[i]) continue;
  Curve crvA = cList[i];
  var bboxA = boundingBoxes[i];
  tree.Search(bboxA, (to, ta) =>
    {
    int j = ta.Id;
    if (i != ta.Id && !sampled[j])
    {
      Curve crvB = cList[j];
      RegionContainment rg = Curve.PlanarClosedCurveRelationship(crvA, crvB, plane, tol);
      if (rg == RegionContainment.BInsideA)
      {
        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);
      }
    }
    });
  branch++;
}
curveClusters = curveClustersLocal;
connClusters = connClustersLocal;
//RTree improvment - end

RebuildTree<Curve>(ref curveClusters);
RebuildTree<int>(ref connClusters);

if(singleItemCluster == 2){
  int bCount = curveClusters.BranchCount;
  for(int i = 0; i < sampled.Length;i++){
    bool bs = sampled[i];
    if(!bs) {
      curveClusters.Add(cList[i], new GH_Path(bCount));
      connClusters.Add(i, new GH_Path(bCount));
      bCount++;
    }
  }
}

}

If shapes are polylines only, code can be rewritten and it would perform significantly faster.

Good stuff I confess. Bravo.

Clusters_CurveContainment_V2A.gh (342.4 KB)