Homepage of Stefan Salewski
Ruby bindings for R-tree of BOOST library
The R-tree data structure (www.boost.org) is useful for fast spatial search. For two dimensions we may have a large set of rectangles and want to find all of them which intersects with a query rectangle. One application is computer graphics, you move one object and have to find and redraw the uncovered other objects -- each one was assigned a rectangular bounding box. My current (planned) task is finding free regions of Printed Circuits Boards where placement of vias is possible.
Currently my Ruby bindings support only two dimensional space and rectangular objects, I think this is the most used area. Query is limited to intersection and nearest neighbour search. Boost library supports higher dimensions by using templates -- for Ruby that needs some modifications of the glue code for each dimension. (A more generic solution may be offered by libspatialindex -- I have not found time to investigate that one, it looks more complicated.)
Please note: These bindings are nearly untested yet, and some method names may be preliminary. After some testing I may write a version for storing points in 2d, and maybe one version for 3d. And I may add other types of query, i.e. for fully covered objects...
Installation (for Linux) cd RBOOST/RTREE ruby extconf.rb make
You need installed Boost library >= 1.54 -- and of course C++ compiler and Ruby 1.93 or 2.0.
# test.rb -- basic test script with string objects
require_relative 'rboost_rtree_2d_rect'
rt = BOOST::R_tree_2d_rect.new
puts (rt.methods - Object.methods).sort
=begin
[]
[]=
delete
each_object
each_pair
insert
intersects?
intersects_each?
intersects_rect?
intersects_rect_each?
nearest
nearest_each
nearest_rect
nearest_rect_each
rect
remove
to_a
update_or_insert
=end
rt.insert('r2277', 2, 2, 7, 7)
p rt.rect('r2277') # query coordinates
rt.insert('r3589', 3, 5, 8, 9)
rt.insert('r1234', 1, 2, 3, 4)
rt.insert('r3456', 1, 1, 9, 9) # wrong
rt.update_or_insert('r3456', 2, 2, 8, 8) # still wrong
rt['r3456'] = [3, 4, 5, 6] # correct
p rt['r3589'] # [3, 5, 8, 9]
puts rt.intersects?(0.9, 0.9, 2.1, 2.1) # should be r2277 and r1234
puts rt.nearest(10, 10, 2) # should be r3589 and r2277
rt.remove('r3589')
puts rt.nearest(10, 10, 2) # now should be r3456 and r2277
puts rt.nearest_rect(10, 10, 2) # returns array -- object and minx, miny, maxx, maxy
rt.nearest_rect_each(10, 10, 2){|r| print r[0], ' has area ', (r[3] - r[1]) * (r[4] - r[2]), "\n"}
rt.each_pair{|el| puts el}
rt.delete('r2277')
rt.each_pair{|el| puts el}
a = rt.to_a
a.each{|el| p el}