Class: RTree

Inherits:
RTreeC show all
Defined in:
lib/rtree.rb

Overview

A Ruby wrapper around librtree implementing the R-tree spatial index of Guttman-Green.

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 32-bit unsigned integer.

Author:

  • RTree J. J. Green

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) (defaults to: :quadratic) —

    determines the splitting strategy, the linear strategy is faster to build, the quadratic produces a better-quality R-tree which is 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 case 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.



169
170
171
172
173
 
# File 'lib/rtree.rb', line 169

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

Examples:

Read from file

rtree = File.open('rtree.bsrt', 'r') { |io| RTree.bsrt_read(io) }

Parameters:

  • io (IO) —

    a readable stream object

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



77
78
79
 
# File 'lib/rtree.rb', line 77

def bsrt_read(io)
  super
end

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

Build a new RTree instance from CSV stream

Parameters:

  • io (IO) —

    a readable stream object

  • dim (Integer) —

    the dimension of the tree

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

    See #initialize

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

    See #initialize

Returns:

  • (RTree) —

    the newly built RTree



96
97
98
99
 
# File 'lib/rtree.rb', line 96

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

Parameters:

  • bsrt (String) —

    a binary encoded string

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



86
87
88
 
# File 'lib/rtree.rb', line 86

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



106
107
108
109
110
 
# File 'lib/rtree.rb', line 106

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:



66
67
68
 
# File 'lib/rtree.rb', line 66

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

Examples:

Read from file

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

Parameters:

  • io (IO) —

    a readable stream object

Returns:

  • (RTree) —

    the newly instantiated RTree

See Also:



58
59
60
 
# File 'lib/rtree.rb', line 58

def json_read(io)
  super
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) 


193
194
195
 
# File 'lib/rtree.rb', line 193

def add_rect(id, coords)
  super
end

#bsrt_write(io) ⇒ self

Serialise to BSRT (binary serialised R-tree) stream

Examples:

Write to file

File.open('rtree.bsrt', 'w') { |io| rtree.bsrt_write(io) }

Parameters:

  • io (IO) —

    a writeable stream

Returns:

  • (self)

See Also:



259
260
261
 
# File 'lib/rtree.rb', line 259

def bsrt_write(io)
  super
end

#clone ⇒ RTree

Create a deep copy

Returns:

  • (RTree) —

    a deep copy of the RTree



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

def clone
  super
end

#empty? ⇒ Boolean

Whether the RTree has any rectangles or not

Returns:

  • (Boolean) —

    true if the RTree is empty



239
240
241
 
# File 'lib/rtree.rb', line 239

def empty?
  height == 0
end

#eq?(other) ⇒ Boolean Also known as: ==

Equality of RTrees. This is a rather strict equality, not only must the tree have the same rectangkes, 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



288
289
290
 
# File 'lib/rtree.rb', line 288

def eq?(other)
  super
end

#height ⇒ Integer

The height to the tree in the usual mathematical sense

Returns:

  • (Integer) —

    the tree height



233
234
235
 
# File 'lib/rtree.rb', line 233

def height
  super
end

#json_write(io) ⇒ self

Serialise to JSON stream

Examples:

Write to file

File.open('rtree.json', 'w') { |io| rtree.json_write(io) }

Parameters:

  • io (IO) —

    a writeable stream

Returns:

  • (self)

See Also:



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

def json_write(io)
  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).



202
203
204
205
206
207
208
209
210
 
# File 'lib/rtree.rb', line 202

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

#to_bsrt ⇒ String

Serialise to BSRT string

Returns:

  • (String) —

    the binary encoded BSRT

See Also:



273
274
275
 
# File 'lib/rtree.rb', line 273

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

#to_h ⇒ Hash

The RTree structure in hash form

Returns:

  • (Hash) 


279
280
281
 
# File 'lib/rtree.rb', line 279

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:



266
267
268
 
# File 'lib/rtree.rb', line 266

def to_json
  serialise(Encoding::UTF_8) { |io| json_write(io) }
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 competetive 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) 


227
228
229
 
# File 'lib/rtree.rb', line 227

def update!
  super
end