Namespace NetTopologySuite.Index.Quadtree

Contains classes that implement a Quadtree spatial index

Classes

DoubleBits

DoubleBits manipulates Double numbers by using bit manipulation and bit-field extraction. For some operations (such as determining the exponent) this is more accurate than using mathematical operations (which suffer from round-off error). The algorithms and constants in this class apply only to IEEE-754 double-precision floating point format.

ExcludingItemVisitor<T>

Item visitor that specifically excludes a predefined area.

IntervalSize

Provides a test for whether an interval is so small it should be considered as zero for the purposes of inserting it into a binary tree. The reason this check is necessary is that round-off error can cause the algorithm used to subdivide an interval to fail, by computing a midpoint value which does not lie strictly between the endpoints.

Key

A Key is a unique identifier for a node in a quadtree. It contains a lower-left point and a level number. The level number is the power of two for the size of the node envelope.

NodeBase<T>

The base class for nodes in a Quadtree.

Node<T>

Represents a node of a Quadtree. Nodes contain items which have a spatial extent corresponding to the node's position in the quadtree.

Quadtree<T>

A Quadtree is a spatial index structure for efficient range querying of items bounded by 2D rectangles.
Geometrys can be indexed by using their Envelopes.
Any type of object can also be indexed, as long as it has an extent that can be represented by an Envelope.

This Quadtree index provides a primary filter for range rectangle queries. The various query methods return a list of all items which may intersect the query rectangle. Note that it may thus return items which do not in fact intersect the query rectangle. A secondary filter is required to test for actual intersection between the query rectangle and the envelope of each candidate item. The secondary filter may be performed explicitly, or it may be provided implicitly by subsequent operations executed on the items (for instance, if the index query is followed by computing a spatial predicate between the query geometry and tree items, the envelope intersection check is performed automatically.

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accommodate any extent of dataset.

This data structure is also known as an MX-CIF quadtree following the terminology usage of Samet and others.

Root<T>

QuadRoot is the root of a single Quadtree. It is centred at the origin, and does not have a defined extent.