geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits > Class Template Reference

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

`#include <TemplateSTRtree.h>`

## Public Types

using | Node = TemplateSTRNode<ItemType, BoundsTraits>
using | NodeList = std::vector<Node>
using | NodeListIterator = typename NodeList::iterator
using | BoundsType = typename BoundsTraits::BoundsType

## Public Member Functions

| TemplateSTRtreeImpl (size_t p_nodeCapacity=10)
| TemplateSTRtreeImpl (size_t p_nodeCapacity, size_t itemCapacity)
| TemplateSTRtreeImpl (const TemplateSTRtreeImpl &other)
TemplateSTRtreeImpl & | operator= (TemplateSTRtreeImpl other)
void | insert (ItemType &&item)
void | insert (const ItemType &item)
void | insert (const BoundsType &itemEnv, ItemType &&item)
void | insert (const BoundsType &itemEnv, const ItemType &item)
template<typename ItemDistance>
std::pair< ItemType, ItemType > | nearestNeighbour (ItemDistance &distance)
template<typename ItemDistance>
std::pair< ItemType, ItemType > | nearestNeighbour ()
template<typename ItemDistance>
std::pair< ItemType, ItemType > | nearestNeighbour (TemplateSTRtreeImpl< ItemType, BoundsTraits > &other, ItemDistance &distance)
template<typename ItemDistance>
std::pair< ItemType, ItemType > | nearestNeighbour (TemplateSTRtreeImpl< ItemType, BoundsTraits > &other)
template<typename ItemDistance>
ItemType | nearestNeighbour (const BoundsType &env, const ItemType &item, ItemDistance &itemDist)
template<typename ItemDistance>
ItemType | nearestNeighbour (const BoundsType &env, const ItemType &item)
template<typename ItemDistance>
bool | isWithinDistance (TemplateSTRtreeImpl< ItemType, BoundsTraits > &other, double maxDistance)
template<typename Visitor>
void | query (const BoundsType &queryEnv, Visitor &&visitor)
template<typename Visitor>
void | queryPairs (Visitor &&visitor)
void | query (const BoundsType &queryEnv, std::vector< ItemType > &results)
Items | items ()
template<typename F>
void | iterate (F &&func)
bool | remove (const BoundsType &itemEnv, const ItemType &item)
bool | built () const
const Node * | getRoot ()
void | build ()

## Protected Member Functions

void | createLeafNode (ItemType &&item, const BoundsType &env)
void | createLeafNode (const ItemType &item, const BoundsType &env)
void | createBranchNode (const Node *begin, const Node *end)
size_t | treeSize (size_t numLeafNodes)
void | createParentNodes (const NodeListIterator &begin, size_t number)
void | addParentNodesFromVerticalSlice (const NodeListIterator &begin, const NodeListIterator &end)
void | sortNodesX (const NodeListIterator &begin, const NodeListIterator &end)
void | sortNodesY (const NodeListIterator &begin, const NodeListIterator &end)
template<typename Visitor, typename std::enable_if< std::is_void< decltype(std::declval< Visitor >()(std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaf (Visitor &&visitor, const Node &node)
template<typename Visitor, typename std::enable_if< std::is_void< decltype(std::declval< Visitor >()(std::declval< ItemType >(), std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaves (Visitor &&visitor, const Node &node1, const Node &node2)
template<typename Visitor, typename std::enable_if< std::is_void< decltype(std::declval< Visitor >()(std::declval< BoundsType >(), std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaf (Visitor &&visitor, const Node &node)
template<typename Visitor, typename std::enable_if<!std::is_void< decltype(std::declval< Visitor >()(std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaf (Visitor &&visitor, const Node &node)
template<typename Visitor, typename std::enable_if<!std::is_void< decltype(std::declval< Visitor >()(std::declval< ItemType >(), std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaves (Visitor &&visitor, const Node &node1, const Node &node2)
template<typename Visitor, typename std::enable_if<!std::is_void< decltype(std::declval< Visitor >()(std::declval< BoundsType >(), std::declval< ItemType >()))>::value, std::nullptr_t, ::type = nullptr>
bool | visitLeaf (Visitor &&visitor, const Node &node)
template<typename Visitor>
bool | query (const BoundsType &queryEnv, const Node &node, Visitor &&visitor)
template<typename Visitor>
bool | queryPairs (const Node &queryNode, const Node &searchNode, Visitor &&visitor)
bool | remove (const BoundsType &queryEnv, const Node &node, const ItemType &item)
size_t | sliceCount (size_t numNodes) const
void | validateConstruction () const

## Static Protected Member Functions

static size_t | sliceCapacity (size_t numNodes, size_t numSlices)

## Protected Attributes

std::mutex | lock_
NodeList | nodes
Node * | root
size_t | nodeCapacity
size_t | numItems

## Detailed Description

template<typename ItemType, typename BoundsTraits>
class geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits >

A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For one- or 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.

A user will instantiate TemplateSTRtree instead of TemplateSTRtreeImpl; this structure is used so that TemplateSTRtree can implement the requirements of the SpatialIndex interface, which is only possible when ItemType is a pointer.

Described in: P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With Application To GIS. Morgan Kaufmann, San Francisco, 2002.

## Member Function Documentation

## build()

template<typename ItemType, typename BoundsTraits>

void geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits >::build | ( |  | ) |

inline

Build the tree if it has not already been built.

References built().

Referenced by getRoot(), and items().

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

- TemplateSTRtree.h