Class Bintree<T>

An BinTree (or "Binary Interval Tree") is a 1-dimensional version of a quadtree. It indexes 1-dimensional intervals (which may be the projection of 2-D objects on an axis). It supports range searching (where the range may be a single point).

Inheritance

object

Bintree<T>

Bintree

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: NetTopologySuite.Index.Bintree

Assembly: NetTopologySuite.dll

Syntax

public class Bintree<T>

Type Parameters

Name	Description
T

Remarks

This structure is dynamic - new items can be added at any time, and it will support deletion of items (although this is not currently implemented).

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

This index is different to the Interval Tree of Edelsbrunner or the Segment Tree of Bentley.

Constructors

Bintree()

Declaration

public Bintree()

Properties

Count

Declaration

public int Count { get; }

Property Value

Type	Description
int

Depth

Declaration

public int Depth { get; }

Property Value

Type	Description
int

NodeSize

Compute the total number of nodes in the tree.

Declaration

public int NodeSize { get; }

Property Value

Type	Description
int	The number of nodes in the tree.

Methods

EnsureExtent(Interval, double)

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

Declaration

public static Interval EnsureExtent(Interval itemInterval, double minExtent)

Parameters

Type	Name	Description
Interval	itemInterval
double	minExtent

Returns

Type	Description
Interval

GetEnumerator()

Declaration

public IEnumerator<T> GetEnumerator()

Returns

Type	Description
IEnumerator<T>

Insert(Interval, T)

Declaration

public void Insert(Interval itemInterval, T item)

Parameters

Type	Name	Description
Interval	itemInterval
T	item

Query(Interval)

Queries the tree to find all candidate items which may overlap the query interval. If the query interval is null, all items in the tree are found. min and max may be the same value.

Declaration

public IList<T> Query(Interval interval)

Parameters

Type	Name	Description
Interval	interval	The interval to query for or null

Returns

Type	Description
IList<T>

Query(Interval, ICollection<T>)

Adds items in the tree which potentially overlap the query interval to the given collection. If the query interval is null, add all items in the tree.

Declaration

public void Query(Interval interval, ICollection<T> foundItems)

Parameters

Type	Name	Description
Interval	interval	A query interval, or null
ICollection<T>	foundItems	The candidate items found

Query(double)

Declaration

public IList<T> Query(double x)

Parameters

Type	Name	Description
double	x

Returns

Type	Description
IList<T>

Remove(Interval, T)

Removes a single item from the tree.

Declaration

public bool Remove(Interval itemInterval, T item)

Parameters

Type	Name	Description
Interval	itemInterval	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)