Class STRtree

java.lang.Object
org.locationtech.jts.index.strtree.AbstractSTRtree
org.locationtech.jts.index.strtree.STRtree
All Implemented Interfaces:
Serializable, SpatialIndex

public class STRtree extends AbstractSTRtree implements SpatialIndex, Serializable
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.

This class is thread-safe. Building the tree is synchronized, and querying is stateless.

Version:
1.7
See Also:
  • Field Details

  • Constructor Details

    • STRtree

      public STRtree()
      Constructs an STRtree with the default node capacity.
    • STRtree

      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.

  • Method Details

    • centreX

      private static double centreX(Envelope e)
    • centreY

      private static double centreY(Envelope e)
    • avg

      private static double avg(double a, double b)
    • createParentBoundables

      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.
      Overrides:
      createParentBoundables in class AbstractSTRtree
    • createParentBoundablesFromVerticalSlices

      private List createParentBoundablesFromVerticalSlices(List[] verticalSlices, int newLevel)
    • createParentBoundablesFromVerticalSlice

      protected List createParentBoundablesFromVerticalSlice(List childBoundables, int newLevel)
    • verticalSlices

      protected List[] verticalSlices(List childBoundables, int sliceCount)
      Parameters:
      childBoundables - Must be sorted by the x-value of the envelope midpoints
    • createNode

      protected AbstractNode createNode(int level)
      Specified by:
      createNode in class AbstractSTRtree
    • getIntersectsOp

      protected AbstractSTRtree.IntersectsOp getIntersectsOp()
      Specified by:
      getIntersectsOp in class AbstractSTRtree
      Returns:
      a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
      See Also:
    • insert

      public void insert(Envelope itemEnv, Object item)
      Inserts an item having the given bounds into the tree.
      Specified by:
      insert in interface SpatialIndex
    • query

      public List query(Envelope searchEnv)
      Returns items whose bounds intersect the given envelope.
      Specified by:
      query in interface SpatialIndex
      Parameters:
      searchEnv - the envelope to query for
      Returns:
      a list of the items found by the query
    • query

      public void query(Envelope searchEnv, ItemVisitor visitor)
      Returns items whose bounds intersect the given envelope.
      Specified by:
      query in interface SpatialIndex
      Parameters:
      searchEnv - the envelope to query for
      visitor - a visitor object to apply to the items found
    • remove

      public boolean remove(Envelope itemEnv, Object item)
      Removes a single item from the tree.
      Specified by:
      remove in interface SpatialIndex
      Parameters:
      itemEnv - the Envelope of the item to remove
      item - the item to remove
      Returns:
      true if the item was found
    • size

      public int size()
      Returns the number of items in the tree.
      Overrides:
      size in class AbstractSTRtree
      Returns:
      the number of items in the tree
    • depth

      public int depth()
      Returns the number of items in the tree.
      Overrides:
      depth in class AbstractSTRtree
      Returns:
      the number of items in the tree
    • getComparator

      protected Comparator getComparator()
      Specified by:
      getComparator in class AbstractSTRtree
    • nearestNeighbour

      public Object[] nearestNeighbour(ItemDistance itemDist)
      Finds the two nearest items in the tree, using ItemDistance as the distance metric. A Branch-and-Bound tree traversal algorithm is used to provide an efficient search.
      Parameters:
      itemDist - a distance metric applicable to the items in this tree
      Returns:
      the pair of the nearest items
    • nearestNeighbour

      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 - the envelope of the query item
      item - the item to find the nearest neighbour of
      itemDist - a distance metric applicable to the items in this tree and the query item
      k - the K nearest items in kNearestNeighbour
      Returns:
      the K nearest items in this tree
    • nearestNeighbour

      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 - the envelope of the query item
      item - the item to find the nearest neighbour of
      itemDist - a distance metric applicable to the items in this tree and the query item
      Returns:
      the nearest item in this tree
    • nearestNeighbour

      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 - another tree
      itemDist - a distance metric applicable to the items in the trees
      Returns:
      the pair of the nearest items, one from each tree
    • nearestNeighbour

      private Object[] nearestNeighbour(BoundablePair initBndPair)
    • nearestNeighbour

      private Object[] nearestNeighbour(BoundablePair initBndPair, int k)
    • nearestNeighbour

      private Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance)
    • nearestNeighbour

      private Object[] nearestNeighbour(BoundablePair initBndPair, double maxDistance, int k)
    • getItems

      private static Object[] getItems(PriorityQueue<BoundablePair> kNearestNeighbors)