Class Definition: RTree

Class: RTree

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

Given a set or rectangles (or higher dimensional cuboids) and their associated ids, one can build an RTree using the 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 Octave-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 applies a user-supplied callback function to the ids of all of the input rectangles which intersect it.

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 the bsrt_read class method. 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.

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.

RTree: obj = RTree (dim, split, np)

Create a new (empty) RTree instance.

dim

The dimension of the tree to create, an integer greater than 0;

split

A string indicating the splitting strategy, one of "linear", "quadratic" or "greene", default "quadratic". The linear strategy is faster to build, the quadratic and Greene strategies produce better-quality R-trees which are faster to query.

np

The number of nodes-per-page, default 0. 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. 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.

See also: RTree.csv_read, RTree.add_rect

Method: add_rect

RTree: add_rect (id, rect)

Add a rectangle rect to the RTree instance.

Method: branch_size

RTree: n = branch_size ()

The size n in bytes of a branch.

Method: branching_factor

RTree: n = branching_factor ()

The number n of branches from each node.

Method: bsrt_read

RTree: obj = bsrt_read (io_arg)

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

Example:

 
 rtree = RTree.bsrt_read ("file.bsrt");

See also: RTree.from_bsrt, RTree.bsrt_write

Method: bsrt_write

RTree: bsrt_write (io_arg)

Serialise to BSRT (binary serialised R-tree) stream or path io_arg.

Method: bugreport

RTree: str = bugreport ()

The email address for bug reports.

Method: clone

RTree: obj = clone ()

Create a deep copy.

Method: csv_read

RTree: obj = csv_read (io_arg, dim, split, np)

Create a new RTree instance from CSV path or stream.

io_arg

A path or readable text-stream of CSV data;

dim

The dimension of the tree to construct;

split

A string indicating the splitting strategy, one of "linear", "quadratic" or "greene", default "quadratic";

np

The number of nodes-per-page, or 0 for heuristic choice, default 0

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 dim is a required argument).

Method: csv_write

RTree: csv_write (io_arg)

Serialise to CSV stream or path io_arg.

Method: dim

RTree: n = dim ()

The dimension n of the R-tree.

Method: empty

RTree: b = empty ()

Whether or not the tree is empty (has no rectangles)

Method: envelope

RTree: rect = envelope ()

Return the envelope, the minimal rectange which contains all of the rectangles so-far inserted into the RTree, Will raise if the rtree is empty.

Method: eq

RTree: bool = eq (other)

Equality of RTrees.

As is usual with Octave, this method is called when one uses the infix equality operator, i.e., A == B is the same as A.eq (B).

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.

See also: RTree.ne, RTree.clone

Method: from_bsrt

RTree: obj = from_bsrt (bsrt)

Create (deserialise) an RTree instance from BSRT string bsrt.

See also: RTree.to_bsrt, RTree.bsrt_read

Method: from_json

RTree: obj = from_json (json)

Create (deserialise) an RTree instance from JSON string json.

See also: RTree.json_read, RTree.bsrt_read

Method: height

RTree: n = height ()

The height of the tree in the usual mathematical sense.

Method: json_read

RTree: obj = json_read (io_arg)

Create (deserialise) an RTree instance from JSON path or stream io_arg.

Example:

 
 rtree = RTree.json_read ("file.json");

See also: RTree.to_json, RTree.json_write

Method: json_write

RTree: json_write (io_arg)

Serialise to JSON stream or path io_arg.

Example:

 
 rtree.json_write ('file.json');

See also: RTree.json_read, RTree.bsrt_read

Method: name

RTree: str = name ()

The name of the wrapped C library.

Method: ne

RTree: bool = ne (other)

Inequality of RTrees.

As is usual with Octave, this method is called when one uses the infix inequality operator, i.e., A != B is the same as A.ne (B).

See also: RTree.eq

Method: node_size

RTree: n = node_size ()

The size n in bytes of a node.

Method: page_size

RTree: n = page_size ()

The size n in bytes of a page of memory.

Method: postscript

RTree: postscript (io_arg, style, axis, extent, margin)

Create a PostScript plot of the RTree instance.

io_arg

A path, or writable text stream (as returned by fopen);

style

An instance of the RTreeStyle class describing the fill colour and stroke width and colour for each level of the tree.

axis

The axis to which the extent variable is to be applied, one of "height" or "width" (default "width");

extent

The size of the output plot on the specified axis in units of PostScript point, 1/72 inch, (default 216 is 3 inches);

margin

Extra space around the plot in units of PostScript point, (default 0).

See also: RTreeStyle

Method: rect_size

RTree: n = rect_size ()

The size n in bytes of a rectangle.

Method: search

RTree: ctx = search (rect, f, ctx)

Search the RTree for intersecting rectangles.

rect

The search rectangle;

f

A user-defined function which takes as argument the id of found intersecting rectangle and the context ctx passed as the final argument, it should return this (usually modified) context;

ctx

Any object, this will be passed as the second input argument to the function f and should then be returned.

Examples:

Count the number of intersecting rectangles:

 
 function val = f (id, count)
   val = count + 1;
 endfunction

 count = rtree.search (rect, @f, 0);

Return all ids of intersecting rectangles:

 
 function val = f (id, ids)
   val = [ids, id];
 endfunction

 ids = rtree.search (rect, @f, []);

Note that this sort of "accumulation" function will return results for all of the rectangles given a sufficiently large search rectangle; thus untrusted (user-supplied) search rectangles may cause excessive resource usage.

Method: size

RTree: n = size ()

The total bytes n allocated for the instance.

This method traverses the entire tree summing 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).

Method: to_bsrt

RTree: bsrt = to_bsrt ()

Serialise to BSRT string.

Example:

 
 bsrt = rtree.to_bsrt ();

See also: RTree.bsrt_write

Method: to_csv

RTree: csv = to_csv ()

Serialise to CSV string.

Example:

 
 csv = rtree.to_csv ();

See also: RTree.csv_write

Method: to_json

RTree: json = to_json ()

Serialise to JSON string.

Example:

 
 json = rtree.to_json ();

See also: RTree.json_write

Method: unit_sphere_volume

RTree: v = unit_sphere_volume ()

The volume v of the unit sphere in the instance’s dimension.

Method: update

RTree: update (f, ctx)

Update the RTree instance. 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.

f

A user-defined function which takes as arguments a rectangle and the context ctx passed as the final argument, it should return the (usually modified) context;

ctx

Any object, this will be passed as the second input argument to the function f. If that function does not access the context, then the update method can omit it.

Example:

A function which shifts all rectangles by 1 on each axis:

 
 function val = f (rect, context)
   val = rect + 1;
 endfunction

called as rtree.update (@f).

Note that in the C library, the implementation (via a C callback function) is much faster than rebuilding the R-tree; in this Octave interface the callback must convert C floats to Octave, modify them and then convert the returned Octave floats to C; so we would expect that it loses much of its competitive advantage when compared to an R-tree rebuild.

Method: url

RTree: str = url ()

The URL of the package’s homepage.

Method: version

RTree: a = version ()

The project’s version as a triple of integers.