Package com.kheops.jmap.spatial.index

Class AbstractSTRtree<T>

java.lang.Object
com.kheops.jmap.spatial.index.AbstractSTRtree<T>
Direct Known Subclasses:
STRtree
public abstract class AbstractSTRtree<T> extends Object
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 just AbstractNodes, because the STR algorithm operates on both nodes and data, both of which are treated here as Boundables.

See Also:

  • Field Details

  • Constructor Details

    • AbstractSTRtree

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

  • 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<Boundable> createParentBoundables(List<Boundable> 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<Boundable> nodes)

    • compareDoubles

      protected int compareDoubles(double a, double b)

    • getRoot

      protected AbstractNode getRoot()

    • getNodeCapacity

      public int getNodeCapacity()
      Returns the maximum number of child nodes that a node may have

    • size

      protected int size()

    • size

      protected int size(AbstractNode node)

    • depth

      protected int depth()

    • depth

      protected int depth(AbstractNode node)

    • insert

      protected void insert(Rectangle bounds, T item)

    • query

      protected List<T> query(Rectangle searchBounds)
      Also builds the tree, if necessary.

    • query

      protected void query(Rectangle searchBounds, ItemVisitor<T> 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:

    • remove

      protected boolean remove(Rectangle searchBounds, T item)
      Removes an item from the tree. (Builds the tree, if necessary.)

    • boundablesAtLevel

      protected List<Boundable> boundablesAtLevel(int level)

    • getComparator

      protected abstract Comparator<Boundable> getComparator()