Class: RTree

Inherits:
RTreeBase
  • Object
show all
Defined in:
lib/rtree.rb

Overview

A Ruby native extension implementing the R-tree spatial index of Guttman-Green. The code is an embedded version of librtree.

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.

Author:

  • RTree J. J. Green

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

Instance Method Summary collapse

Constructor Details

#initialize(dim, split: :quadratic, node_page: 0) ⇒ RTree

Initialize a new (empty) RTree

Parameters:

  • dim (Integer) —

    the dimension of the tree

  • split (:linear, :quadratic, :greene) (defaults to: :quadratic) —

    determines the splitting strategy, the linear strategy is faster to build, the quadratic and greene strategies produce better-quality R-trees which are faster to query.

  • node_page (Integer) (defaults to: 0) —

    the nodes-per-page value. This value can affect performance quite dramatically, particularly build time. A value which is too large would result in an infeasible branching factor for the R-tree and will cause the function to error with errno set to EINVAL. A value of zero is permitted and the default; in this case the function will choose a good value based on heuristics. You may get better performance for your use-case by manual experimentation, but zero is a good place to start.



309
310
311
312
313
 
# File 'lib/rtree.rb', line 309

def initialize(dim, split: :quadratic, node_page: 0)
  @split = split
  @node_page = node_page
  super(dim, flags)
end

Class Method Details

.bsrt_read(io_arg) ⇒ RTree

Create a new RTree instance from BSRT (binary serialised R-tree) path or stream

Examples:

Read from path

rtree = RTree.bsrt_read('rtree.bsrt')

Parameters:

  • io_arg (String|IO) —

    a path or readable stream

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



188
189
190
191
192
 
# File 'lib/rtree.rb', line 188

def bsrt_read(io_arg)
  RTree::IOUtil.io_with_mode(io_arg, 'rb') do |io|
    super(io)
  end
end

.bugreport ⇒ String

Returns email address for librtree bug reports.

Returns:

  • (String) —

    email address for librtree bug reports



243
244
245
 
# File 'lib/rtree.rb', line 243

def bugreport
  super
end

.csv_read(io_arg, dim, split: :quadratic, node_page: 0) ⇒ RTree

Note:

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 path or stream

Parameters:

  • io_arg (String|IO) —

    a path or readable stream

  • dim (Integer) —

    the dimension of the tree

  • split (:linear, :quadratic, :greene) (defaults to: :quadratic) —

    See #initialize

  • node_page (Integer) (defaults to: 0) —

    See #initialize

Returns:

  • (RTree) —

    the newly built RTree



216
217
218
219
220
221
 
# File 'lib/rtree.rb', line 216

def csv_read(io_arg, dim, split: :quadratic, node_page: 0)
  flags = split_flag(split) | node_page_flag(node_page)
   RTree::IOUtil.io_with_mode(io_arg, 'r') do |io|
     super(io, dim, flags)
  end
end

.from_bsrt(bsrt) ⇒ RTree

Create a new RTree instance from BSRT (binary serialised R-tree) string

Parameters:

  • bsrt (String) —

    a binary encoded string

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



200
201
202
 
# File 'lib/rtree.rb', line 200

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

Parameters:

  • csv (String) —

    the CSV data in a string

  • dim (Integer) —

    the dimension of the tree

  • kwarg (Hash) —

    As for csv_read

Returns:

  • (RTree) —

    the newly built RTree



229
230
231
232
233
 
# File 'lib/rtree.rb', line 229

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

Parameters:

  • json (String) —

    a JSON string

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



176
177
178
 
# File 'lib/rtree.rb', line 176

def from_json(json)
  deserialise(json, Encoding::UTF_8) { |io| json_read(io) }
end

.json_read(io_arg) ⇒ RTree

Create a new RTree instance from JSON path or stream

Examples:

Using a path

rtree = RTree.json_read('rtree.json')

Using a stream

rtree = File.open('rtree.json', 'r') { |io| RTree.json_read(io) }

Parameters:

  • io_arg (String|IO) —

    a path or readable stream

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



165
166
167
168
169
 
# File 'lib/rtree.rb', line 165

def json_read(io_arg)
  RTree::IOUtil.io_with_mode(io_arg, 'r') do |io|
    super(io)
  end
end

.url ⇒ String

Returns librtree homepage.

Returns:

  • (String) —

    librtree homepage



249
250
251
 
# File 'lib/rtree.rb', line 249

def url
  super
end

.version ⇒ Array<Integer>

Returns version of librtree.

Returns:

  • (Array<Integer>) —

    version of librtree



237
238
239
 
# File 'lib/rtree.rb', line 237

def version
  @version ||= super.split('.').map(&:to_i)
end

Instance Method Details

#add_rect(id, coords) ⇒ self

Add a rectangle to the RTree

Examples:

Add a rectangle to a dimension two RTree

rtree = RTree.new(2)
rtree.add_rect(7, [0, 0, 1, 1])

Parameters:

  • id (Integer) —

    the id of the rectangle. It is anticipated that the id will be used as an index for application specific data to which this rectangle relates, 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.

  • coords (Array<Float>) —

    the extent of the rectangle, the minima for each dimension, then the maxima for each dimension.

Returns:

  • (self) 


335
336
337
 
# File 'lib/rtree.rb', line 335

def add_rect(id, coords)
  super
end

#branch_size ⇒ Integer

Returns the size in bytes of a branch.

Returns:

  • (Integer) —

    the size in bytes of a branch



485
486
487
 
# File 'lib/rtree.rb', line 485

def branch_size
  super
end

#branching_factor ⇒ Integer

Returns the number of branches from each node.

Returns:

  • (Integer) —

    the number of branches from each node



491
492
493
 
