Suppose we’d like to work with the containment relation of a set K of 2d curves with the following properties:
A. All curves are closed
B. All curves are mutually disjoint
This means we’d like to:
 Verify that K has property A and B (so we can throw an error if it doesn’t)
 Create a data structure that lets us take curves p and q in K and answer:
i) Does p contain q?
ii) Is p the parent of q? (p contains q, and no other curve in p contains q)
iii) Is p a top level curve? (p has no parent)
Example 1
Suppose K looks like the diagram on the left. We can answer these questions using its containment graph:
 p contains q if there is a path up from p to q
 p is the parent of q if this path is length 1
 p is a top level if it is a root node
Example 2 (Use case)
Here we have a complicated design that’ll be CNC manufactured. It has multiple panels with interior details, all represented by closed, mutually disjoint curves:
Before manufacturing, we’d like to nest them with @Petras_Vestartas’s OpenNest:
In order to properly align the results, we must group each internal detail with the top level curve that contains it. We can save a lot of time here if we can automatically answer questions 2.iii) and 2.i.
Solutions So far:
1.A)
Property A fails if the output of the “Closed” operation has any false
values:
1.B)
Property B fails if the “Multiple Curves” operation finds any intersections:
2.i)
We can use “Point In Curve” to create a containment matrix; call it M.
M has a 1 at column i, row j exactly when curve j contains curve i, and zeros elsewhere:
This algorithm requires O(n^2) pointincurve tests. For example 2, this is 462^2 = 213444 tests. Not great! Another limitation: M does not represent the containment graph as drawn in example 1, but rather its transitive closure. This means it lets us answer 2.i and 2.iii fairly easily, but it has a lot of redundant data that makes 2.ii harder to answer.
Ideas for accelerating this step include:
 Precompute bounding boxes and use PointRectangle intersection as a cheap pretest
 “Point In Curve” may already do this
 Split curves (or bounding boxes) into a quad tree, Btree, or grid
 This can probably give us O(n log(n)) time
 Not clear how to do this in a very “Grasshopperish” way
2.ii)
Suppose that K has n curves and let
N' = M  M^2  M^3  \dots  M^{n1}
N_{ij} = Max(0, N'_{ij})
Then N_ij = 1 exactly when curve j is the parent of curve i, and is zero otherwise. This works because M^k_{ij} counts the paths of length k between nodes i and j in the graph represented by M.
In Grasshopper, we can implement this matrix wrangling with some custom python code.
This algorithm requires around O(n^4) multiplications. Here, example 2 make grasshopper crash under an avalanche of approximately 45,558,341,136 multiplications.
Luckily, M is sparse, and this algorithm can be simplified:
 Use an adjacency list instead of an adjacency matrix
 Perform topological sort instead of matrix multiplication
This should have running time O(n + m), where m is the number of 1s in M.
2.iii)
This is conceptually easy: curve i is top level if and only if row i of M is all zero. Computing this efficiently goes back to bounding boxes and divideandconquer.
Questions:

Is there any grasshopper component that already does some or all of this stuff more efficiently than my prototype?

Is there any “grasshopperish” way to implement divide and conquer algorithms like quad trees?

What are some other ways to accelerate these algorithms?
Thanks!