logo

[G]allopingTopiary

Projects details

created at Mode Lab Experiments

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 

Simple Example Part 1Bounding Regions should contain approximately the same number of nodes

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

Simple Example Part 3Using 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

Simple Example Part 4Once 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
import Rhino
import rhinoscriptsyntax as rs
import scriptcontext
from System.Drawing import Color
import random as rnd
import time
"""--------------------------------------------------------
PERFORMANCE TEST - RTREE CLASS RHINOCOMMON
Repeated Search To Find Closest Neighbor
Search Sample = 1 Million Points
Search Radius = 500 Units
Search Space = Cube (5000,5000,5000)
--------------------------------------------------------"""
class SearchData:
    def __init__(self, pts, point):
        #Search Data class set up for instancing repeaded searching and tracking
        self.HitCount = 0 #amount of times we searched starts with 0
        self.arrPts = pts
        self.Point = point
        self.Index = -1 #insuring that we reduce the search radius after the first pass, see the conditional in searchcallback
        self.Distance = 0
        self.count = 0
def SearchCallback(sender, e):
    data = e.Tag
    data.HitCount += 1 #incrementing the hitcount
    vertex = data.arrPts[e.Id] #the current closest neighbor
    distance = data.Point.DistanceTo(vertex) #distance to the current closest neighbor from the query loc to define new search radius
    if data.Index == -1 or data.Distance > distance: #condition to resize the search sphere to optimize the searching
        e.SearchSphere = Rhino.Geometry.Sphere(data.Point, distance) #resize the search sphere
        data.Index = e.Id #update the data.index to current point ID
        data.Distance = distance #update the data.distance to the current distance
def RunSearch():
    pttimeStart = time.time() #Start Timer
    point = Rhino.Geometry.Point3d(5000/2,5000/2,5000/2)
    intNumPts = 1000000 #specify the number of sample points to search 
    pts = []
    tree = Rhino.Geometry.RTree() #create a new instance of the rtree class
    for x in range(0,intNumPts):
        randomPt = Rhino.Geometry.Point3d(rnd.random()*50000,rnd.random()*50000,rnd.random()*50000) #randomly place each point inside the 5k x 5k x 5k cube
        pts.append(randomPt) #add the current point to the end of the pts list
        tree.Insert(randomPt,x) #insert the current random point in the RTree at the specified index (x)
    pttimeEnd = time.time() #end the timer
    print "time taken to create pts: {}".format(pttimeEnd - pttimeStart) #print amount of time it took for calculations
    print "TreeCount = {}".format(tree.Count) #count of the amount of items in the tree
    timeStart = time.time() #Start Timer
    data = SearchData(pts, point) #Create an instance of the Search Data Class passing sample list, query loc
    sphere = Rhino.Geometry.Sphere(point, 500) #specify the inital search sphere size
    if tree.Search(sphere, SearchCallback, data): #call the search method from the Rtree Class 
        print "Found point in {0} tests".format(data.HitCount) #print the amount of search iterations we did
        print "ClosestPt = {}".format(data.arrPts[data.Index]) #print the closest neighbor
    timeEnd = time.time() #end the timer
    print "time taken: {}".format(timeEnd - timeStart) #print amount of time it took for calculations
if __name__=="__main__":
    RunSearch()
Update
import Rhino
import rhinoscriptsyntax as rs
import scriptcontext
from System.Drawing import Color
import random as rnd
import time
"""--------------------------------------------------------
RHINOCOMMON METHODS
One Time Search to find all points within specified radius
The points found inside the specified radius get sampled for closest neighbor
No Repeat Search
Search Sample = 1 Million Points
Search Radius = 500 Units
Search Space = Cube (5000,5000,5000)
--------------------------------------------------------"""
def closestSearch(pts, point):
    #function to sample point based on a search radius first then search for the closest inside that list mimic the rtree pass basically but with brute force
    ptsinRange = [] #dynamic list to store points found inside initial search
    for i, pt in enumerate(pts):
        dist = point.DistanceTo(pt) #find the distance from each point to the query point
        if dist < 500: 
            ptsinRange.append(pt) #if the distance is less than 500 append that point to the ptsinRange List
    cPoint = Rhino.Collections.Point3dList.ClosestPointInList(ptsinRange,point) #search for the closest point from that list of points in range
    if cPoint[0] == point[0] and cPoint[1] == point[1] and cPoint[2] == point[1]: #test against the closest neighbor being you
        print "IS THE SAME" 
    return cPoint,ptsinRange #return the closest neighbor and the list of points in range
