#include <Quadtree.h>
Inheritance diagram for geos::index::quadtree::Quadtree:
Public Member Functions | |
Quadtree () | |
Constructs a Quadtree with zero items. | |
int | depth () |
Returns the number of levels in the tree. | |
int | size () |
Returns the number of items in the tree. | |
void | insert (const geom::Envelope *itemEnv, void *item) |
Adds a spatial item with an extent specified by the given Envelope to the index. | |
void | query (const geom::Envelope *searchEnv, std::vector< void * > &ret) |
Queries the tree and returns items which may lie in the given search envelope. | |
void | query (const geom::Envelope *searchEnv, ItemVisitor &visitor) |
Queries the tree and visits items which may lie in the given search envelope. | |
bool | remove (const geom::Envelope *itemEnv, void *item) |
std::vector< void * > * | queryAll () |
Return a list of all items in the Quadtree. | |
std::string | toString () const |
Static Public Member Functions | |
geom::Envelope * | ensureExtent (const geom::Envelope *itemEnv, double minExtent) |
Ensure that the envelope for the inserted item has non-zero extents. |
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.
|
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). |
|
Adds a spatial item with an extent specified by the given Envelope to the index.
Implements geos::index::SpatialIndex. |
|
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.
Implements geos::index::SpatialIndex. |
|
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.
Implements geos::index::SpatialIndex. |
|
Removes a single item from the tree.
Implements geos::index::SpatialIndex. |