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) point-in-curve 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:
- Pre-compute bounding boxes and use Point-Rectangle intersection as a cheap pre-test
- “Point In Curve” may already do this
- Split curves (or bounding boxes) into a quad tree, B-tree, 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^{n-1}
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 divide-and-conquer.
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!
