The library provides an R-tree implementation as originally designed by Guttman in 1984. For insertions, the quadratic split method is used. The library is restricted to planar case and does not provide external memory management.
Generally (but restricted to planar case here), an R-tree (or R-tree like) structure is used to equip dynamically a given model of a set of planar objects with index information, so that for a given planar object, possibly outside the model, the incident objects can be accessed effectively. Because an R-tree works with object ranges - axis parallel rectangular approximations of the objects - the extent to which an effective access is achieved depends strongly on the proportionality of objects incidences number with the objects range incidences number.
The library assumes each object record of the input model to be accessible through a 4-byte identifier named record identifier. Objects are assumed to have sufficiently effective 4-byte integer range approximation, meaning that possible rounding of coordinates does not increase the ranges significantly.
The created R-tree implementation is named UfRep which stands for Uniform Representation. Each entry, whether in an inner node or in a leaf node, has 16 bytes for its range and 4 bytes for its identifier. In the case of an inner node the identifier addresses the node with children entries, in the case of a leaf node the identifier is the corresponding record identifier.
Nodes are equipped with a header information including the reference to node's parent entry.
An example application, Segment Incidences Detector, is included with its source files located in examapps/SegIncid directory. The application shows how to use the library for detecting singularities in incidences between line segments.
References:
1.2.16