#include <Spatial_Tree.h>
Inherits Tree< container_type *, tree_type >.
Inheritance diagram for Spatial_Tree< tree_type, bb_type, container_type >:
Public Member Functions | |
| virtual bool | checkReady () const |
| virtual void | ensureReady () |
| virtual | ~Spatial_Tree () |
| virtual tree_type * | insert (container_type *container)=0 |
| virtual tree_type * | remove (container_type *container)=0 |
| template<class InputIterator> | |
| void | insertPolytopes (InputIterator begin, InputIterator end) |
| virtual vector< int > | neighboursOf (const container_type *item) const=0 |
| virtual vector< int > | neighboursOf (const vector< double > &point, const unsigned int k) const=0 |
| virtual vector< int > | containedIn (const bb_type &box) const=0 |
| virtual vector< int > | intersects (const Point &point) const=0 |
| virtual vector< int > | intersects (const vector< double > &begin, const vector< double > &end) const=0 |
| virtual vector< int > | intersects (const vector< double > &a, const double b) const=0 |
For the application on Shell's problem, we need a Tree which stores Polytopes. Also, the queries which Shell wants to execute on the data stored in this tree, are declared as purely virtual functions here. This forces any derived class to have to implement code to support those queries.
Definition at line 31 of file Spatial_Tree.h.
| virtual Spatial_Tree< tree_type, bb_type, container_type >::~Spatial_Tree | ( | ) | [inline, virtual] |
Base deconstructor
Definition at line 52 of file Spatial_Tree.h.
| virtual bool Spatial_Tree< tree_type, bb_type, container_type >::checkReady | ( | ) | const [inline, virtual] |
Checks if the tree is ready for access.
Definition at line 41 of file Spatial_Tree.h.
| virtual void Spatial_Tree< tree_type, bb_type, container_type >::ensureReady | ( | ) | [inline, virtual] |
Checks if the tree is ready for queries. If not, it starts the procedures necessary to make it so.
Definition at line 47 of file Spatial_Tree.h.
| virtual tree_type* Spatial_Tree< tree_type, bb_type, container_type >::insert | ( | container_type * | container | ) | [pure virtual] |
Inserts a single element into the tree structure
| container | Pointer to the container to be added |
Implements Tree< container_type *, tree_type >.
Implemented in Basic_R_tree, and Hilbert_R_tree.
Referenced by Spatial_Tree< Basic_R_tree, BB_type, BB_container >::insertPolytopes().
| virtual tree_type* Spatial_Tree< tree_type, bb_type, container_type >::remove | ( | container_type * | container | ) | [pure virtual] |
Removes elements from the tree. This is also a tree-type specific operation and thus is virtual here.
| container | Pointer to the element to be removed |
Implements Tree< container_type *, tree_type >.
Implemented in Basic_R_tree, and Hilbert_R_tree.
| void Spatial_Tree< tree_type, bb_type, container_type >::insertPolytopes | ( | InputIterator | begin, | |
| InputIterator | end | |||
| ) | [inline] |
Inserts a range of polytopes into the tree structure.
| begin | An iterator at the first polytope to be added. | |
| end | An iterator at one location past the last iterator to be added. |
Definition at line 100 of file Spatial_Tree.h.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::neighboursOf | ( | const container_type * | item | ) | const [pure virtual] |
Searches and returns which polytopes are considered to be neighbours of a given polytope pointed to.
| item | A pointer to the Polytope we wish to know the neighbours of. |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::neighboursOf | ( | const vector< double > & | point, | |
| const unsigned int | k | |||
| ) | const [pure virtual] |
Searches and returns the polytopes that are the closest neighbours of a given point.
| point | The point we wish to know the neighbours of. | |
| k | The number of neighbours we are looking for. |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::containedIn | ( | const bb_type & | box | ) | const [pure virtual] |
Searches and returns all polytopes which are contained in a given bounding box.
| box | The given bounding box. |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::intersects | ( | const Point & | point | ) | const [pure virtual] |
Searches and returns all polytopes which intersect a given Point.
| point | The given point. |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::intersects | ( | const vector< double > & | begin, | |
| const vector< double > & | end | |||
| ) | const [pure virtual] |
Searches and returns all polytopes which intersect a line defined by its given start- en ending points.
| begin | The starting point of the line | |
| end | The ending point of the line |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
| virtual vector<int> Spatial_Tree< tree_type, bb_type, container_type >::intersects | ( | const vector< double > & | a, | |
| const double | b | |||
| ) | const [pure virtual] |
Searches and returns all polytopes which intersect an affine hyperplane. A hyperplane is defined as:
a_1 * x_1 + a_2 * x_2 + ... + a_{n-1} * x_{n-1} = b
where n is the dimension of the bounding boxes stored in this tree, a is a vector of length n-1, x are the coordinates in R^{(n-1)} which lie on the hyperplane, b is a scalar.
| a | The n-1 vector a. | |
| b | The scalar b. |
Implemented in R_tree< r_tree_variation >, R_tree< Basic_R_tree >, and R_tree< Hilbert_R_tree >.
1.5.2