GEOS  3.9.1dev
Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | List of all members
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:
[legend]
Collaboration diagram for geos::index::quadtree::Quadtree:
[legend]

Public Member Functions

 Quadtree ()
 Constructs a Quadtree with zero items. More...
 
 ~Quadtree () override=default
 
int depth ()
 Returns the number of levels in the tree. More...
 
size_t size ()
 Returns the number of items in the tree. More...
 
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. More...
 
std::string toString () const
 
 Quadtree (const Quadtree &)=delete
 
Quadtreeoperator= (const Quadtree &)=delete
 
- Public Member Functions inherited from geos::index::SpatialIndex
virtual ~SpatialIndex ()
 

Static Public Member Functions

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

Private Member Functions

void collectStats (const geom::Envelope &itemEnv)
 

Private Attributes

std::vector< std::unique_ptr< geom::Envelope > > newEnvelopes
 
Root root
 
double minExtent
 

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 accomodate any extent of dataset.

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

Definition at line 71 of file Quadtree.h.

Constructor & Destructor Documentation

geos::index::quadtree::Quadtree::Quadtree ( )
inline

Constructs a Quadtree with zero items.

Definition at line 109 of file Quadtree.h.

geos::index::quadtree::Quadtree::~Quadtree ( )
overridedefault
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

void geos::index::quadtree::Quadtree::collectStats ( const geom::Envelope itemEnv)
private
int geos::index::quadtree::Quadtree::depth ( )

Returns the number of levels in the tree.

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

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
itemEnvEnvelope of the item, ownership left to caller. TODO: Reference hold by this class ?
itemOpaque item, ownership left to caller. Reference hold by this class.

Implements geos::index::SpatialIndex.

Quadtree& geos::index::quadtree::Quadtree::operator= ( const Quadtree )
delete
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
searchEnvthe envelope of the desired query area.
reta vector where items which may intersect the search envelope are pushed

Implements geos::index::SpatialIndex.

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
searchEnvthe envelope of the desired query area.
visitora visitor object which is passed the visited items

Implements geos::index::SpatialIndex.

Definition at line 162 of file Quadtree.h.

References geos::index::quadtree::NodeBase::visit().

Here is the call graph for this function:

std::vector<void*>* geos::index::quadtree::Quadtree::queryAll ( )

Return a list of all items in the Quadtree.

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

Removes a single item from the tree.

Parameters
itemEnvthe Envelope of the item to be removed
itemthe item to remove
Returns
true if the item was found (and thus removed)

Implements geos::index::SpatialIndex.

size_t geos::index::quadtree::Quadtree::size ( )

Returns the number of items in the tree.

std::string geos::index::quadtree::Quadtree::toString ( ) const

Member Data Documentation

double geos::index::quadtree::Quadtree::minExtent
private

Statistics

minExtent is the minimum envelope extent of all items inserted into the tree so far. It is used as a heuristic value to construct non-zero envelopes for features with zero X and/or Y extent. Start with a non-zero extent, in case the first feature inserted has a zero extent in both directions. This value may be non-optimal, but only one feature will be inserted with this value.

Definition at line 92 of file Quadtree.h.

std::vector<std::unique_ptr<geom::Envelope> > geos::index::quadtree::Quadtree::newEnvelopes
private

Definition at line 75 of file Quadtree.h.

Root geos::index::quadtree::Quadtree::root
private

Definition at line 79 of file Quadtree.h.


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