Class: RTree
- Inherits:
-
RTreeBase
- Object
- RTreeBase
- RTree
- Defined in:
- lib/rtree.rb
Overview
A Ruby wrapper around librtree implementing the R-tree spatial index of Guttman-Green.
Use
require 'rtree'
to make the RTree class available.
Given a set or rectangles (or higher dimensional cuboids) and their associated ids, one can build an RTree using the RTree.csv_read class method or repeated calls to the #add_rect instance method. The former is more performant since it avoids routing the rectangles through the Ruby-C interface.
Once the RTree instance is created one can make spatial queries against it with the #search method; one passes a rectangle to the method and it returns the ids of all of the input rectangles which intersect it (or yields them one at a time to a block, if given).
It may be convenient to serialise the RTree for faster loading, the library implements a custom binary format, BSRT (binary serialised R-tree) which can be written by #bsrt_write and read with RTree.bsrt_read. One can also serialise to JSON, but this results in a much larger file (a factor of ten) and so correspondingly slow to read/write. Useful, nevertheless, for debugging and loading into a native Ruby hash format (see #to_h).
All rectangles used in the library are simply arrays of floats, the lower value for each dimension, followed by the upper value for each dimension. Thus
[0, 0, 1, 2]
is the rectangle with 0 ≤ x ≤ 1 and 0 ≤ y ≤ 2. Upper and lower values may coincide (to create a line segment in 2-space, for example) but a lower value larger than the upper value will cause an error.
It is anticipated that the ids passed to the library will be used as an index for application specific data to which this rectangle relates (its location in an array, or a DB id) but this is entirely at the discretion of the caller, the library makes no use of the value, treating it as payload. In particular, the value may be non-unique and may be zero. One should note that the id type used internally by the library is determined at compile-time (with the RTREE_ID_TYPE variable) and by default this is a 64-bit unsigned integer.
Defined Under Namespace
Classes: Style
Constant Summary
Constants inherited from RTreeBase
RTreeBase::AXIS_HEIGHT, RTreeBase::AXIS_WIDTH, RTreeBase::SPLIT_GREENE, RTreeBase::SPLIT_LINEAR, RTreeBase::SPLIT_QUADRATIC
Class Method Summary collapse
-
.bsrt_read(io) ⇒ RTree
Create a new RTree instance from BSRT (binary serialised R-tree) stream.
-
.bugreport ⇒ String
Email address for librtree bug reports.
-
.csv_read(io, dim, split: :quadratic, node_page: 0) ⇒ RTree
Build a new RTree instance from CSV stream.
-
.from_bsrt(bsrt) ⇒ RTree
Create a new RTree instance from BSRT (binary serialised R-tree) string.
-
.from_csv(csv, dim, **kwarg) ⇒ RTree
Build a new RTree instance from CSV string.
-
.from_json(json) ⇒ RTree
Create a new RTree instance from JSON string.
-
.json_read(io) ⇒ RTree
Create a new RTree instance from JSON stream.
-
.url ⇒ String
Librtree homepage.
-
.version ⇒ Array<Integer>
Version of librtree.
Instance Method Summary collapse
-
#add_rect(id, coords) ⇒ self
Add a rectangle to the RTree.
-
#branch_size ⇒ Integer
The size in bytes of a branch.
-
#branching_factor ⇒ Integer
The number of branches from each node.
-
#bsrt_write(io) ⇒ self
Serialise to BSRT (binary serialised R-tree) stream.
-
#clone ⇒ RTree
Create a deep copy.
-
#dim ⇒ Integer
The dimension of the R-tree.
-
#empty? ⇒ Boolean
Whether the RTree has any rectangles or not.
-
#eq?(other) ⇒ Boolean
(also: #==)
Equality of RTrees.
-
#height ⇒ Integer
The height to the tree in the usual mathematical sense.
-
#initialize(dim, split: :quadratic, node_page: 0) ⇒ RTree
constructor
Initialize a new (empty) RTree.
-
#json_write(io) ⇒ self
Serialise to JSON stream.
-
#node_size ⇒ Integer
The size in bytes of a node.
-
#page_size ⇒ Integer
The bytes in a page of memory.
-
#postscript(io, style, height: nil, width: nil, margin: 0) ⇒ Object
Create a PostScript plot of the RTree.
-
#rect_size ⇒ Integer
The size in bytes of a rectangle.
-
#search(coords) ⇒ Array<Integer>
Search the RTree.
-
#size ⇒ Integer
The total bytes allocated for the instance.
-
#to_bsrt ⇒ String
Serialise to BSRT string.
-
#to_h ⇒ Hash
The RTree structure in hash form.
-
#to_json ⇒ String
Serialise to JSON string.
-
#unit_sphere_volume ⇒ Float
The volume of the unit sphere in the R-tree’s dimension.
-
#update! {|id, coords| ... } ⇒ self
Update the RTree.
Constructor Details
#initialize(dim, split: :quadratic, node_page: 0) ⇒ RTree
Initialize a new (empty) RTree
281 282 283 284 285 |
# File 'lib/rtree.rb', line 281 def initialize(dim, split: :quadratic, node_page: 0) @split = split @node_page = node_page super(dim, flags) end |
Class Method Details
.bsrt_read(io) ⇒ RTree
Create a new RTree instance from BSRT (binary serialised R-tree) stream
169 170 171 |
# File 'lib/rtree.rb', line 169 def bsrt_read(io) super end |
.bugreport ⇒ String
Returns email address for librtree bug reports.
220 221 222 |
# File 'lib/rtree.rb', line 220 def bugreport super end |
.csv_read(io, dim, split: :quadratic, node_page: 0) ⇒ RTree
The CSV file (without header) should have the id in the first column, then twice as many floats as the dimension. Extra columns may be present and will be ignored (this useful feature is the reason that the dimension is a required argument).
Build a new RTree instance from CSV stream
195 196 197 198 |
# File 'lib/rtree.rb', line 195 def csv_read(io, dim, split: :quadratic, node_page: 0) flags = split_flag(split) | node_page_flag(node_page) super(io, dim, flags) end |
.from_bsrt(bsrt) ⇒ RTree
Create a new RTree instance from BSRT (binary serialised R-tree) string
179 180 181 |
# File 'lib/rtree.rb', line 179 def from_bsrt(bsrt) deserialise(bsrt, Encoding::BINARY) { |io| bsrt_read(io) } end |
.from_csv(csv, dim, **kwarg) ⇒ RTree
Build a new RTree instance from CSV string
206 207 208 209 210 |
# File 'lib/rtree.rb', line 206 def from_csv(csv, dim, **kwarg) deserialise(csv, Encoding::UTF_8) do |io| csv_read(io, dim, **kwarg) end end |
.from_json(json) ⇒ RTree
Create a new RTree instance from JSON string
157 158 159 |
# File 'lib/rtree.rb', line 157 def from_json(json) deserialise(json, Encoding::UTF_8) { |io| json_read(io) } end |
.json_read(io) ⇒ RTree
Create a new RTree instance from JSON stream
148 149 150 |
# File 'lib/rtree.rb', line 148 def json_read(io) super end |
.url ⇒ String
Returns librtree homepage.
226 227 228 |
# File 'lib/rtree.rb', line 226 def url super end |
.version ⇒ Array<Integer>
Returns version of librtree.
214 215 216 |
# File 'lib/rtree.rb', line 214 def version @version ||= super.split('.').map(&:to_i) end |
Instance Method Details
#add_rect(id, coords) ⇒ self
Add a rectangle to the RTree
307 308 309 |
# File 'lib/rtree.rb', line 307 def add_rect(id, coords) super end |
#branch_size ⇒ Integer
Returns the size in bytes of a branch.
455 456 457 |
# File 'lib/rtree.rb', line 455 def branch_size super end |
#branching_factor ⇒ Integer
Returns the number of branches from each node.
461 462 463 |
# File 'lib/rtree.rb', line 461 def branching_factor super end |
#bsrt_write(io) ⇒ self
Serialise to BSRT (binary serialised R-tree) stream
379 380 381 |
# File 'lib/rtree.rb', line 379 def bsrt_write(io) super end |
#dim ⇒ Integer
Returns the dimension of the R-tree.
420 421 422 |
# File 'lib/rtree.rb', line 420 def dim super end |
#empty? ⇒ Boolean
Whether the RTree has any rectangles or not
357 358 359 |
# File 'lib/rtree.rb', line 357 def empty? height.zero? end |
#eq?(other) ⇒ Boolean Also known as: ==
Equality of RTrees. This is a rather strict equality, not only must the tree have the same rectangles, they must be in the same order. Certainly #clone will produce an instance which is equal in this sense.
412 413 414 |
# File 'lib/rtree.rb', line 412 def eq?(other) super end |
#height ⇒ Integer
The height to the tree in the usual mathematical sense
350 351 352 |
# File 'lib/rtree.rb', line 350 def height super end |
#json_write(io) ⇒ self
Serialise to JSON stream
368 369 370 |
# File 'lib/rtree.rb', line 368 def json_write(io) super end |
#node_size ⇒ Integer
Returns the size in bytes of a node.
443 444 445 |
# File 'lib/rtree.rb', line 443 def node_size super end |
#page_size ⇒ Integer
Returns the bytes in a page of memory.
437 438 439 |
# File 'lib/rtree.rb', line 437 def page_size super end |
#postscript(io, style, height: nil, width: nil, margin: 0) ⇒ Object
Create a PostScript plot of the RTree
487 488 489 490 491 492 493 494 495 496 497 498 499 |
# File 'lib/rtree.rb', line 487 def postscript(io, style, height: nil, width: nil, margin: 0) if height && width then raise ArgumentError, 'cannot specify both height and width' end if height then axis = AXIS_HEIGHT extent = height else axis = AXIS_WIDTH extent = width || 216 end super(style, axis, extent, margin, io) end |
#rect_size ⇒ Integer
Returns the size in bytes of a rectangle.
449 450 451 |
# File 'lib/rtree.rb', line 449 def rect_size super end |
#search(coords) ⇒ Array<Integer>
Search the RTree
317 318 319 320 321 322 323 324 325 |
# File 'lib/rtree.rb', line 317 def search(coords) if block_given? then super else ids = [] super(coords) { |id| ids << id } ids end end |
#size ⇒ Integer
This method traverses the entire tree summing the contributions for each node (rather than maintaining a running count). Performance-minded users may wish to cache this value (invalidating the cache when calling #add_rect of course).
Returns the total bytes allocated for the instance.
431 432 433 |
# File 'lib/rtree.rb', line 431 def size super end |
#to_bsrt ⇒ String
Serialise to BSRT string
395 396 397 |
# File 'lib/rtree.rb', line 395 def to_bsrt serialise(Encoding::BINARY) { |io| bsrt_write(io) } end |
#to_h ⇒ Hash
The RTree structure in hash form
402 403 404 |
# File 'lib/rtree.rb', line 402 def to_h JSON.parse(to_json, symbolize_names: true) end |
#to_json ⇒ String
Serialise to JSON string
387 388 389 |
# File 'lib/rtree.rb', line 387 def to_json serialise(Encoding::UTF_8) { |io| json_write(io) } end |
#unit_sphere_volume ⇒ Float
Returns the volume of the unit sphere in the R-tree’s dimension.
468 469 470 |
# File 'lib/rtree.rb', line 468 def unit_sphere_volume super end |
#update! {|id, coords| ... } ⇒ self
In the C library, the implementation (via a C callback function) is much faster than rebuilding the R-tree; in this Ruby interface the callback must convert C floats to Ruby, yield them to the block and then convert the returned Ruby Floats to C; so we would expect that it loses much of its competitive advantage when compared to an R-tree rebuild.
Update the RTree. Modifies the rectangles in-place without changing the tree structure. Provided that the changes are small, the search efficiency should be close to that of freshly built RTree.
343 344 345 |
# File 'lib/rtree.rb', line 343 def update! super end |