Namespace NetTopologySuite.Index.Strtree

Contains 2-D and 1-D versions of the Sort-Tile-Recursive (STR) tree, a query-only R-tree.

Classes

AbstractNode<T, TItem>

A node of an AbstractSTRtree<T, TItem>. A node is one of:

A node stores the bounds of its children, and its level within the index tree.

AbstractSTRtree<T, TItem>

Base class for STRtree and SIRtree. STR-packed R-trees are described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

This implementation is based on IBoundable<T, TItem>s rather than just AbstractNode<T, TItem>s, because the STR algorithm operates on both nodes and data, both of which are treated as IBoundable<T, TItem>s.

EnvelopeDistance

Utility functions for working with Envelopes.

GeometryItemDistance

An IItemDistance<T, TItem> function for items which are Geometry using the Distance(Geometry) method.

To make this distance function suitable for using to query a single index tree, the distance metric is anti-reflexive. That is, if the two arguments are the same Geometry object, the distance returned is MaxValue.

Interval

A contiguous portion of 1D-space. Used internally by SIRtree.

ItemBoundable<T, TItem>

Boundable wrapper for a non-Boundable spatial object. Used internally by AbstractSTRtree.

SIRtree<TItem>

One-dimensional version of an STR-packed R-tree. SIR stands for "Sort-Interval-Recursive". STR-packed R-trees are described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

STRtree<TItem>

A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatial data.

The STR packed R-tree is simple to implement and maximizes space utilization; that is, as many leaves as possible are filled to capacity. Overlap between nodes is far less than in a basic R-tree. However, the index is semi-static; once the tree has been built (which happens automatically upon the first query), items may not be added.
Items may be removed from the tree using Remove(Envelope, TItem).

Described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

Note that inserting items into a tree is not thread-safe. Inserting performed on more than one thread must be synchronized externally.

Querying a tree is thread-safe. The building phase is done synchronously, and querying is stateless.

Interfaces

AbstractSTRtree<T, TItem>.IIntersectsOp

IItemDistance<T, TItem>

A function method which computes the distance between two IBoundable<T, TItem>s in an STRtree<TItem>. Used for Nearest Neighbour searches.

To make a distance function suitable for querying a single index tree via NearestNeighbour(IItemDistance<Envelope, TItem>), the function should have a non-zero reflexive distance. That is, if the two arguments are the same object, the distance returned should be non-zero. If it is required that only pairs of distinct items be returned, the distance function must be anti-reflexive, and must return MaxValue for identical arguments.