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:

Collaboration diagram for geos::index::strtree::STRtree:

Classes
class	STRIntersectsOp

Public Member Functions
	~STRtree () override=default

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

virtual	~AbstractSTRtree ()

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

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

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

Static Public Member Functions
static double	avg (double a, double b)

static double	centreY (const geom::Envelope *e)

Protected Member Functions
AbstractNode *	createNode (int level) override

IntersectsOp *	getIntersectsOp () override

Protected Member Functions inherited from geos::index::strtree::AbstractSTRtree
virtual AbstractNode *	lastNode (BoundableList *nodeList)

virtual AbstractNode *	getRoot ()

virtual void	insert (const void bounds, void item)
	Also builds the tree, if necessary. More...

void	query (const void searchBounds, std::vector< void > &foundItems)
	Also builds the tree, if necessary. More...

void	query (const void *searchBounds, ItemVisitor &visitor)
	Also builds the tree, if necessary. More...

void	query (const void *searchBounds, const AbstractNode &node, ItemVisitor &visitor)

bool	remove (const void itemEnv, void item)
	Also builds the tree, if necessary. More...

std::unique_ptr< BoundableList >	boundablesAtLevel (int level)

Private Member Functions
std::unique_ptr< BoundableList >	createParentBoundables (BoundableList *childBoundables, int newLevel) override

std::unique_ptr< BoundableList >	createParentBoundablesFromVerticalSlices (std::vector< BoundableList * > *verticalSlices, int newLevel)

std::unique_ptr< BoundableList >	sortBoundablesY (const BoundableList *input)

std::unique_ptr< BoundableList >	sortBoundablesX (const BoundableList *input)

std::unique_ptr< BoundableList >	createParentBoundablesFromVerticalSlice (BoundableList *childBoundables, int newLevel)

std::vector< BoundableList * > *	verticalSlices (BoundableList *childBoundables, size_t sliceCount)

bool	isWithinDistance (BoundablePair *initBndPair, double maxDistance)

Private Attributes
STRIntersectsOp	intersectsOp

Additional Inherited Members
Protected Attributes inherited from geos::index::strtree::AbstractSTRtree
AbstractNode *	root

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.

Definition at line 64 of file STRtree.h.

Constructor & Destructor Documentation

geos::index::strtree::STRtree::~STRtree ( )

overridedefault

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

static double geos::index::strtree::STRtree::avg	(	double	a,
		double	b
	)

inlinestatic

Definition at line 131 of file STRtree.h.

Referenced by centreY().

Here is the caller graph for this function:

static double geos::index::strtree::STRtree::centreY ( const geom::Envelope * e )

inlinestatic

Definition at line 137 of file STRtree.h.

References avg(), geos::geom::Envelope::getMaxY(), and geos::geom::Envelope::getMinY().

Here is the call graph for this function:

AbstractNode* geos::index::strtree::STRtree::createNode ( int level )

overrideprotectedvirtual

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

std::unique_ptr<BoundableList> geos::index::strtree::STRtree::createParentBoundables	(	BoundableList *	childBoundables,
		int	newLevel
	)

overrideprivatevirtual

Creates the parent level for the given child level. First, orders the items by the x-values of the midpoints, and groups them into vertical slices. For each slice, orders the items by the y-values of the midpoints, and group them into runs of size M (the node capacity). For each run, creates a new (parent) node.

Reimplemented from geos::index::strtree::AbstractSTRtree.

std::unique_ptr<BoundableList> geos::index::strtree::STRtree::createParentBoundablesFromVerticalSlice	(	BoundableList *	childBoundables,
		int	newLevel
	)

private

std::unique_ptr<BoundableList> geos::index::strtree::STRtree::createParentBoundablesFromVerticalSlices	(	std::vector< BoundableList * > *	verticalSlices,
		int	newLevel
	)

private

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.

Definition at line 111 of file STRtree.h.

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

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::STRtree::isWithinDistance	(	BoundablePair *	initBndPair,
		double	maxDistance
	)

private

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

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

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

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

std::pair<const void*, const void*> geos::index::strtree::STRtree::nearestNeighbour ( BoundablePair * initBndPair )

std::pair<const void, const void> geos::index::strtree::STRtree::nearestNeighbour	(	BoundablePair *	initBndPair,
		double	maxDistance
	)

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

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.

Definition at line 143 of file STRtree.h.

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

Here is the call graph for this function:

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

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

Implements geos::index::SpatialIndex.

Definition at line 149 of file STRtree.h.

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

Here is the call graph for this function:

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

inlineoverridevirtual

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.

Definition at line 161 of file STRtree.h.

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

Here is the call graph for this function:

std::unique_ptr<BoundableList> geos::index::strtree::STRtree::sortBoundablesX ( const BoundableList * input )

private

std::unique_ptr<BoundableList> geos::index::strtree::STRtree::sortBoundablesY ( const BoundableList * input )

private

std::vector<BoundableList> geos::index::strtree::STRtree::verticalSlices	(	BoundableList *	childBoundables,
		size_t	sliceCount
	)

private

Parameters

childBoundables Must be sorted by the x-value of the envelope midpoints

Returns

Member Data Documentation

STRIntersectsOp geos::index::strtree::STRtree::intersectsOp

private

Definition at line 86 of file STRtree.h.

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

STRtree.h

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation