Class AbstractSTRtree

java.lang.Object
org.locationtech.jts.index.strtree.AbstractSTRtree
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
SIRtree, STRtree

public abstract class AbstractSTRtree extends Object implements Serializable
Base class for STRtree and SIRtree. STR-packed R-trees are described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

This implementation is based on Boundables rather than AbstractNodes, because the STR algorithm operates on both nodes and data, both of which are treated as Boundables.

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

Version:
1.7
See Also:
  • Field Details

  • Constructor Details

    • AbstractSTRtree

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

      public AbstractSTRtree(int nodeCapacity)
      Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have
      Parameters:
      nodeCapacity - the maximum number of child nodes in a node
    • AbstractSTRtree

      public AbstractSTRtree(int nodeCapacity, AbstractNode root)
      Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and the root node
      Parameters:
      nodeCapacity - the maximum number of child nodes in a node
      root - the root node that links to all other nodes in the tree
    • AbstractSTRtree

      public AbstractSTRtree(int nodeCapacity, ArrayList itemBoundables)
      Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have, and all leaf nodes in the tree
      Parameters:
      nodeCapacity - the maximum number of child nodes in a node
      itemBoundables - the list of leaf nodes in the tree
  • Method Details

    • build

      public void build()
      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.
    • createNode

      protected abstract AbstractNode createNode(int level)
    • createParentBoundables

      protected List createParentBoundables(List childBoundables, int newLevel)
      Sorts the childBoundables then divides them into groups of size M, where M is the node capacity.
    • lastNode

      protected AbstractNode lastNode(List nodes)
    • compareDoubles

      protected static int compareDoubles(double a, double b)
    • getRoot

      public AbstractNode getRoot()
      Gets the root node of the tree.
      Returns:
      the root node
    • getNodeCapacity

      public int getNodeCapacity()
      Returns the maximum number of child nodes that a node may have.
      Returns:
      the node capacity
    • isEmpty

      public boolean isEmpty()
      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.
      Returns:
      true if the index does not contain any items
    • size

      protected int size()
    • size

      protected int size(AbstractNode node)
    • depth

      protected int depth()
    • depth

      protected int depth(AbstractNode node)
    • insert

      protected void insert(Object bounds, Object item)
    • query

      protected List query(Object searchBounds)
      Also builds the tree, if necessary.
    • query

      protected void query(Object searchBounds, ItemVisitor visitor)
      Also builds the tree, if necessary.
    • getIntersectsOp

      protected abstract AbstractSTRtree.IntersectsOp getIntersectsOp()
      Returns:
      a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
      See Also:
    • itemsTree

      public List itemsTree()
      Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree.

      The returned Lists contain either Object items, or Lists which correspond to subtrees of the tree Subtrees which do not contain any items are not included.

      Builds the tree if necessary.

      Returns:
      a List of items and/or Lists
    • remove

      protected boolean remove(Object searchBounds, Object item)
      Removes an item from the tree. (Builds the tree, if necessary.)
    • boundablesAtLevel

      protected List boundablesAtLevel(int level)
    • getComparator

      protected abstract Comparator getComparator()