Spatial Index
Spatial indexes are used to organize a collection of spatial objects in the ways that spatial queries can be optimized. There are many spatial index methods available; for example, Quadtree, R‑tree, X‑tree, and kd‑tree. In JADE .NET, R‑tree is chosen as the spatial index method.
R-tree is a tree data structure similar to B‑tree, but is used for indexing multi-dimensional information. The R in R‑tree stands for rectangle, indicating the shape R‑tree uses to split space. For more details about R‑tree and how it works, see the following Web sites.
Since R‑trees deal only with rectangles and different geometries may have the same bounding rectangle, searching an R‑tree cannot always give you an accurate answer. For example, if you are looking for geometries in a R‑tree that are intersecting with the search region in the following diagram, you end up with two geometries: both the blue one and the green one.
To obtain the accurate answer, you then need a second level of filtering concerning only the actual geometries, not their bounding rectangles.
However, this second-level filtering could be a much more computational-intensive process, especially when the actual shape of a geometry is complex. Therefore, use R‑tree to narrow down the number of geometries before passing them to the second-level filter.
When you are interacting with JADE .NET’s R‑tree APIs, you do not have to worry about this two-level filtering process, as it is automatically handled for you.
JADE .NET provides the following classes that enable you to work with R‑trees.
JoobRTree is an abstract class encapsulating the implementation of the R-tree algorithm in JADE .NET. It exposes a series of search methods that enable you to find required IMultiDimensionalObjects. Be aware that R-tree can handle multi‑dimensional data that may or may not reside in the spatial domain. JoobRTree, as well as MemberKeyRTree and ExtKeyRTree, are therefore generic types and expect you to specify the type parameters when you create subclasses.
In addition to the normal collection methods such as Add and Remove, JoobRTree contains a list of search methods for searching geometries spatially. Currently, JADE .NET supports eight spatial relationships: contain, within, disjoint, intersect, touch, cross, overlap, and equal.
To perform a spatial search, you can call the corresponding search method such as ContainSearch or IntersectSearch, or you can call the generic Search method with a relationship parameter; for example:
var rtree = // new ...
rtree.Add(new SpatialObject { Geometry = new JoobGeometry("...") });
rtree.Add(new SpatialObject { Geometry = new JoobGeometry("...") });
...
var searchRegion = new JoobGeometry("POLYGON ((...))");
var results = rtree.IntersectSearch(searchRegion);
// or
results = rtree.Search(searchRegion, MultiDimensionalObjectRelationship.Intersect);
MemberKeyRTree is an abstract subclass of JoobRTree. Similar to a MemberKeyDictionary, objects stored in a MemberKeyRTree are keyed using their own properties. However, there can be a single key only for a MemberKeyRTree, and the key must be of type IMultiDimensionalObject.
ExtKeyRTree is also an abstract subclass of JoobRTree. Each ExtKeyRTree can also have only a single key of type IMultiDimensionalObject.
SpatialRTree is a concrete subclass of ExtKeyRTree, with a key type predefined to JoobGeometry.
When you create a subclass from JoobRTree or one of its subclasses, you automatically benefit from all of the advantages provided by the JADE collection implementation; for example, inverse maintenance and distributed processing.
