geos::index::quadtree::Quadtree Class Reference

A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of spatial objects need to be indexed they can be represented by their envelopes. More...

#include <Quadtree.h>

Inheritance diagram for geos::index::quadtree::Quadtree:

Public Member Functions
	Quadtree ()
	Constructs a Quadtree with zero items.
std::size_t	depth ()
	Returns the number of levels in the tree.
std::size_t	size ()
	Returns the number of items in the tree.
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 * > &ret) override
	Queries the tree and returns items which may lie in the given search envelope. More...
void	query (const geom::Envelope *searchEnv, ItemVisitor &visitor) override
	Queries the tree and visits items which may lie in the given search envelope. More...
bool	remove (const geom::Envelope *itemEnv, void *item) override
std::vector< void * > *	queryAll ()
	Return a list of all items in the Quadtree.
std::string	toString () const
	Quadtree (const Quadtree &)=delete
Quadtree &	operator= (const Quadtree &)=delete
	Quadtree (Quadtree &&other) noexcept
Quadtree &	operator= (Quadtree &&other) noexcept

Static Public Member Functions
static geom::Envelope *	ensureExtent (const geom::Envelope *itemEnv, double minExtent)
	Ensure that the envelope for the inserted item has non-zero extents. More...

Detailed Description

A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of spatial objects need to be indexed they can be represented by their envelopes.

The quadtree structure is used to provide a primary filter for range rectangle queries. The query() method returns a list of all objects which may intersect the query rectangle. Note that it may return objects which do not in fact intersect. A secondary filter is required to test for exact intersection. Of course, this secondary filter may consist of other tests besides intersection, such as testing other kinds of spatial relationships.

This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accommodate any extent of dataset.

This data structure is also known as an MX-CIF quadtree following the usage of Samet and others.

Constructor & Destructor Documentation

Quadtree()

geos::index::quadtree::Quadtree::Quadtree ( const Quadtree &  )

delete

Disable copy construction and assignment. Apparently needed to make this class compile under MSVC. (See https://stackoverflow.com/q/29565299)

Member Function Documentation

ensureExtent()

static geom::Envelope* geos::index::quadtree::Quadtree::ensureExtent ( const geom::Envelope *  itemEnv, double  minExtent  )

static

Ensure that the envelope for the inserted item has non-zero extents.

Use the current minExtent to pad the envelope, if necessary. Can return a new Envelope or the given one (casted to non-const).

insert()

void geos::index::quadtree::Quadtree::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.

query() [1/2]

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

inlineoverridevirtual

Queries the tree and visits items which may lie in the given search envelope.

Precisely, the items that are visited are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be visited as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not visited - thus providing improved performance over a simple linear scan.

Parameters

searchEnv	the envelope of the desired query area.
visitor	a visitor object which is passed the visited items

Implements geos::index::SpatialIndex.

query() [2/2]

void geos::index::quadtree::Quadtree::query ( const geom::Envelope *  searchEnv, std::vector< void * > &  ret  )

overridevirtual

Queries the tree and returns items which may lie in the given search envelope.

Precisely, the items that are returned are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be returned as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not returned - thus providing improved performance over a simple linear scan.

Parameters

searchEnv	the envelope of the desired query area.
ret	a vector where items which may intersect the search envelope are pushed

Implements geos::index::SpatialIndex.

remove()

bool geos::index::quadtree::Quadtree::remove ( const geom::Envelope *  itemEnv, void *  item  )

overridevirtual

Removes a single item from the tree.

Parameters

itemEnv	the Envelope of the item to be removed
item	the item to remove

Returns

true if the item was found (and thus removed)

Implements geos::index::SpatialIndex.

---

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

• Quadtree.h