Overview | Package | Class | Tree | Deprecated | Index | Help
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

public class STRtree
extends AbstractSTRtree
implements SpatialIndex

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

Nested Class Summary

Nested classes 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.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, 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`

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