[RhinoCommon] RTree is too limited

Continuing the discussion from PointCloud Analysis:

@stevebaer In the C++ ON_RTree it is possible to navigate the RTree on different levels using, ON_RTreeBranch, m_branch[], m_child, m_id, IsLeaf() etc. It would be very, very useful to have the same functionality in RhinoCommon.

I’m writing an spatial tree class at the moment and I’d like to know what this would be useful for. I’ve actually completely abstracted the tree logic, making the tree behave as a regular List, but with some very fast search methods on it. It sounds like you want access to the hardcore stuff, but I can’t think of a scenario where you’d need this.

I have had to resort to C++ to implement the MeshMesh closest point algorithm we discussed a couple of weeks ago. Now today, it popped up in the context of another topic ( PointCloud Analysis ) where I think the search would be much faster when using RTree and having access to the bounding box of each level in the tree. If that bounding box is inside the search Brep, the lower levels do not have to be tested.

How would your implementation of the spatial tree class handle the problem in the linked topic?

You’re right, it wouldn’t. I’ve added methods to my tree class for finding all loci inside BoundingBox, inside oriented Box, inside Sphere and above Plane, but no other shapes. I’ve also got methods for finding the N closest/furthest points from a search start point with optional min and max radii.

If I were to expose a more interactive search method, I’d probably do it by allowing you to supply a delegate which puts the responsibility of rejecting/accepting nodes squarely into your hands. I’d probably only give you readonly access to some of the properties of each node (boundingbox, pointcount, childnodecount), but that should be enough for making custom searches like the one you mentioned.

Let me make up some bogus code to elaborate.

Tree<Point3d> tree = new Tree<Point3d>(mesh.VertexCount);
int[] idxs = tree.FindPoints(ValidateNode, ValidatePoint);

bool ValidatePoint(Point3d point)
  return _brep.Contains(point);
SearchInstruction ValidateNode(BoundingBox nodeBox)
  if (IsCompletelyInside(_brep, nodeBox)
    return SearchInstruction.Include;
  if (IsCompletelyOutside(_brep, nodeBox)
    return SearchInstruction.Reject;
  return SearchInstruction.Recurse;

That should cover it, yes.

Do you think the Tree.FindPointsInside method would also be usable for searching two trees together, such that you can compare two nodes, each from one tree, and decide to keep searching depending on how the two nodes relate to each other? (this is the basis of the mesh-mesh closest point algorithm).

That sounds a lot more complicated, but possible in principle I’m sure. I did briefly try to write a closest point search between two Tree instances, but decided it was too difficult and could always be added later.