GEOS  3.8.0dev
Public Member Functions | Static Public Member Functions | Protected Member Functions | List of all members
geos::index::strtree::STRtree Class Reference

A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatial data. More...

#include <STRtree.h>

Inheritance diagram for geos::index::strtree::STRtree:
geos::index::strtree::AbstractSTRtree geos::index::SpatialIndex

Public Member Functions

 STRtree (std::size_t nodeCapacity=10)
 
void insert (const geom::Envelope *itemEnv, void *item) override
 Adds a spatial item with an extent specified by the given Envelope to the index. More...
 
void query (const geom::Envelope *searchEnv, std::vector< void * > &matches) override
 Queries the index for all items whose extents intersect the given search Envelope. More...
 
void query (const geom::Envelope *searchEnv, ItemVisitor &visitor) override
 Queries the index for all items whose extents intersect the given search Envelope and applies an ItemVisitor to them. More...
 
std::pair< const void *, const
void * > 
nearestNeighbour (ItemDistance *itemDist)
 
const void * nearestNeighbour (const geom::Envelope *env, const void *item, ItemDistance *itemDist)
 
std::pair< const void *, const
void * > 
nearestNeighbour (STRtree *tree, ItemDistance *itemDist)
 
std::pair< const void *, const
void * > 
nearestNeighbour (BoundablePair *initBndPair)
 
std::pair< const void *, const
void * > 
nearestNeighbour (BoundablePair *initBndPair, double maxDistance)
 
bool remove (const geom::Envelope *itemEnv, void *item) override
 Removes a single item from the tree. More...
 
bool isWithinDistance (STRtree *tree, ItemDistance *itemDist, double maxDistance)
 
- Public Member Functions inherited from geos::index::strtree::AbstractSTRtree
 AbstractSTRtree (std::size_t newNodeCapacity)
 Constructs an AbstractSTRtree with the specified maximum number of child nodes that a node may have.
 
virtual 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. More...
 
virtual std::size_t getNodeCapacity ()
 Returns the maximum number of child nodes that a node may have.
 
virtual void query (const void *searchBounds, const AbstractNode *node, std::vector< void * > *matches)
 
void iterate (ItemVisitor &visitor)
 
virtual void boundablesAtLevel (int level, AbstractNode *top, BoundableList *boundables)
 
ItemsList * itemsTree ()
 Gets a tree structure (as a nested list) corresponding to the structure of the items and nodes in this tree. More...
 

Static Public Member Functions

static double avg (double a, double b)
 
static double centreY (const geom::Envelope *e)
 
- Static Public Member Functions inherited from geos::index::strtree::AbstractSTRtree
static bool compareDoubles (double a, double b)
 

Protected Member Functions

AbstractNodecreateNode (int level) override
 
IntersectsOpgetIntersectsOp () override
 
- Protected Member Functions inherited from geos::index::strtree::AbstractSTRtree
virtual AbstractNodelastNode (BoundableList *nodeList)
 
virtual AbstractNodegetRoot ()
 
virtual void insert (const void *bounds, void *item)
 Also builds the tree, if necessary.
 
void query (const void *searchBounds, std::vector< void * > &foundItems)
 Also builds the tree, if necessary.
 
void query (const void *searchBounds, ItemVisitor &visitor)
 Also builds the tree, if necessary.
 
void query (const void *searchBounds, const AbstractNode &node, ItemVisitor &visitor)
 
bool remove (const void *itemEnv, void *item)
 Also builds the tree, if necessary.
 
std::unique_ptr< BoundableListboundablesAtLevel (int level)
 

Additional Inherited Members

- Protected Attributes inherited from geos::index::strtree::AbstractSTRtree
AbstractNoderoot
 
std::vector< AbstractNode * > * nodes
 
std::size_t nodeCapacity
 

Detailed Description

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.

Constructor & Destructor Documentation

geos::index::strtree::STRtree::STRtree ( std::size_t  nodeCapacity = 10)

Constructs an STRtree with the given maximum number of child nodes that a node may have

Member Function Documentation

IntersectsOp* geos::index::strtree::STRtree::getIntersectsOp ( )
inlineoverrideprotectedvirtual
Returns
a test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have different implementations of bounds.
See also
IntersectsOp

Implements geos::index::strtree::AbstractSTRtree.

void geos::index::strtree::STRtree::insert ( const geom::Envelope itemEnv,
void *  item 
)
overridevirtual

Adds a spatial item with an extent specified by the given Envelope to the index.

Parameters
itemEnvEnvelope of the item, ownership left to caller. TODO: Reference hold by this class ?
itemOpaque item, ownership left to caller. Reference hold by this class.

Implements geos::index::SpatialIndex.

void geos::index::strtree::STRtree::query ( const geom::Envelope searchEnv,
std::vector< void * > &   
)
inlineoverridevirtual

Queries the index for all items whose extents intersect the given search Envelope.

Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.

Parameters
searchEnvthe envelope to query for
Returns
a list of the items found by the query in a newly allocated vector

Implements geos::index::SpatialIndex.

References geos::index::strtree::AbstractSTRtree::query().

void geos::index::strtree::STRtree::query ( const geom::Envelope searchEnv,
ItemVisitor visitor 
)
inlineoverridevirtual

Queries the index for all items whose extents intersect the given search Envelope and applies an ItemVisitor to them.

Note that some kinds of indexes may also return objects which do not in fact intersect the query envelope.

Parameters
searchEnvthe envelope to query for
visitora visitor object to apply to the items found

Implements geos::index::SpatialIndex.

References geos::index::strtree::AbstractSTRtree::query().

bool geos::index::strtree::STRtree::remove ( const geom::Envelope itemEnv,
void *  item 
)
inlineoverridevirtual

Removes a single item from the tree.

Parameters
itemEnvthe Envelope of the item to remove
itemthe item to remove
Returns
true if the item was found

Implements geos::index::SpatialIndex.


The documentation for this class was generated from the following file: