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

#include <SimpleSTRtree.h>

Inheritance diagram for geos::index::strtree::SimpleSTRtree:

Collaboration diagram for geos::index::strtree::SimpleSTRtree:

Public Member Functions
	SimpleSTRtree (std::size_t capacity=10)

std::size_t	getNodeCapacity () const

std::size_t	getNumLeafNodes () const

bool	getBuilt () const

SimpleSTRnode *	getRoot ()

void	insert (geom::Geometry *geom)

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	iterate (ItemVisitor &visitor)

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...

bool	remove (const geom::Envelope searchBounds, void item) override
	Removes a single item from the tree. 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 (SimpleSTRtree &tree, ItemDistance *itemDist)

bool	isWithinDistance (SimpleSTRtree &tree, ItemDistance *itemDist, double maxDistance)

Public Member Functions inherited from geos::index::SpatialIndex
virtual	~SpatialIndex ()

Public Attributes
SimpleSTRnode *	root

Private Member Functions
SimpleSTRnode *	createNode (int newLevel, const geom::Envelope itemEnv, void item)

SimpleSTRnode *	createNode (int newLevel)

void	build ()

void	query (const geom::Envelope searchEnv, const SimpleSTRnode node, ItemVisitor &visitor)

void	query (const geom::Envelope searchEnv, const SimpleSTRnode node, std::vector< void * > &matches)

	SimpleSTRtree (const SimpleSTRtree &)=delete

SimpleSTRtree &	operator= (const SimpleSTRtree &)=delete

std::vector< SimpleSTRnode * >	createHigherLevels (std::vector< SimpleSTRnode * > &nodesOfALevel, int level)

void	addParentNodesFromVerticalSlice (std::vector< SimpleSTRnode * > &verticalSlice, int newLevel, std::vector< SimpleSTRnode * > &parentNodes)

std::vector< SimpleSTRnode * >	createParentNodes (std::vector< SimpleSTRnode * > &childNodes, int newLevel)

bool	remove (const geom::Envelope searchBounds, SimpleSTRnode node, void *item)

Static Private Member Functions
static void	sortNodesY (std::vector< SimpleSTRnode * > &nodeList)

static void	sortNodesX (std::vector< SimpleSTRnode * > &nodeList)

Private Attributes
std::deque< SimpleSTRnode >	nodesQue

std::vector< SimpleSTRnode * >	nodes

std::size_t	nodeCapacity

bool	built

Friends
std::ostream &	operator<< (std::ostream &os, const SimpleSTRtree &tree)

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.

Definition at line 65 of file SimpleSTRtree.h.

Constructor & Destructor Documentation

geos::index::strtree::SimpleSTRtree::SimpleSTRtree ( const SimpleSTRtree & )

privatedelete

geos::index::strtree::SimpleSTRtree::SimpleSTRtree ( std::size_t capacity = 10 )

inline

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

Definition at line 120 of file SimpleSTRtree.h.

Member Function Documentation

void geos::index::strtree::SimpleSTRtree::addParentNodesFromVerticalSlice	(	std::vector< SimpleSTRnode * > &	verticalSlice,
		int	newLevel,
		std::vector< SimpleSTRnode * > &	parentNodes
	)

private

void geos::index::strtree::SimpleSTRtree::build ( )

private

std::vector<SimpleSTRnode*> geos::index::strtree::SimpleSTRtree::createHigherLevels	(	std::vector< SimpleSTRnode * > &	nodesOfALevel,
		int	level
	)

private

SimpleSTRnode* geos::index::strtree::SimpleSTRtree::createNode	(	int	newLevel,
		const geom::Envelope *	itemEnv,
		void *	item
	)

private

SimpleSTRnode* geos::index::strtree::SimpleSTRtree::createNode ( int newLevel )

private

std::vector<SimpleSTRnode*> geos::index::strtree::SimpleSTRtree::createParentNodes	(	std::vector< SimpleSTRnode * > &	childNodes,
		int	newLevel
	)

private

bool geos::index::strtree::SimpleSTRtree::getBuilt ( ) const

inline

Definition at line 139 of file SimpleSTRtree.h.

std::size_t geos::index::strtree::SimpleSTRtree::getNodeCapacity ( ) const

inline

