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>

Inherited by geos::index::strtree::TemplateSTRtree< SegmentView, index::strtree::IntervalTraits >, geos::index::strtree::TemplateSTRtree< const FacetSequence * >, geos::index::strtree::TemplateSTRtree< const geos::index::chain::MonotoneChain * >, geos::index::strtree::TemplateSTRtree< const geos::geom::LinearRing * >, and geos::index::strtree::TemplateSTRtree< geos::operation::polygonize::EdgeRing * >.

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

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 geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits >::built().

Referenced by geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits >::getRoot(), and geos::index::strtree::TemplateSTRtreeImpl< ItemType, BoundsTraits >::items().

---

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

• TemplateSTRtree.h