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.
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.
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.
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
outside polygon has larger length than inside one
AreaCentroid as well as polygonCenter is inside of polygon
These two conditions are not always true: Lengths_rg1.gh (8.8 KB)
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 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.
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.
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):
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 .
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):
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):
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).
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.
