Table of Contents

Class SpatialIndex<T>

Namespace
SpatialNET
Assembly
SpatialNET.Extensions.dll

A static, bulk-loaded spatial index over envelopes with a payload (ADR 0014). The tree is packed once with the Sort-Tile-Recursive (STR) method and never changes afterwards; to reflect changes, build a new index.

public sealed class SpatialIndex<T>

Type Parameters

T

The payload, for example a geometry or an id.

Inheritance

Inherited Members

Extension Methods

Remarks

The index works on envelopes only. A query returns the items whose envelope touches or overlaps the query envelope (closed intervals); an exact test on the real geometry is up to the caller.

Thread-safe: after construction the instance is immutable and every query uses only local state, so any number of threads may query the same instance.

Constructors

SpatialIndex(IEnumerable<(Envelope2D Envelope, T Item)>, int)

Builds the index. The input is copied (snapshot, ADR 0013); later changes have no effect.

public SpatialIndex(IEnumerable<(Envelope2D Envelope, T Item)> items, int nodeCapacity = 16)

Parameters

items IEnumerable<(Envelope2D Envelope, T Item)>

The envelopes with their payload. Items with an empty envelope are skipped.

nodeCapacity int

The maximum number of children per node, at least 2.

Exceptions

ArgumentNullException

items is null.

ArgumentOutOfRangeException

nodeCapacity is below 2, or an envelope is invalid (partly NaN, infinite, or Min greater than Max).

Fields

DefaultNodeCapacity

The default maximum number of children per node.

public const int DefaultNodeCapacity = 16

Field Value

int

Properties

Count

The number of indexed items (items with an empty envelope are not counted).

public int Count { get; }

Property Value

int

Extent

The envelope of all indexed items; SpatialNET.Envelope2D.Empty if the index is empty.

public Envelope2D Extent { get; }

Property Value

Envelope2D

Methods

Join<TOther>(SpatialIndex<TOther>, double)

All pairs of an item of this index and an item of other whose envelopes touch or overlap (closed intervals), found by walking both trees together (ADR 0021). The envelopes of other are widened by distance for the comparison. Like Query, this is a pre-filter: the exact test on the geometries is up to the caller.

public IEnumerable<(T Left, TOther Right)> Join<TOther>(SpatialIndex<TOther> other, double distance = 0)

Parameters

other SpatialIndex<TOther>

The other index; it may be this index itself (every pair then occurs in both orders, and every item with itself).

distance double

The distance by which the envelopes of other are widened; finite and not negative.

Returns

IEnumerable<(T Left, TOther Right)>

Every pair exactly once, in no particular order; nothing if either index is empty.

Type Parameters

TOther

The payload of the other index.

Exceptions

ArgumentNullException

other is null.

ArgumentOutOfRangeException

distance is negative, NaN or infinite.

Join<TOther>(SpatialIndex<TOther>, ICollection<(T Left, TOther Right)>, double)

Like SpatialNET.SpatialIndex`1.Join``1(SpatialNET.SpatialIndex{``0},System.Double), but adds the pairs to results.

public void Join<TOther>(SpatialIndex<TOther> other, ICollection<(T Left, TOther Right)> results, double distance = 0)

Parameters

other SpatialIndex<TOther>

The other index.

results ICollection<(T Left, TOther Right)>

The collection that receives the pairs; it is not cleared first.

distance double

The distance by which the envelopes of other are widened; finite and not negative.

Type Parameters

TOther

The payload of the other index.

Exceptions

ArgumentNullException

other or results is null.

ArgumentOutOfRangeException

distance is negative, NaN or infinite.

Nearest(Coordinate, int, Func<T, Coordinate, double>?)

The k items nearest to point, ascending by distance; items at equal distance keep their input order. Fewer are returned if the index holds fewer.

public IReadOnlyList<T> Nearest(Coordinate point, int k, Func<T, Coordinate, double>? distance = null)

Parameters

point Coordinate

The query point.

k int

How many items to return, at least 1.

distance Func<T, Coordinate, double>?

The exact distance of an item to the query point. Without it, the distance from the point to the item's envelope is used (0 inside). The delegate must never return less than the envelope distance, which holds for any real distance to a geometry inside the envelope.

Returns

IReadOnlyList<T>

Exceptions

ArgumentOutOfRangeException

The point is not finite, or k is below 1.

InvalidOperationException

distance returned System.Double.NaN.

Query(Envelope2D)

The items whose envelope touches or overlaps envelope, in no particular order. An empty query envelope yields nothing.

public IEnumerable<T> Query(Envelope2D envelope)

Parameters

envelope Envelope2D

The query envelope.

Returns

IEnumerable<T>

Exceptions

ArgumentOutOfRangeException

The envelope is invalid (partly NaN, infinite, or Min greater than Max).

Query(Envelope2D, ICollection<T>)

Like SpatialNET.SpatialIndex`1.Query(SpatialNET.Envelope2D), but adds the items to results (no allocation of an enumerator).

public void Query(Envelope2D envelope, ICollection<T> results)

Parameters

envelope Envelope2D

The query envelope.

results ICollection<T>

The collection that receives the items; it is not cleared first.

Exceptions

ArgumentNullException

results is null.

ArgumentOutOfRangeException

The envelope is invalid (partly NaN, infinite, or Min greater than Max).

SelfJoin(double)

All unordered pairs of different entries of this index whose envelopes touch or overlap (ADR 0021): each pair once, never an entry with itself. Entries with equal payload are different entries and pair up. The envelopes of one side are widened by distance for the comparison.

public IEnumerable<(T First, T Second)> SelfJoin(double distance = 0)

Parameters

distance double

The distance by which the envelopes are widened; finite and not negative.

Returns

IEnumerable<(T First, T Second)>

Every pair exactly once, in no particular order and orientation.

Exceptions

ArgumentOutOfRangeException

distance is negative, NaN or infinite.