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.

Other

version: 1.7

public STRtree()

Constructs an STRtree with the default node capacity.

public STRtree(int nodeCapacity)

Constructs an STRtree with the given maximum number of child nodes that a node may have.

The minimum recommended capacity setting is 4.

protected List createParentBoundables(List childBoundables, int newLevel)

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.

protected List createParentBoundablesFromVerticalSlice(List childBoundables, int newLevel)

protected List[] verticalSlices(List childBoundables, int sliceCount)

Parameters:: childBoundables - childBoundables Must be sorted by the x-value of the envelope midpoints

protected AbstractNode createNode(int level)

protected IntersectsOp getIntersectsOp()

public void insert(Envelope itemEnv, Object item)

Inserts an item having the given bounds into the tree.

public List query(Envelope searchEnv)

Returns items whose bounds intersect the given envelope.

public void query(Envelope searchEnv, ItemVisitor visitor)

Returns items whose bounds intersect the given envelope.

public boolean remove(Envelope itemEnv, Object item)

Removes a single item from the tree.

Parameters:: itemEnv - itemEnv the Envelope of the item to remove; item - item the item to remove

Returns:: true if the item was found

public int size()

Returns the number of items in the tree.

Returns:: the number of items in the tree

public int depth()

Returns the number of items in the tree.

Returns:: the number of items in the tree

protected Comparator getComparator()

public Object[] nearestNeighbour(ItemDistance itemDist)

public Object nearestNeighbour(Envelope env, Object item, ItemDistance itemDist)

Finds the item in this tree which is nearest to the given Object, using ItemDistance as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

The query object does not have to be contained in the tree, but it does have to be compatible with the itemDist distance metric.

Parameters:: env - env the envelope of the query item; item - item the item to find the nearest neighbour of; itemDist - itemDist a distance metric applicable to the items in this tree and the query item

Returns:: the nearest item in this tree or null if the tree is empty

public Object[] nearestNeighbour(STRtree tree, ItemDistance itemDist)

Finds the two nearest items from this tree and another tree, using 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.

Parameters:: tree - tree another tree; itemDist - itemDist a distance metric applicable to the items in the trees

Returns:: the pair of the nearest items, one from each tree or null if no pair of distinct items can be found

public boolean isWithinDistance(STRtree tree, ItemDistance itemDist, double maxDistance)

Tests whether some two items from this tree and another tree lie within a given distance. ItemDistance is used as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.

Parameters:: tree - tree another tree; itemDist - itemDist a distance metric applicable to the items in the trees; maxDistance - maxDistance the distance limit for the search

Returns:: true if there are items within the distance

public Object[] nearestNeighbour(Envelope env, Object item, ItemDistance itemDist, int k)

Finds k items in this tree which are the top k nearest neighbors to the given item, using 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:

Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. "Nearest neighbor queries." ACM sigmod record. Vol. 24. No. 2. ACM, 1995.

The query item does not have to be contained in the tree, but it does have to be compatible with the itemDist distance metric.

Parameters:: env - env the envelope of the query item; item - item the item to find the nearest neighbour of; itemDist - itemDist a distance metric applicable to the items in this tree and the query item; k - k the K nearest items in kNearestNeighbour

Returns:: the K nearest items in this tree