Definition at line 126 of file SimpleSTRtree.h.

std::size_t geos::index::strtree::SimpleSTRtree::getNumLeafNodes ( ) const

inline

Definition at line 130 of file SimpleSTRtree.h.

References geos::index::strtree::SimpleSTRnode::getNumLeafNodes().

Here is the call graph for this function:

SimpleSTRnode* geos::index::strtree::SimpleSTRtree::getRoot ( )

inline

Definition at line 143 of file SimpleSTRtree.h.

References geos::geom::operator<<().

Here is the call graph for this function:

void geos::index::strtree::SimpleSTRtree::insert ( geom::Geometry * geom )

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

overridevirtual

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

Parameters

itemEnv	Envelope of the item, ownership left to caller. TODO: Reference hold by this class ?
item	Opaque item, ownership left to caller. Reference hold by this class.

Implements geos::index::SpatialIndex.

bool geos::index::strtree::SimpleSTRtree::isWithinDistance	(	SimpleSTRtree &	tree,
		ItemDistance *	itemDist,
		double	maxDistance
	)

void geos::index::strtree::SimpleSTRtree::iterate ( ItemVisitor & visitor )

std::pair<const void*, const void*> geos::index::strtree::SimpleSTRtree::nearestNeighbour ( ItemDistance * itemDist )

const void* geos::index::strtree::SimpleSTRtree::nearestNeighbour	(	const geom::Envelope *	env,
		const void *	item,
		ItemDistance *	itemDist
	)

std::pair<const void, const void> geos::index::strtree::SimpleSTRtree::nearestNeighbour	(	SimpleSTRtree &	tree,
		ItemDistance *	itemDist
	)

SimpleSTRtree& geos::index::strtree::SimpleSTRtree::operator= ( const SimpleSTRtree & )

privatedelete

void geos::index::strtree::SimpleSTRtree::query	(	const geom::Envelope *	searchEnv,
		const SimpleSTRnode *	node,
		ItemVisitor &	visitor
	)

private

void geos::index::strtree::SimpleSTRtree::query	(	const geom::Envelope *	searchEnv,
		const SimpleSTRnode *	node,
		std::vector< void * > &	matches
	)

private

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

overridevirtual

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

searchEnv the envelope to query for

Returns: a list of the items found by the query in a newly allocated vector

Implements geos::index::SpatialIndex.

void geos::index::strtree::SimpleSTRtree::query	(	const geom::Envelope *	searchEnv,
		ItemVisitor &	visitor
	)

overridevirtual

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

searchEnv	the envelope to query for
visitor	a visitor object to apply to the items found

Implements geos::index::SpatialIndex.

bool geos::index::strtree::SimpleSTRtree::remove	(	const geom::Envelope *	searchBounds,
		SimpleSTRnode *	node,
		void *	item
	)

private

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

overridevirtual

Removes a single item from the tree.

Parameters

itemEnv	the Envelope of the item to remove
item	the item to remove

Returns: true if the item was found

Implements geos::index::SpatialIndex.

static void geos::index::strtree::SimpleSTRtree::sortNodesX ( std::vector< SimpleSTRnode * > & nodeList )

staticprivate

static void geos::index::strtree::SimpleSTRtree::sortNodesY ( std::vector< SimpleSTRnode * > & nodeList )

staticprivate

Friends And Related Function Documentation

std::ostream& operator<<	(	std::ostream &	os,
		const SimpleSTRtree &	tree
	)

friend

Member Data Documentation

bool geos::index::strtree::SimpleSTRtree::built

private

Definition at line 74 of file SimpleSTRtree.h.

std::size_t geos::index::strtree::SimpleSTRtree::nodeCapacity

private

Definition at line 73 of file SimpleSTRtree.h.

std::vector<SimpleSTRnode*> geos::index::strtree::SimpleSTRtree::nodes

private

Definition at line 72 of file SimpleSTRtree.h.

std::deque<SimpleSTRnode> geos::index::strtree::SimpleSTRtree::nodesQue

private

Definition at line 71 of file SimpleSTRtree.h.

SimpleSTRnode* geos::index::strtree::SimpleSTRtree::root

Definition at line 114 of file SimpleSTRtree.h.

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

SimpleSTRtree.h

Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation