Overview | Package | Class | Tree | Deprecated | Index | Help
| JTS Topology Suite version 1.13
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## com.vividsolutions.jts.index.strtree
Class STRtree

    java.lang.Object
      com.vividsolutions.jts.index.strtree.AbstractSTRtree
          com.vividsolutions.jts.index.strtree.STRtree

All Implemented Interfaces:
  SpatialIndex, java.io.Serializable

    public class STRtree

extends AbstractSTRtree
implements SpatialIndex, java.io.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.

Version:
  1.7
See Also:
  Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree
`AbstractSTRtree.IntersectsOp`

Field Summary

Fields inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree
`root`

Constructor Summary
`STRtree()` Constructs an STRtree with the default node capacity.
`STRtree(int nodeCapacity)` Constructs an STRtree with the given maximum number of child nodes that a node may have.

Method Summary
`protected AbstractNode` | `createNode(int level)`
`protected java.util.List` | `createParentBoundables(java.util.List childBoundables, int newLevel)` Creates the parent level for the given child level.
`protected java.util.List` | `createParentBoundablesFromVerticalSlice(java.util.List childBoundables, int newLevel)`
`int` | `depth()` Returns the number of items in the tree.
`protected java.util.Comparator` | `getComparator()`
`protected AbstractSTRtree.IntersectsOp` | `getIntersectsOp()`
`void` | `insert(Envelope itemEnv, java.lang.Object item)` Inserts an item having the given bounds into the tree.
`java.lang.Object` | `nearestNeighbour(Envelope env, java.lang.Object item, ItemDistance itemDist)` Finds the item in this tree which is nearest to the given `Object`, using `ItemDistance` as the distance metric.
`java.lang.Object[]` | `nearestNeighbour(ItemDistance itemDist)` Finds the two nearest items in the tree, using `ItemDistance` as the distance metric.
`java.lang.Object[]` | `nearestNeighbour(STRtree tree, ItemDistance itemDist)` Finds the two nearest items from this tree and another tree, using `ItemDistance` as the distance metric.
`java.util.List` | `query(Envelope searchEnv)` Returns items whose bounds intersect the given envelope.
`void` | `query(Envelope searchEnv, ItemVisitor visitor)` Returns items whose bounds intersect the given envelope.
`boolean` | `remove(Envelope itemEnv, java.lang.Object item)` Removes a single item from the tree.
`int` | `size()` Returns the number of items in the tree.
`protected java.util.List[]` | `verticalSlices(java.util.List childBoundables, int sliceCount)`

Methods inherited from class com.vividsolutions.jts.index.strtree.AbstractSTRtree
`boundablesAtLevel, build, compareDoubles, depth, getNodeCapacity, getRoot, insert, isEmpty, itemsTree, lastNode, query, query, remove, size`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### 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 Detail

### createParentBoundables

    protected java.util.List createParentBoundables(java.util.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`

### createParentBoundablesFromVerticalSlice

    protected java.util.List createParentBoundablesFromVerticalSlice(java.util.List childBoundables,
                                                                     int newLevel)

### verticalSlices

    protected java.util.List[] verticalSlices(java.util.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:
    `AbstractSTRtree.IntersectsOp`

### insert

    public void insert(Envelope itemEnv,
                       java.lang.Object item)

  Inserts an item having the given bounds into the tree.

  Specified by:
    `insert` in interface `SpatialIndex`

### query

    public java.util.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,
                          java.lang.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 java.util.Comparator getComparator()

  Specified by:
    `getComparator` in class `AbstractSTRtree`

### nearestNeighbour

    public java.lang.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 java.lang.Object nearestNeighbour(Envelope env,
                                             java.lang.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 java.lang.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

Overview | Package | Class | Tree | Deprecated | Index | Help
| JTS Topology Suite version 1.13
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD