Eclipse SUMO - Simulation of Urban MObility
|
Partitions the router's network wrt a k-d tree subdivision scheme. More...
#include <KDTreePartition.h>
Data Structures | |
class | Cell |
Represents an element of the node partition (i.e. a node set) More... | |
class | NodeXComparator |
class | NodeYComparator |
Public Types | |
enum class | Axis { X , Y } |
Enum type for cell axis. More... | |
Public Member Functions | |
const Cell * | cell (int number) const |
Returns the cell with the given number. | |
std::vector< int > * | cellNumbers (const N *node) const |
Returns the numbers of the cells which the given node is situated in. | |
const std::vector< const Cell * > & | getCells () |
Returns all cells. | |
const std::vector< const Cell * > & | getCellsAtLevel (int level) const |
Returns all cells of a level. | |
int | getNumberOfLevels () const |
Returns the number of levels L incl. the zeroth level. | |
const Cell * | getRoot () const |
Returns the root of the k-d tree. | |
void | init (const V *const vehicle) |
Initialize the k-d tree wrt to the given vehicle's permissions. | |
bool | isClean () |
Returns true iff the k-d tree is uninitialized. | |
KDTreePartition (int numberOfLevels, const std::vector< E * > &edges, const bool havePermissions, const bool haveRestrictions) | |
Constructor. | |
int | numberOfArcFlags () const |
Returns the number of arc flags required in a multi-level approach. | |
size_t | numberOfCells () const |
Returns the number of cells at all levels. | |
size_t | numberOfRegions () const |
Returns the number of regions, i.e. the number of cells at the shallowest (bottom/leaf) level. | |
void | reset (const V *const vehicle) |
Delete the k-d tree, and create a new one param[in] vehicle The vehicle. | |
const Cell * | searchNode (const N *node) const |
Search a node in the bottom cells (i.e., return the respective cell) | |
~KDTreePartition () | |
Destructor. | |
Static Public Member Functions | |
static Axis | flip (Axis axis) |
Returns the conjugated 2D axis. | |
Private Member Functions | |
void | cellNumbersAux (const N *node, const Cell *cell, int level, std::vector< int > *nodeCellNumbers) const |
Helper method for cellNumbers() . | |
Private Attributes | |
bool | myAmClean |
The boolean flag indicating whether the k-d tree is a clean (empty, uninitialized) instance or not. | |
std::vector< const Cell * > | myCells |
The cells. | |
const std::vector< E * > & | myEdges |
The reference to a constant container with pointers to edges. | |
const bool | myHavePermissions |
The boolean flag indicating whether edge permissions need to be considered or not. | |
const bool | myHaveRestrictions |
The boolean flag indicating whether edge restrictions need to be considered or not. | |
std::vector< std::vector< const Cell * > > | myLevelCells |
The cells of all partitions at all levels of the k-d tree subdivision scheme. | |
const int | myNumberOfLevels |
The number of levels. | |
const Cell * | myRoot |
The root of the k-d tree. | |
std::vector< const N * > | mySortedNodes |
The container with all nodes, sorted wrt to the k-d tree subdivision scheme. | |
Partitions the router's network wrt a k-d tree subdivision scheme.
The template parameters are:
E | The edge class to use (MSEdge/ROEdge) |
N | The node class to use (MSJunction/RONode) |
V | The vehicle class to use (MSVehicle/ROVehicle) |
Definition at line 86 of file KDTreePartition.h.
|
strong |
KDTreePartition< E, N, V >::KDTreePartition | ( | int | numberOfLevels, |
const std::vector< E * > & | edges, | ||
const bool | havePermissions, | ||
const bool | haveRestrictions | ||
) |
Constructor.
[in] | numberOfLevels | The number of levels |
[in] | edges | The container with all edges of the network |
[in] | havePermissions | The boolean flag indicating whether edge permissions need to be considered or not |
[in] | haveRestrictions | The boolean flag indicating whether edge restrictions need to be considered or not |
Definition at line 598 of file KDTreePartition.h.
|
inline |
Destructor.
Definition at line 478 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myCells, KDTreePartition< E, N, V >::myLevelCells, KDTreePartition< E, N, V >::myRoot, and KDTreePartition< E, N, V >::mySortedNodes.
const KDTreePartition< E, N, V >::Cell * KDTreePartition< E, N, V >::cell | ( | int | number | ) | const |
Returns the cell with the given number.
[in] | number | The cell number |
Definition at line 686 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::searchNode().
std::vector< int > * KDTreePartition< E, N, V >::cellNumbers | ( | const N * | node | ) | const |
Returns the numbers of the cells which the given node is situated in.
[in] | node | The node |
Definition at line 697 of file KDTreePartition.h.
|
private |
Helper method for cellNumbers()
.
node | The node |
cell | The cell |
level | The level |
nodeCellNumbers | The vector of cell numbers for the passed node |
Definition at line 715 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::Cell::contains(), KDTreePartition< E, N, V >::Cell::getAxis(), KDTreePartition< E, N, V >::Cell::getLeftOrLowerSubcell(), KDTreePartition< E, N, V >::Cell::getMaxX(), KDTreePartition< E, N, V >::Cell::getMaxY(), KDTreePartition< E, N, V >::Cell::getMinX(), KDTreePartition< E, N, V >::Cell::getMinY(), KDTreePartition< E, N, V >::Cell::getNumber(), and KDTreePartition< E, N, V >::Cell::getRightOrUpperSubcell().
|
inlinestatic |
Returns the conjugated 2D axis.
[in] | axis | The axis |
Definition at line 525 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::X, and KDTreePartition< E, N, V >::Y.
Referenced by KDTreePartition< E, N, V >::Cell::Cell().
|
inline |
Returns all cells.
Definition at line 502 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myCells.
|
inline |
Returns all cells of a level.
Definition at line 512 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myLevelCells.
|
inline |
Returns the number of levels L incl. the zeroth level.
Definition at line 538 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myNumberOfLevels.
|
inline |
Returns the root of the k-d tree.
Definition at line 498 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myRoot.
void KDTreePartition< E, N, V >::init | ( | const V *const | vehicle | ) |
Initialize the k-d tree wrt to the given vehicle's permissions.
[in] | vehicle | The vehicle |
Definition at line 611 of file KDTreePartition.h.
Referenced by computeRoutes(), and KDTreePartition< E, N, V >::reset().
|
inline |
Returns true iff the k-d tree is uninitialized.
Definition at line 554 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myAmClean.
|
inline |
Returns the number of arc flags required in a multi-level approach.
Definition at line 533 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myNumberOfLevels.
|
inline |
Returns the number of cells at all levels.
Definition at line 544 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myNumberOfLevels.
|
inline |
Returns the number of regions, i.e. the number of cells at the shallowest (bottom/leaf) level.
Definition at line 550 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::myNumberOfLevels.
|
inline |
Delete the k-d tree, and create a new one param[in] vehicle The vehicle.
Definition at line 493 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::init(), and KDTreePartition< E, N, V >::myRoot.
const KDTreePartition< E, N, V >::Cell * KDTreePartition< E, N, V >::searchNode | ( | const N * | node | ) | const |
Search a node in the bottom cells (i.e., return the respective cell)
[in] | node | The node |
Definition at line 1489 of file KDTreePartition.h.
References KDTreePartition< E, N, V >::cell(), KDTreePartition< E, N, V >::Cell::contains(), KDTreePartition< E, N, V >::Cell::getAxis(), KDTreePartition< E, N, V >::Cell::getLeftOrLowerSubcell(), KDTreePartition< E, N, V >::Cell::getMedianCoordinate(), KDTreePartition< E, N, V >::Cell::getRightOrUpperSubcell(), KDTreePartition< E, N, V >::myRoot, and KDTreePartition< E, N, V >::X.
|
private |
The boolean flag indicating whether the k-d tree is a clean (empty, uninitialized) instance or not.
Definition at line 590 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::isClean().
|
private |
The cells.
Definition at line 582 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::getCells(), and KDTreePartition< E, N, V >::~KDTreePartition().
|
private |
The reference to a constant container with pointers to edges.
Definition at line 578 of file KDTreePartition.h.
|
private |
The boolean flag indicating whether edge permissions need to be considered or not.
Definition at line 586 of file KDTreePartition.h.
|
private |
The boolean flag indicating whether edge restrictions need to be considered or not.
Definition at line 588 of file KDTreePartition.h.
|
private |
The cells of all partitions at all levels of the k-d tree subdivision scheme.
Definition at line 584 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::getCellsAtLevel(), and KDTreePartition< E, N, V >::~KDTreePartition().
|
private |
The number of levels.
Definition at line 576 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::getNumberOfLevels(), KDTreePartition< E, N, V >::numberOfArcFlags(), KDTreePartition< E, N, V >::numberOfCells(), and KDTreePartition< E, N, V >::numberOfRegions().
|
private |
The root of the k-d tree.
Definition at line 574 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::getRoot(), KDTreePartition< E, N, V >::reset(), KDTreePartition< E, N, V >::searchNode(), and KDTreePartition< E, N, V >::~KDTreePartition().
|
private |
The container with all nodes, sorted wrt to the k-d tree subdivision scheme.
Definition at line 580 of file KDTreePartition.h.
Referenced by KDTreePartition< E, N, V >::Cell::edgeSet(), KDTreePartition< E, N, V >::Cell::maxAxisValue(), KDTreePartition< E, N, V >::Cell::minAxisValue(), KDTreePartition< E, N, V >::Cell::nodeIterators(), KDTreePartition< E, N, V >::Cell::nodes(), KDTreePartition< E, N, V >::Cell::numberOfEdgesEndingInCell(), KDTreePartition< E, N, V >::Cell::numberOfEdgesStartingInCell(), KDTreePartition< E, N, V >::Cell::partition(), and KDTreePartition< E, N, V >::~KDTreePartition().