The RTree class¶

The main class for the librtree package, load it with

from librtree import RTree

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 Python-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 function to 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 the bsrt_write() instance method 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 and loading into a native Python dict format (see the to_dict() method).

All rectangles used in the library are simply lists (or tuples) 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 a list, 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 and by default this is a 64-bit unsigned integer.

class RTree(dim, split='quadratic', node_page=0)¶

Bases: Serialise, Deserialise

Instances of this class implememt the R-tree spatial index of Guttman-Green.

Parameters:

dim (int) – the dimension of the tree, must be a postive integer;
split (Split) – one of ‘linear’, ‘quadratic’, ‘greene’, which 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 (int) – 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.

__eq__(other)¶

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.

Return type:: bool

add_rect(rect_id, coords)¶

Add a rectangle to the RTree.

Parameters:

rect_id (int) – 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 (Tuple[float, ...]) – the extent of the rectangle, the minima for each dimension, then the maxima for each dimension.

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

property branch_size: int¶: The size in bytes of a branch.

property branching_factor: int¶: The number of branches from each node.

classmethod bsrt_read(io_arg)¶

Build a new RTree instance from BSRT.

Parameters:: io_arg (IOBase | Path | str) – the stream or path (string or object) from which to read the BSRT bytes.
Return type:: RTree

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

bsrt_write(io_arg)¶

Serialise to BSRT (binary serialised R-tree).

Parameters:: io_arg (IOBase | Path | str) – A writable binary stream or path (string or object) to which to write the BSRT.

Example:

with open('file.bsrt', 'wb') as io:
    rtree.bsrt_write(io)

bugreport: str¶: The email address where bug-reports may be directed.

clone()¶

A deep copy of the RTree.

Return type:: RTree

classmethod csv_read(io_arg, dim, split='quadratic', node_page=0)¶

Build a new RTree instance from CSV.

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).

Parameters:

io_arg (IOBase | Path | str) – a stream or path (string or object) from which to read CSV;
dim (int) – the dimension of the tree;
split (Literal['quadratic', 'linear', 'greene']) – splitting strategy;
node_page (int) – node per page of memory.

Return type:

RTree

rtree = RTree.csv_read('file.csv', 2)

csv_write(io_arg)¶

Serialise to CSV.

Parameters:: io_arg (IOBase | Path | str) – A writable binary stream or path (string or object) to which to write the CSV.

Example:

with open('file.csv', 'wb') as io:
    rtree.csv_write(io)

property dim: int¶: The dimension of the RTree instance.

property envelope: Tuple[float, ...]¶: The bounding rectangle of all rectangles in the tree, returns None if the tree is empty.

classmethod from_bsrt(bsrt)¶

Create a new RTree instance from BSRT byte-string.

Parameters:: bsrt (bytes) – the BSRT byte-string.
Return type:: RTree

classmethod from_csv(csv, dim, split='quadratic', node_page=0)¶

Build a new RTree instance from CSV string.

Parameters:

csv (str) – the CSV string;
dim (int) – the dimension of the tree;
split (Literal['quadratic', 'linear', 'greene']) – splitting strategy;
node_page (int) – node per page of memory.

Return type:

RTree

classmethod from_json(json)¶

Create a new RTree instance from JSON string.

Parameters:: json (str) – the JSON string.
Return type:: RTree

property height: int¶: The height to the tree in the usual mathematical sense.

property is_empty: bool¶: Whether or not the tree is empty (has no rectangles).

classmethod json_read(io_arg)¶

Build a new RTree instance from JSON.

Parameters:: io_arg (IOBase | Path | str) – a stream or path (string or object) from which to read the JSON.
Return type:: RTree

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

json_write(io_arg)¶

Serialise to JSON.

Parameters:: io_arg (IOBase | Path | str) – A writable text stream or path (string or object) to which to write the JSON.

Example:

rtree.json_write('file.json')

property node_size: int¶: The size in bytes of a node.

property page_size: int¶: The size in bytes in a page of memory.

postscript(io_arg, style, height=None, width=None, margin=0)¶

Create a PostScript plot of the RTree.

Parameters:

io_arg (IOarg) – a writeable stream or path (string or object) to which to write the PostScript;
style (RTreeStyle) – a style object describing the fill colour and stroke width and colour for each level of the tree;
height (float | None) – the height of the plot in units of PostScript point; (1/72 inch)
width (float | None) – 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) – extra space around the plot in units of PostScript point (1/72 inch), default zero.

property rect_size: int¶: The size in bytes of a rectangle.

search(f, rect, context)¶

Search the RTree for intersecting rectangles.

Parameters:

f (Callable) – a callback function, it will be called as f(id, context) for the id of each of the rectangles in the tree which intersect the rect argument. Returns zero to continue, non-zero to terminate;
rect (Tuple[float, ...]) – the search rectangle;
context (Any) – user context to be passed to f.

Example, generate a list of the ids:

def f(id, ids):
    ids.append(id)
    return 0

ids = []
rtree.search(f, (0, 0, 1, 1), ids)

property size: int¶

The total bytes allocated for the instance.

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).

to_bsrt()¶

Serialise to BSRT (binary serialised R-tree) bytes.

Return type:: bytes

to_csv()¶

Serialise to CSV.

Return type:: bytes

to_dict()¶

Serialise to Python dict.

Return type:: dict

to_json()¶

Serialise to JSON string.

Return type:: str

property unit_sphere_volume: float¶: The volume of the unit sphere in the R-tree’s dimension.

update(f, context)¶

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.

Parameters:

f (Callable) – a callback function, it will be called as f(id, coords, context) for the id and the coords of each rectangle in the tree, along with the context. It should return a tuple of modified rectangle extent;
context (Any) – to be passed as the last argument to each call to the callback function f.

url: str¶: The package’s homepage.

version: Tuple[int, ...] = ()¶: The version of the C librtree package embedded.

The RTree class¶

Table of Contents

Previous topic

Next topic

This Page