Name

rtree — build and query R-tree spatial indices

Synopsis

#include <rtree.h>
    
rtree_t* rtree_new( size_t dim,
  unsigned flags);
 
void rtree_destroy( rtree_t *rtree);
 
rtree_t* rtree_clone( const rtree_t *rtree);
 
rtree_height_t rtree_height( const rtree_t *rtree);
 
int rtree_add_rect( rtree_t *rtree,
  rtree_id_t id,
  const rtree_coord_t *rect);
 
int rtree_update( rtree_t *rtree,
  rtree_update_t *f,
  void *context);
 
int rtree_search( const rtree_t *rtree,
  const rtree_coord_t *rect,
  rtree_search_t *f,
  void *context);
 
rtree_t* rtree_csv_read( FILE *stream,
  size_t dim,
  unsigned flags);
 
int rtree_json_write( const rtree_t *rtree,
  FILE *stream);
 
rtree_t* rtree_json_read( FILE *stream);
 
int rtree_bsrt_write( const rtree_t *rtree,
  FILE *stream);
 
rtree_t* rtree_bsrt_read( FILE *stream);
 
int rtree_postscript( const rtree_t *rtree,
  const rtree_postscript_t *options,
  FILE *stream);
 
bool rtree_identical( const rtree_t *rtree0,
  const rtree_t *rtree1);
 
const char* rtree_strerror( int err);
 

DESCRIPTION

On including the header rtree.h the following functions become available:

rtree_new

The size_t argument specifies the dimension of the (empty) R-tree returned; it should be a positive integer. The flags may be one of RTREE_SPLIT_LINEAR, RTREE_SPLIT_QUADRATIC or RTREE_DEFAULT; these determine the splitting strategy, the linear strategy is faster to build, the quadratic produces a better-quality R-tree which is faster to query. The RTREE_DEFAULT value is (and will remain) zero. Which of the splitting strategies it selects may change.

On error, returns NULL, and may set the errno variable to indicate the cause.

rtree_destroy

Releases the memory used by the rtree_t* which is its argument, as returned by rtree_new or rtree_clone.

rtree_clone

Creates and returns a deep-copy of the rtree_t* which is its argument. On failure NULL is returned. The copy shares no data with the original and should be destroyed separately.

A typical use case for this function is a sequence of R-trees which share a common part. Once can create the latter, then clone and add the specific part for each instance.

On error, returns NULL, and may set the errno variable to indicate the cause.

rtree_height

Returns the height of the R-tree in the usual mathematical sense. A newly created rtree_t* has height zero (it has a root-node with no descendants).

The return values is of type rtree_height_t, an unsigned integer type.

rtree_add_rect

Adds a rectangle (or higher-dimensional cuboid) to the R-tree structure specified by the first rtree_t* argument.

The second id argument is an integer used to identify the rectangle. The type rtree_id_t of this integer is determined at compile-time. By default it is the largest unsigned integer type which is no larger than a pointer, so a uint32_t on x86 and uint64_t on the AMD64 architecture. One can, however, override the default at compilation by defining the RTREE_ID_TYPE constant.

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.

The final argument is (a pointer to) an array of rtree_coord_t, twice as many as the dimension of the R-tree. The floating point values are the lower extents of each dimension, followed by the upper extents of each dimension; these values are copied into the tree. By default the rtree_coord_t type is float, but this can be overridden at compilation by defining the RTREE_COORD_TYPE constant to the desired floating-point type.

rtree_update

Modifies the rtree which is the first argument according to the function f which is the second. This function, which has prototype

int f( rtree_id_t id,
  rtree_coord_t *rect,
  void *context);
 

is applied to all of the rectangles in the tree, it is passed the id as used in the constructor, and may modify the rect which is its second argument. If the return value is non-zero, then the iteration will abort and return RTREE_ERR_USER. Otherwise, once all rectangles have been updated, the spatial index will be updated and queries against the tree should be correct.

Notes

  1. The update of the spatial index does not modify the structure of the tree, it just recalculates the bounding rectangles for the parent branches down to the root (which is much faster than rebuilding the tree).

  2. If the rectangles are only slightly modified, then the resulting tree should be nearly as efficient as the original in spatial searching, but if the rectangles are substantially changed then one could find a collapse in search speed, one should instead rebuild the tree from scratch.

  3. If the function does not return RTREE_OK (in particular, if it returns RTREE_ERR_USER) then subsequent spatial queries against the tree may not be correct.

rtree_search

This function searches the rtree_t* which is its first argument for rectangles which intersect the the second rect argument. For each found, the callback function f, whose prototype is

int f( rtree_id_t id,
  void *context);
 

is called. The id is the rectangle identifier as given in rtree_add_rectangle, and the context is the void* passed as the final argument to rtree_search.

The function f should return zero to continue the search, non-zero to terminate it. In the latter case it is this value which rtree_search returns.

rtree_csv_read

Reads rectangles from the stream in the format described by rtree-csv(5) writing them to the rtree_t* returned. One also passes the dimension of the tree as size_t; not guessing this value from the CSV file allows the function to handle files with extra columns. The final flags arguments is as described in rtree_new, above.

On error, returns NULL, and may set the errno variable to indicate the cause. In particular, the value ENOSYS indicates that the library was compiled without CSV support.

rtree_json_write

Writes the R-tree in the first argument to the stream in the second in the JSON format as described in rtree-json(5) .

rtree_json_read

Reads JSON in the format as described in rtree-json(5) from stream and returns the R-tree that it describes.

Note that the read will fail if the JSON input was created on a system with a different page-size, or where the library was compiled with a different float size. In this case one would need to build the R-tree afresh.

On error, returns NULL, and may set the errno variable to indicate the cause. In particular, the value ENOSYS indicates that the library was compiled without JSON support, while EINVAL that the input file is incompatible with the library (a later version, of differing page-size and so on).

rtree_bsrt_write

Writes the R-tree in the first argument to the stream in the second in the BSRT (binary serialised R-tree) format as described in rtree-bsrt(5) .

rtree_bsrt_read

Reads BSRT in the format as described in rtree-bsrt(5) from stream and returns the R-tree that it describes.

Note that the read will fail if the BSRT input was created on a system with a different page-size, or where the library was compiled with a different float size. In this case one would need to build the R-tree afresh.

On error, returns NULL, and may set the errno variable to indicate the cause. In particular, the value ENOSYS indicates that the library was compiled without BSRT support, while EINVAL that the input file is incompatible with the library (a later version, of differing page-size and so on).

rtree_postscript

Plots the rtree argument as PostScript to the specified stream. The appearance of the plot is controlled by the options argument.

rtree_identical

Two R-trees are identical if they have the same nodes, branches and leaves in the same order. This function returns a Boolean indicating whether its arguments are identical or not. It is mainly intended for tests (of rtree_clone and the serialisation functions for example).

rtree_strerror

For library functions which return an integer, zero represents success, non-zero an error. A readable description of the error can be obtained by passing the value to this function. The returned string is a constant: it should not be freed.

The one exception to this is rtree_search, since that returns a user-defined value.

AUTHOR

J. J. Green, .

SEE ALSO

rtree-csv(5) , rtree-json(5) , rtree-bsrt(5) , errno(3).