STRtree class
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, once the tree has been built (explicitly or on the first call to #query), items may not be added or removed.
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.
@version 1.7
- Inheritance
-
- Object
- AbstractSTRtree
- STRtree
- Implemented types
Constructors
- STRtree()
- Constructs an STRtree with the default node capacity.
- STRtree.withCapacity(int nodeCapacity)
- Constructs an STRtree with the given maximum number of child nodes that a node may have.
Properties
- built ↔ bool
-
getter/setter pairinherited
- hashCode → int
-
The hash code for this object.
no setterinherited
- itemBoundables ↔ List?
-
Set to null when index is built, to avoid retaining memory.
getter/setter pairinherited
- nodeCapacity ↔ int
-
getter/setter pairinherited
- root ↔ AbstractNode
-
getter/setter pairinherited
- runtimeType → Type
-
A representation of the runtime type of the object.
no setterinherited
Methods
-
boundablesAtLevel(
int level) → List -
inherited
-
boundablesAtLevelWithNode(
int level, AbstractNode top, List boundables) → void -
@param level -1 to get items
inherited
-
build(
) → void -
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.
inherited
-
createHigherLevels(
List boundablesOfALevel, int level) → AbstractNode -
Creates the levels higher than the given level
inherited
-
createNode(
int level) → AbstractNode -
override
-
createParentBoundables(
List childBoundables, int newLevel) → List -
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.
override
-
createParentBoundablesFromVerticalSlice(
List childBoundables, int newLevel) → List -
createParentBoundablesFromVerticalSlices(
List< List> verticalSlices, int newLevel) → List -
depth(
) → int -
Returns the number of items in the tree.
override
-
depthWithNode(
AbstractNode node) → int -
inherited
-
getComparator(
) → Comparator -
override
-
getIntersectsOp(
) → IntersectsOp -
@return a test for intersection between two bounds, necessary because subclasses
of AbstractSTRtree have different implementations of bounds.
@see IntersectsOp
override
-
getNodeCapacity(
) → int -
Returns the maximum number of child nodes that a node may have.
inherited
-
getRoot(
) → AbstractNode -
Gets the root node of the tree.
inherited
-
insert(
Envelope itemEnv, Object item) → void -
Inserts an item having the given bounds into the tree.
override
-
insertObj(
Object bounds, Object item) → void -
inherited
-
isEmpty(
) → bool -
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.
inherited
-
isWithinDistance(
BoundablePair initBndPair, double maxDistance) → bool - Performs a withinDistance search on the tree node pairs. This is a different search algorithm to nearest neighbour. It can utilize the {@link BoundablePair#maximumDistance()} between tree nodes to confirm if two internal nodes must have items closer than the maxDistance, and short-circuit the search.
-
isWithinDistanceWithTree(
STRtree tree, ItemDistance itemDist, double maxDistance) → bool - Tests whether some two items from this tree and another tree lie within a given distance. {@link ItemDistance} is used as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.
-
itemsTree(
) → List -
Gets a tree structure (as a nested list)
corresponding to the structure of the items and nodes in this tree.
inherited
-
itemsTreeWithNode(
AbstractNode node) → List? -
inherited
-
lastNode(
List nodes) → AbstractNode -
inherited
-
nearestNeighbour(
ItemDistance itemDist) → List< Object> ? - Finds the two nearest items in the tree, using {@link ItemDistance} as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.
-
nearestNeighbourK(
BoundablePair initBndPair, int k) → List< Object> -
nearestNeighbourKWithMaxD(
BoundablePair initBndPair, double maxDistance, int k) → List< Object> -
nearestNeighbourWithEnv(
Envelope env, Object item, ItemDistance itemDist, int k) → List< Object> - Finds k items in this tree which are the top k nearest neighbors to the given {@code item}, using {@code 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:
-
nearestNeighbourWithEnvelope(
Envelope env, Object item, ItemDistance itemDist) → Object - Finds the item in this tree which is nearest to the given {@link Object}, using {@link ItemDistance} as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.
-
nearestNeighbourWithPair(
BoundablePair initBndPair) → List< Object> ? -
nearestNeighbourWithTree(
STRtree tree, ItemDistance itemDist) → List< Object> ? - Finds the two nearest items from this tree and another tree, using {@link ItemDistance} 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.
-
noSuchMethod(
Invocation invocation) → dynamic -
Invoked when a nonexistent method or property is accessed.
inherited
-
query(
Envelope searchEnv) → List -
Returns items whose bounds intersect the given envelope.
override
-
queryInternal(
Object searchBounds, AbstractNode node, List matches) → void -
inherited
-
queryInternalWithVisitor(
Object searchBounds, AbstractNode node, ItemVisitor visitor) → void -
inherited
-
queryObj(
Object searchBounds) → List -
Also builds the tree, if necessary.
inherited
-
queryObjWithVisitor(
Object searchBounds, ItemVisitor visitor) → void -
Also builds the tree, if necessary.
inherited
-
queryWithVisitor(
Envelope searchEnv, ItemVisitor visitor) → void -
Returns items whose bounds intersect the given envelope.
override
-
remove(
Envelope itemEnv, Object item) → bool -
Removes a single item from the tree.
override
-
removeItem(
AbstractNode node, Object item) → bool -
inherited
-
removeObj(
Object searchBounds, Object item) → bool -
Removes an item from the tree.
(Builds the tree, if necessary.)
inherited
-
removeWithNode(
Object searchBounds, AbstractNode node, Object item) → bool -
inherited
-
size(
) → int -
Returns the number of items in the tree.
override
-
sizeWithNode(
AbstractNode node) → int -
inherited
-
toString(
) → String -
A string representation of this object.
inherited
-
verticalSlices(
List childBoundables, int sliceCount) → List< List> - @param childBoundables Must be sorted by the x-value of the envelope midpoints
Operators
-
operator ==(
Object other) → bool -
The equality operator.
inherited
Static Properties
- DEFAULT_NODE_CAPACITY → int
-
final
- intersectsOp ↔ IntersectsOp
-
getter/setter pair
- xComparator ↔ Comparator
-
getter/setter pair
- yComparator ↔ Comparator
-
getter/setter pair