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

Inheritance

Object

AbstractSTRtree<Envelope, TItem>

STRtree<TItem>

Implements

ISpatialIndex<TItem>

Inherited Members

AbstractSTRtree<Envelope, TItem>.Build()

AbstractSTRtree<Envelope, TItem>.CreateNode(Int32)

AbstractSTRtree<Envelope, TItem>.CreateParentBoundables(IList<IBoundable<Envelope, TItem>>, Int32)

AbstractSTRtree<Envelope, TItem>.LastNode(IList<IBoundable<Envelope, TItem>>)

AbstractSTRtree<Envelope, TItem>.CompareDoubles(Double, Double)

AbstractSTRtree<Envelope, TItem>.Root

AbstractSTRtree<Envelope, TItem>.NodeCapacity

AbstractSTRtree<Envelope, TItem>.IsEmpty

AbstractSTRtree<Envelope, TItem>.Count

AbstractSTRtree<Envelope, TItem>.GetSize(AbstractNode<Envelope, TItem>)

AbstractSTRtree<Envelope, TItem>.Depth

AbstractSTRtree<Envelope, TItem>.GetDepth(AbstractNode<Envelope, TItem>)

AbstractSTRtree<Envelope, TItem>.Insert(Envelope, TItem)

AbstractSTRtree<Envelope, TItem>.Query(Envelope)

AbstractSTRtree<Envelope, TItem>.Query(Envelope, IItemVisitor<TItem>)

AbstractSTRtree<Envelope, TItem>.ItemsTree()

AbstractSTRtree<Envelope, TItem>.IntersectsOp

AbstractSTRtree<Envelope, TItem>.Remove(Envelope, TItem)

AbstractSTRtree<Envelope, TItem>.BoundablesAtLevel(Int32)

AbstractSTRtree<Envelope, TItem>.GetComparer()

AbstractSTRtree<Envelope, TItem>.ItemBoundables

Object.Equals(Object)

Object.Equals(Object, Object)

Object.GetHashCode()

Object.GetType()

Object.MemberwiseClone()

Object.ReferenceEquals(Object, Object)

Object.ToString()

Namespace: NetTopologySuite.Index.Strtree

Assembly: NetTopologySuite.dll

Syntax

[Serializable]
public class STRtree<TItem> : AbstractSTRtree<Envelope, TItem>, ISpatialIndex<TItem>

Type Parameters

Name	Description
TItem

Constructors

STRtree()

Constructs an STRtree with the default (10) node capacity.

Declaration

public STRtree()

STRtree(Int32)

Constructs an STRtree with the given maximum number of child nodes that a node may have.

Declaration

public STRtree(int nodeCapacity)

Parameters

Type	Name	Description
Int32	nodeCapacity

Remarks

The minimum recommended capacity setting is 4.

STRtree(Int32, AbstractNode<Envelope, TItem>)

Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and the root node

Declaration

public STRtree(int nodeCapacity, AbstractNode<Envelope, TItem> root)

Parameters

Type	Name	Description
Int32	nodeCapacity	The maximum number of child nodes in a node
AbstractNode<Envelope, TItem>	root	The root node that links to all other nodes in the tree

STRtree(Int32, IList<IBoundable<Envelope, TItem>>)

Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and all leaf nodes in the tree

Declaration

public STRtree(int nodeCapacity, IList<IBoundable<Envelope, TItem>> itemBoundables)

Parameters

Type	Name	Description
Int32	nodeCapacity	The maximum number of child nodes in a node
IList<IBoundable<Envelope, TItem>>	itemBoundables	The list of leaf nodes in the tree

Properties

IntersectsOp

Declaration

protected override AbstractSTRtree<Envelope, TItem>.IIntersectsOp IntersectsOp { get; }

Property Value

Type	Description
AbstractSTRtree.IIntersectsOp<>

Overrides

