Rtree methods for diagonal paths

Scripting
, , , ,
1

I’ve been working on a pathfinder algorithm that finds the shortest path between 2 points through a given point cloud.

For the most part it is working as intended but I noticed a weird behaviour that I’m trying to fix. The rtree search method seems to be significantly slower if the path is not aligned with the world axes. In one test that I ran, it took 3s to find a straight vertical path, but when I rotated the geometry (the path length and the point cloud remained the same) it took 50s.

I’m currently using this method: RTree.Search method (rhino3d.com)

Is this an expected behaviour? And if it is, how can I make it more efficient for diagonal paths? Would another method like PointCloudClosestPoints perform better in this case?

Any help is appreciated

2

Hi Robneto,

I’m a hobby programmer, but I’ve spent some time investigating how graphs and trees work, so take this all with a grain of salt.

How I understand it, an R-tree is a hierarchical, three-dimensional data structure in Rhino. The inserted points are partitioned into bounding boxes, which are usually axis aligned.
Now, when doing a nearest neighbour search, the R-tree is traversed down, starting from it’s root node. The bounding boxes of each node are checked and those closer to the current node point are prioritized. I would imagine that world axes-aligned points thus simply are contained within fewer bounding boxes, and there’s simply less to check (fewer node travels), consequently making the computation faster.
Diagonal points should be spread throughout more bounding boxes, which means more travel down the tree to find a close neighbour.

1 Like
3

Thank you for your input Diff-arch.

I’m also not an expert in R-Trees, and only have a superficial knowledge of how they work, but my assumption matches what you said, it’s the exponential increase in the number of searched points in the point cloud due to a large number of bounding boxes being used for inclined paths.

However, when we explore the R-Tree class, there are quite a different number of methods that can be used to find neighbouring points. So I was wondering if one is better than others for incline paths.

For instance, the Point3dKNeighbors sounds like a type of method that you would find in K-Trees, which tend to be more efficient in finding diagonal paths (I think).

Again, I’m really not an expert in any of this so any input is appreciated.

4

I don’t think so. If it’s a class method of the RTree than, it probably also uses its same principals for nearest neighbour searches. I guess the method just searches for the k-nearest points, where k is the number of points to look for.

As for K-D trees - here K stands for the dimension (e.g. 2D, 3D, etc) since they can be multidimensional -, they split along axes, which again entails that diagonal searches mean traversing more branches and thus more checks.

For diagonal searches my guess is that an octree or ball tree would probably be best, but I’m not 100% sure.

5

I see. And I guess I would have to create that class from scratch since I don’t see it in rhino common documentation.

It might be easier to accept that some paths will take much longer than others.

6

Hi Robneto,

just another pluging developer, but i’ve used Rtree quite extensively. In my experiance its very senstive to how you handle the callback - particularly how you update the search sphere / box to reduce the search space. I’ve a collection of half a dozen approaches depending on use-case.

50seconds for an RTree search does seem extremely long, for comparison I’d expect to get a few hundred thousand searchs on 10,000 bounding boxes in 10 seconds.

Have you looked at any of the other Rtree search methods available?

One approach to solving your original problem would be to:

  1. Plot a straight line from A → B
  2. Sample along it every Xmm to get a set “way points”.
  3. Use RTree.PointCloudClosestPoints method (rhino3d.com) with needle points as the “way points” to get the nearest points to the optimal path
  4. Advantage of this is you only need to do 1 search of the RTree
  5. Order these points based on distance from A (or B)
  6. for each successive triple of points X,Y,Z in the ordered list figure out whether its more efficient to jump from X,Z then to go via Y.
  7. You probably need to run #6 through the list until there are no changes.
  8. Obviously #6/#7 is an heuristic but it ought to be quick and maybe “quick enough”

Just an idea, was a fun problem to think about :slight_smile:

7

Thanks for the tips David.

Just to clarify, 50s was the time it took me to find an incline straight path through a cube of point cloud, not the time it took to do one search. Idk how many searches it did during that time but I would estimate it’s in the order of 5 digits.

This was just a test case, my real application is way more complex and I don’t think sampling the points based on a straight line between A-B would work for me unfortunately.

I will give it a go with the PointCloudClosestPoints method and see if that’s faster.