def RunSearch():
    point = Rhino.Geometry.Point3d(5000/2,5000/2,5000/2)
    intNumPts = 1000000 #specify number of sample points
    pts = [] #store the random points in an empty list
    for x in range(0,intNumPts):
        randomPt = Rhino.Geometry.Point3d(rnd.random()*5000,rnd.random()*5000,rnd.random()*5000) #randomly place each point inside the 5k x 5k x 5k cube
        pts.append(randomPt) #append each random point to the pts list
    timeStart = time.time() #Start timer
    data = closestSearch(pts, point) #call closestsearch function Pass query pt and list of points to search
    print "ClosestPoint = {}".format(data[0]) #print the closest neighbor
    print "Number of Pts in Range = {}".format(len(data[1])) #print how many points were captures inside the search radius
    timeEnd = time.time() #stop the timer
    print "time taken: {}".format(timeEnd - timeStart) #print the amount of time the calculations took
if __name__=="__main__":
    RunSearch()
Update
import Rhino
import rhinoscriptsyntax as rs
import scriptcontext
from System.Drawing import Color
import random as rnd
import time
"""--------------------------------------------------------
RHINOSCRIPT METHODS USING PYTHON
One Time Search to find all points within specified radius
The points found inside the specified radius get sampled for closest neighbor
No Repeat Search
Search Sample = 1 Million Points
Search Radius = 500 Units
Search Space = Cube (5000,5000,5000)
--------------------------------------------------------"""
def closestSearch(pts, point):
    #function to sample point based on a search radius first then search for the closest inside that list mimic the rtree pass basically but with brute force
    ptsinRange = []#dynamic list to store points found inside initial search
    for i in range(len(pts)):
        dist = rs.Distance(pts[i],point)#find the distance from each point to the query point
        if dist < 500:
            ptsinRange.append(pts[i])#if the distance is less than 500 append that point to the ptsinRange List
    cPointIndex = rs.PointArrayClosestPoint(ptsinRange,point)#search for the closest index from that list of points in range
    cPoint = ptsinRange[cPointIndex] #find the closest point in the in range list from the index found above
    if cPoint[0] == point[0] and cPoint[1] == point[1] and cPoint[2] == point[1]:#test against the closest neighbor being you
        print "IS THE SAME"
    return cPoint,ptsinRange #return the closest neighbor and the list of points in range
def main():
    point = [5000/2,5000/2,5000/2]
    intNumPts = 1000000#specify number of sample points
    pts = []#store the random points in an empty list
    for x in range(0,intNumPts):
        randomPt = [rnd.random()*5000,rnd.random()*5000,rnd.random()*5000] #randomly place each point inside the 5k x 5k x 5k cube
        pts.append(randomPt)#append each random point to the pts list
    timeStart = time.time()#Start timer
    data = closestSearch(pts, point)#call closestsearch function Pass query pt and list of points to search
    print "ClosestPoint = {}".format(data[0])#print the closest neighbor
    print "Number of Pts in Range = {}".format(len(data[1]))#print how many points were captures inside the search radius
    timeEnd = time.time()#stop the timer
    print "time taken: {}".format(timeEnd - timeStart)#print the amount of time the calculations took
main()
Update

 

  • Share

Leave a reply

Your email address will not be published. Required fields are marked *