NetTopologySuite.Index.Strtree.AbstractSTRtree<NetTopologySuite.Geometries.Envelope, TItem>.IntersectsOp

Methods

CreateNode(Int32)

Declaration

protected override AbstractNode<Envelope, TItem> CreateNode(int level)

Parameters

Type	Name	Description
Int32	level

Returns

Type	Description
AbstractNode<Envelope, TItem>

Overrides

NetTopologySuite.Index.Strtree.AbstractSTRtree<NetTopologySuite.Geometries.Envelope, TItem>.CreateNode(System.Int32)

CreateParentBoundables(IList<IBoundable<Envelope, TItem>>, Int32)

Creates the parent level for the given child level. First, orders the items by the x-values of the midpoints, and groups them into vertical slices. For each slice, orders the items by the y-values of the midpoints, and group them into runs of size M (the node capacity). For each run, creates a new (parent) node.

Declaration

protected override IList<IBoundable<Envelope, TItem>> CreateParentBoundables(IList<IBoundable<Envelope, TItem>> childBoundables, int newLevel)

Parameters

Type	Name	Description
IList<IBoundable<Envelope, TItem>>	childBoundables
Int32	newLevel

Returns

Type	Description
IList<IBoundable<Envelope, TItem>>

Overrides

NetTopologySuite.Index.Strtree.AbstractSTRtree<NetTopologySuite.Geometries.Envelope, TItem>.CreateParentBoundables(System.Collections.Generic.IList<NetTopologySuite.Geometries.IBoundable<NetTopologySuite.Geometries.Envelope, TItem>>, System.Int32)

CreateParentBoundablesFromVerticalSlice(IList<IBoundable<Envelope, TItem>>, Int32)

Declaration

protected IList<IBoundable<Envelope, TItem>> CreateParentBoundablesFromVerticalSlice(IList<IBoundable<Envelope, TItem>> childBoundables, int newLevel)

Parameters

Type	Name	Description
IList<IBoundable<Envelope, TItem>>	childBoundables
Int32	newLevel

Returns

Type	Description
IList<IBoundable<Envelope, TItem>>

GetComparer()

Declaration

protected override IComparer<IBoundable<Envelope, TItem>> GetComparer()

Returns

Type	Description
IComparer<IBoundable<Envelope, TItem>>

Overrides

NetTopologySuite.Index.Strtree.AbstractSTRtree<NetTopologySuite.Geometries.Envelope, TItem>.GetComparer()

Insert(Envelope, TItem)

Inserts an item having the given bounds into the tree.

Declaration

public void Insert(Envelope itemEnv, TItem item)

Parameters

Type	Name	Description
Envelope	itemEnv
TItem	item

IsWithinDistance(STRtree<TItem>, IItemDistance<Envelope, TItem>, Double)

Tests whether some two items from this tree and another tree lie within a given distance. IItemDistance<T, TItem> is used as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

Declaration

public bool IsWithinDistance(STRtree<TItem> tree, IItemDistance<Envelope, TItem> itemDist, double maxDistance)

Parameters

Type	Name	Description
STRtree<TItem>	tree	Another tree
IItemDistance<Envelope, TItem>	itemDist	A distance metric applicable to the items in the trees
Double	maxDistance	The distance limit for the search

Returns

Type	Description
Boolean	true if there are items within the distance

NearestNeighbour(Envelope, TItem, IItemDistance<Envelope, TItem>)

Finds the item in this tree which is nearest to the given item, using IItemDistance<T, TItem> as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

The query item does not have to be contained in the tree, but it does have to be compatible with the itemDist distance metric.

Declaration

public TItem NearestNeighbour(Envelope env, TItem item, IItemDistance<Envelope, TItem> itemDist)

Parameters

Type	Name	Description
Envelope	env	The envelope of the query item
TItem	item	The item to find the nearest neighbour of
IItemDistance<Envelope, TItem>	itemDist	A distance metric applicable to the items in this tree and the query item

