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

Inheritance

object

Quadtree<T>

Implements

ISpatialIndex<T>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: NetTopologySuite.Index.Quadtree

Assembly: NetTopologySuite.dll

Syntax

[Serializable]
public class Quadtree<T> : ISpatialIndex<T>

Type Parameters

Name	Description
T

Constructors

Quadtree()

Constructs a Quadtree with zero items.

Declaration

public Quadtree()

Properties

Count

Returns the number of items in the tree.

Declaration

public int Count { get; }

Property Value

Type	Description
int

Depth

Returns the number of levels in the tree.

Declaration

public int Depth { get; }

Property Value

Type	Description
int

IsEmpty

Tests whether the index contains any items.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool

Root

Gets a value indicating the root node of this QuadTree

Declaration

public Root<T> Root { get; }

Property Value

Type	Description
Root<T>	The root node of this QuadTree

Methods

EnsureExtent(Envelope, double)

Ensure that the envelope for the inserted item has non-zero extents. Use the current minExtent to pad the envelope, if necessary.

Declaration

public static Envelope EnsureExtent(Envelope itemEnv, double minExtent)

Parameters

Type	Name	Description
Envelope	itemEnv
double	minExtent

Returns

Type	Description
Envelope

Insert(Envelope, T)

Declaration

public void Insert(Envelope itemEnv, T item)

Parameters

Type	Name	Description
Envelope	itemEnv
T	item

Query(Envelope)

Queries the tree and returns items which may lie in the given search envelope.

Declaration

public IList<T> Query(Envelope searchEnv)

Parameters

Type	Name	Description
Envelope	searchEnv	The envelope of the desired query area.

Returns

Type	Description
IList<T>	A List of items which may intersect the search envelope

Remarks

Precisely, the items that are returned are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be returned as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not returned - thus providing improved performance over a simple linear scan.

Query(Envelope, IItemVisitor<T>)

Queries the tree and visits items which may lie in the given search envelope.

Declaration

public void Query(Envelope searchEnv, IItemVisitor<T> visitor)

Parameters

Type	Name	Description
Envelope	searchEnv	The envelope of the desired query area.
IItemVisitor<T>	visitor	A visitor object which is passed the visited items

Remarks

Precisely, the items that are visited are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be visited as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not visited - thus providing improved performance over a simple linear scan.

QueryAll()

Return a list of all items in the Quadtree.

Declaration

public IList<T> QueryAll()

Returns

Type	Description
IList<T>

Remove(Envelope, T)

Removes a single item from the tree.

Declaration

public bool Remove(Envelope itemEnv, T item)

Parameters

Type	Name	Description
Envelope	itemEnv	The Envelope of the item to be removed.
T	item	The item to remove.

Returns

Type	Description
bool	true if the item was found (and thus removed).

Implements

ISpatialIndex<T>