GEOS
3.9.1dev
|
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatial data. More...
#include <SimpleSTRtree.h>
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) |
![]() | |
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) |
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.
|
privatedelete |
|
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.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
inline |
Definition at line 139 of file SimpleSTRtree.h.
|
inline |
Definition at line 126 of file SimpleSTRtree.h.
|
inline |
Definition at line 130 of file SimpleSTRtree.h.
References geos::index::strtree::SimpleSTRnode::getNumLeafNodes().
|
inline |
Definition at line 143 of file SimpleSTRtree.h.
References geos::geom::operator<<().
void geos::index::strtree::SimpleSTRtree::insert | ( | geom::Geometry * | geom | ) |
|
overridevirtual |
Adds a spatial item with an extent specified by the given Envelope to the index.
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 | ||
) |
|
privatedelete |
|
private |
|
private |
|
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.
searchEnv | the envelope to query for |
Implements geos::index::SpatialIndex.
|
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.
searchEnv | the envelope to query for |
visitor | a visitor object to apply to the items found |
Implements geos::index::SpatialIndex.
|
private |
|
overridevirtual |
Removes a single item from the tree.
itemEnv | the Envelope of the item to remove |
item | the item to remove |
true
if the item was found Implements geos::index::SpatialIndex.
|
staticprivate |
|
staticprivate |
|
friend |
|
private |
Definition at line 74 of file SimpleSTRtree.h.
|
private |
Definition at line 73 of file SimpleSTRtree.h.
|
private |
Definition at line 72 of file SimpleSTRtree.h.
|
private |
Definition at line 71 of file SimpleSTRtree.h.
SimpleSTRnode* geos::index::strtree::SimpleSTRtree::root |
Definition at line 114 of file SimpleSTRtree.h.