GEOS 3.13.1
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)
TemplateSTRtreeImploperator= (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

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: