Class AbstractSTRtree<T, TItem>

Namespace

NetTopologySuite.Index.Strtree

Assembly

NetTopologySuite.dll

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.

public abstract class AbstractSTRtree<T, TItem> where T : IIntersectable<T>, IExpandable<T>

Type Parameters

T

TItem

Inheritance

object

AbstractSTRtree<T, TItem>

Derived

SIRtree<TItem>

STRtree<TItem>

Inherited Members

object.GetType()

object.MemberwiseClone()

object.ToString()

object.Equals(object)

object.Equals(object, object)

object.ReferenceEquals(object, object)

object.GetHashCode()

Constructors

AbstractSTRtree(int)

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

protected AbstractSTRtree(int nodeCapacity)

Parameters

nodeCapacity int

AbstractSTRtree(int, AbstractNode<T, TItem>)

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

protected AbstractSTRtree(int nodeCapacity, AbstractNode<T, TItem> root)

Parameters

nodeCapacity int

The maximum number of child nodes in a node

root AbstractNode<T, TItem>

The root node that links to all other nodes in the tree

AbstractSTRtree(int, IList<IBoundable<T, TItem>>)

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

protected AbstractSTRtree(int nodeCapacity, IList<IBoundable<T, TItem>> itemBoundables)

Parameters

nodeCapacity int

The maximum number of child nodes in a node

itemBoundables IList<IBoundable<T, TItem>>

The list of leaf nodes in the tree

Properties

Count

Gets the number of elements in the tree

public int Count { get; }

Property Value

int

Depth

public int Depth { get; }

Property Value

int

IntersectsOp

protected abstract AbstractSTRtree<T, TItem>.IIntersectsOp IntersectsOp { get; }

Property Value

AbstractSTRtree<T, TItem>.IIntersectsOp

A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.

IsEmpty

Tests whether the index contains any items. This method does not build the index, so items can still be inserted after it has been called.

public bool IsEmpty { get; }

Property Value

bool

ItemBoundables

Gets a value indicating the boundable items that have to be included in the index

public IList<IBoundable<T, TItem>> ItemBoundables { get; }

Property Value

IList<IBoundable<T, TItem>>

A list of boundable items

NodeCapacity

Gets the maximum number of child nodes that a node may have.

public int NodeCapacity { get; }

Property Value

int

Root

Gets the root node of the tree.

public AbstractNode<T, TItem> Root { get; protected set; }

Property Value

AbstractNode<T, TItem>

Methods

BoundablesAtLevel(int)

protected IList<IBoundable<T, TItem>> BoundablesAtLevel(int level)

Parameters

level int

Returns

IList<IBoundable<T, TItem>>

Build()

Creates parent nodes, grandparent nodes, and so forth up to the root node, for the data that has been inserted into the tree. Can only be called once, and thus can be called only after all of the data has been inserted into the tree.

public void Build()

CompareDoubles(double, double)

protected static int CompareDoubles(double a, double b)

Parameters

a double

b double

Returns

int

CreateNode(int)

protected abstract AbstractNode<T, TItem> CreateNode(int level)

Parameters

level int

Returns

AbstractNode<T, TItem>

CreateParentBoundables(IList<IBoundable<T, TItem>>, int)

Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.

protected virtual IList<IBoundable<T, TItem>> CreateParentBoundables(IList<IBoundable<T, TItem>> childBoundables, int newLevel)

Parameters

childBoundables IList<IBoundable<T, TItem>>

newLevel int

Returns

IList<IBoundable<T, TItem>>

GetComparer()

protected abstract IComparer<IBoundable<T, TItem>> GetComparer()

Returns

IComparer<IBoundable<T, TItem>>

GetDepth(AbstractNode<T, TItem>)

protected int GetDepth(AbstractNode<T, TItem> node)

Parameters

node AbstractNode<T, TItem>

Returns

int

GetSize(AbstractNode<T, TItem>)

protected int GetSize(AbstractNode<T, TItem> node)

Parameters

node AbstractNode<T, TItem>

Returns

int

Insert(T, TItem)

protected void Insert(T bounds, TItem item)

Parameters

bounds T

item TItem

ItemsTree()

Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree. The returned Lists contain either Object items, or Lists which correspond to subtrees of the tree Subtrees which do not contain any items are not included. Builds the tree if necessary.

public IList<object> ItemsTree()

Returns

IList<object>

a List of items and/or Lists

LastNode(IList<IBoundable<T, TItem>>)

protected AbstractNode<T, TItem> LastNode(IList<IBoundable<T, TItem>> nodes)

Parameters

nodes IList<IBoundable<T, TItem>>

Returns

AbstractNode<T, TItem>

Query(T)

Also builds the tree, if necessary.

protected IList<TItem> Query(T searchBounds)

Parameters

searchBounds T

Returns

IList<TItem>

Query(T, IItemVisitor<TItem>)

protected void Query(T searchBounds, IItemVisitor<TItem> visitor)

Parameters

searchBounds T

visitor IItemVisitor<TItem>

Remove(T, TItem)

Removes an item from the tree. (Builds the tree, if necessary.)

protected bool Remove(T searchBounds, TItem item)

Parameters

searchBounds T

item TItem

Returns

bool