# File 'lib/rtree.rb', line 491

def branching_factor
  super
end

#bsrt_write(io_arg) ⇒ self

Serialise to BSRT (binary serialised R-tree)

Examples:

Write to file

rtree.bsrt_write('rtree.bsrt')

Parameters:

  • io_arg (String|IO) —

    a path or writable stream

Returns:

  • (self)

See Also:



408
409
410
411
 
# File 'lib/rtree.rb', line 408

def bsrt_write(io_arg)
  RTree::IOUtil.io_with_mode(io_arg, 'wb') { |io| super(io) }
  self
end

#clone ⇒ RTree

Create a deep copy

Returns:

  • (RTree) —

    a deep copy of the RTree



318
319
320
 
# File 'lib/rtree.rb', line 318

def clone
  super
end

#dim ⇒ Integer

Returns the dimension of the R-tree.

Returns:

  • (Integer) —

    the dimension of the R-tree



450
451
452
 
# File 'lib/rtree.rb', line 450

def dim
  super
end

#empty? ⇒ Boolean

Whether the RTree has any rectangles or not

Returns:

  • (Boolean) —

    true if the RTree is empty



385
386
387
 
# File 'lib/rtree.rb', line 385

def empty?
  super
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.

Returns:

  • (Boolean) —

    true if the instances are identical



442
443
444
 
# File 'lib/rtree.rb', line 442

def eq?(other)
  super
end

#height ⇒ Integer

The height to the tree in the usual mathematical sense

Returns:

  • (Integer) —

    the tree height



378
379
380
 
# File 'lib/rtree.rb', line 378

def height
  super
end

#json_write(io_arg) ⇒ self

Serialise to JSON

Examples:

Write to file

rtree.json_write('rtree.json')

Parameters:

  • io_arg (String|IO) —

    a path or writable stream

Returns:

  • (self)

See Also:



396
397
398
399
 
# File 'lib/rtree.rb', line 396

def json_write(io_arg)
  RTree::IOUtil.io_with_mode(io_arg, 'w') { |io| super(io) }
  self
end

#node_size ⇒ Integer

Returns the size in bytes of a node.

Returns:

  • (Integer) —

    the size in bytes of a node



473
474
475
 
# File 'lib/rtree.rb', line 473

def node_size
  super
end

#page_size ⇒ Integer

Returns the bytes in a page of memory.

Returns:

  • (Integer) —

    the bytes in a page of memory



467
468
469
 
# File 'lib/rtree.rb', line 467

def page_size
  super
end

#postscript(io_arg, style, height: nil, width: nil, margin: 0) ⇒ Object

Create a PostScript plot of the RTree

Parameters:

  • io_arg (String|IO) —

    a path or writeable stream

  • style (RTree::Style) —

    a style object describing the fill colour and stroke width and colour for each level of the tree.

  • height (Float) (defaults to: nil) —

    the height of the plot in units of PostScript point (1/72 inch)

  • width (Float) (defaults to: nil) —

    the width of the plot in units of PostScript point (1/72 inch), if neither height nor width is given then a width of 216 (3 inches) will be taken as default

  • margin (Float) (defaults to: 0) —

    extra space around the plot in units of PostScript point (1/72 inch), default zero



515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
 
# File 'lib/rtree.rb', line 515

def postscript(io_arg, 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
  RTree::IOUtil.io_with_mode(io_arg, 'w') do |io|
    super(style, axis, extent, margin, io)
  end
end

#rect_size ⇒ Integer

Returns the size in bytes of a rectangle.

Returns:

  • (Integer) —

    the size in bytes of a rectangle



479
480
481
 
# File 'lib/rtree.rb', line 479

def rect_size
  super
end

#search(coords) ⇒ Array<Integer>

Search the RTree

Parameters:

  • coords (Array<Float>) —

    the search rectangle, as #add_rect

Returns:

  • (Array<Integer>) —

    the ids of all rectangles which intersect the search rectangle. If a block is given then these values will be yielded to the block (one at a time).



345
346
347
348
349
350
351
352
353
 
# File 'lib/rtree.rb', line 345

def search(coords)
  if block_given? then
    super
  else
    ids = []
    super(coords) { |id| ids << id }
    ids
  end
end

#size ⇒ Integer

Note:

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.

Returns:

  • (Integer) —

    the total bytes allocated for the instance



461
462
463
 
# File 'lib/rtree.rb', line 461

def size
  super
end

#to_bsrt ⇒ String

Serialise to BSRT string

Returns:

  • (String) —

    the binary encoded BSRT

See Also:



425
426
427
 
# File 'lib/rtree.rb', line 425

def to_bsrt
  serialise(Encoding::BINARY) { |io| bsrt_write(io) }
end

#to_h ⇒ Hash

The RTree structure in hash form

Returns:

  • (Hash) 


432
433
434
 
# File 'lib/rtree.rb', line 432

def to_h
  JSON.parse(to_json, symbolize_names: true)
end

#to_json ⇒ String

Serialise to JSON string

Returns:

  • (String) —

    the UTF-8 encoded JSON

See Also:



417
418
419
 
# File 'lib/rtree.rb', line 417

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.

Returns:

  • (Float) —

    the volume of the unit sphere in the R-tree’s dimension



498
499
500
 
# File 'lib/rtree.rb', line 498

def unit_sphere_volume
  super
end

#update! {|id, coords| ... } ⇒ self

Note:

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.

Examples:

Shift all rectangles by ε

rtree.update! { |id, coords| coords.map { |x| x + ε } }

Yield Parameters:

Yield Returns:

  • (Array<Float>) —

    the modified rectangle extent

Returns:

  • (self) 


371
372
373
 
# File 'lib/rtree.rb', line 371

def update!
  super
end