[G]allopingTopiary

Gallery details

R-trees are balanced tree data structures used for spatial access methods in N-dimensional space. Implementing the RTree Class will allows us to reduce the search space by incorporating a searching sphere or bbox . R-tree is also a balanced search tree (so all leaf nodes are at the same height), organizes the data in pages, and is designed for storage on disk.

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle (MBR) in the next higher level of the tree. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation of an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set. – Wikipedia

RTree Simple Example | 50 Point Sample Size | 1 Point Query | Drawing a line to closest Neighbor, base diagrams below from Julius Davis – Implementing the Pseudo Priority RTree

Bounding Regions should contain approximately the same number of nodes

First the search find the closest bounding box, followed by the closest point inside that box. Distance to that point determines the next search radius

Using the Search Call Back function we repeatedly search until no new Best candidate is found. In this case the closest box did not contain a point inside the search radius therefore it is pruned and the search is repeated

Once the search is repeated we see there are no more best candidates to chose from therefore the red point is our closest neighbor

Performance Tests

Calculation Time Comparison Between Code Versions in Seconds. Search Space Sampling 1 Million Points from 1 Point to find X nearest in a 500 unit radius then closest within that range. Searches 1 Million Points in a (5000,5000,5000) Unit Cube

RTREE Rhinocommon

Tree Item Count = 1,000,000
Found closest n point in 9 tests
CALCULATION TIME TAKEN : 0.002 sec
Search sphere size of 500

Rhinocommon Python

Point Count = 1,000,000
ClosestPoint = [2092.39 , 2955.144 , 2235.82]
Number of Points in Range = 4151
CALCULATION TIME TAKEN : 0.512 sec
Search sphere size of 500

Rhinoscript Python

Point Count = 1,000,000
ClosestPoint = [2192.45 , 2958.38 , 2230.98]
Number of Points in Range = 4236
CALCULATION TIME TAKEN : 3.95 sec

Calculation Time Comparison Between Code Versions in Seconds. Single Search, non recursive. Sphere (r=500) Searches 1 Million Points in a (5000,5000,5000) Unit Cube

RTREE Rhinocommon

Tree Item Count = 1,000,000
Number of Points in Range = 1
CALCULATION TIME TAKEN : 0.00099 sec

Rhinocommon Python

Point Count = 1,000,000
Number of Points in Range = 1
CALCULATION TIME TAKEN : 0.015 sec

Rhinoscript Python

Point Count = 1,000,000
Number of Points in Range = 1
CALCULATION TIME TAKEN : 2.72 sec

Calculation Time Comparison Between Code Versions in Seconds Agent Interactions while Mesh Sampling – Seeking for closest values within 4 units of their current position.

RTREE Rhinocommon

Mesh Vertex Count = 393,216
Number of Agents = 50
Iteration Steps = 200
CALCULATION TIME TAKEN : 9.7 sec
Search Radius = 4

Rhinocommon Python

Mesh Vertex Count = 393,216
Number of Agents = 50
Iteration Steps = 200
CALCULATION TIME TAKEN : 1390 sec
Search Radius = 4

Rhinoscript Python

Mesh Vertex Count = 393,216
Number of Agents = 50
Iteration Steps = 200
CALCULATION TIME TAKEN : N/A Either Crashes or gave up because time was insanely long
Search Radius = 4

Why the drastic difference in performance?

Searching an arraylist based on distance requires a search to all elements within the Array, while using a Data Tree Search Space Algorithm will reduce the search space to a specified range (search sphere size or bounding box size) The search uses a distance (radius) to prune the search tree, meaning any elements that lie outside of the search radius will be omitted from the search therefore dramatically reducing the calculation time.

Code

RTree_NeighborSearch_RhinocommonBruteForce_NeighborSearch_RhinocommonBruteForce_NeighborSearch_RhinoscriptPY

[snippet slug=topiary_rtree_rc lang=python]

[snippet slug=topiary_bruteforce_rc lang=python]

[snippet slug=topiary_bruteforce_ip lang=python]