Returns

Type	Description
TItem	The nearest item in this tree or null if the tree is empty

NearestNeighbour(Envelope, TItem, IItemDistance<Envelope, TItem>, Int32)

Finds up to k items in this tree which are the top k nearest neighbors to the given item, using itemDist as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search. This method implements the KNN algorithm described in the following paper:

Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. "Nearest neighbor queries." ACM sigmod record. Vol. 24. No. 2. ACM, 1995.

The query item does not have to be contained in the tree, but it does have to be compatible with the itemDist distance metric.

If the tree size is smaller than k fewer items will be returned. If the tree is empty an array of size 0 is returned.

Declaration

public TItem[] NearestNeighbour(Envelope env, TItem item, IItemDistance<Envelope, TItem> itemDist, int k)

Parameters

Type	Name	Description
Envelope	env	The envelope of the query item
TItem	item	The item to find the nearest neighbours of
IItemDistance<Envelope, TItem>	itemDist	A distance metric applicable to the items in this tree and the query item
Int32	k	The maximum number of nearest items to search for

Returns

Type	Description
TItem[]	An array of the nearest items found (with length between 0 and k)

NearestNeighbour(IItemDistance<Envelope, TItem>)

Finds the two nearest items in the tree, using IItemDistance<T, TItem> as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

If the tree is empty, the return value is null. If the tree contains only one item, the return value is a pair containing that item. If it is required to find only pairs of distinct items, the IItemDistance<T, TItem> function must be anti-reflexive.

Declaration

public TItem[] NearestNeighbour(IItemDistance<Envelope, TItem> itemDist)

Parameters

Type	Name	Description
IItemDistance<Envelope, TItem>	itemDist	A distance metric applicable to the items in this tree

Returns

Type	Description
TItem[]	The pair of the nearest items or null if the tree is empty

NearestNeighbour(STRtree<TItem>, IItemDistance<Envelope, TItem>)

Finds the two nearest items from this tree and another tree, using IItemDistance<T, TItem> as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search. The result value is a pair of items, the first from this tree and the second from the argument tree.

Declaration

public TItem[] NearestNeighbour(STRtree<TItem> tree, IItemDistance<Envelope, TItem> itemDist)

Parameters

Type	Name	Description
STRtree<TItem>	tree	Another tree
IItemDistance<Envelope, TItem>	itemDist	A distance metric applicable to the items in the trees

Returns

Type	Description
TItem[]	The pair of the nearest items, one from each tree or null if no pair of distinct items can be found.

Query(Envelope)

Returns items whose bounds intersect the given envelope.

Declaration

public IList<TItem> Query(Envelope searchEnv)

Parameters

Type	Name	Description
Envelope	searchEnv

Returns

Type	Description
IList<TItem>

Query(Envelope, IItemVisitor<TItem>)

Returns items whose bounds intersect the given envelope.

Declaration

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

Parameters

Type	Name	Description
Envelope	searchEnv
IItemVisitor<TItem>	visitor

Remove(Envelope, TItem)

Removes a single item from the tree.

Declaration

public bool Remove(Envelope itemEnv, TItem item)

Parameters

Type	Name	Description
Envelope	itemEnv	The Envelope of the item to remove.
TItem	item	The item to remove.

Returns

Type	Description
Boolean	true if the item was found.

VerticalSlices(IList<IBoundable<Envelope, TItem>>, Int32)

Declaration

protected IList<IBoundable<Envelope, TItem>>[] VerticalSlices(IList<IBoundable<Envelope, TItem>> childBoundables, int sliceCount)

Parameters

Type	Name	Description
IList<IBoundable<Envelope, TItem>>	childBoundables	Must be sorted by the x-value of the envelope midpoints.
Int32	sliceCount

Returns

Type	Description
IList<IBoundable<Envelope, TItem>>[]

Implements

ISpatialIndex<T>