Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
KDTreePartition< E, N, V > Class Template Reference

Partitions the router's network wrt a k-d tree subdivision scheme. More...

#include <KDTreePartition.h>

Collaboration diagram for KDTreePartition< E, N, V >:
[legend]

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 Cellcell (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 CellgetRoot () 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 CellsearchNode (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 CellmyRoot
 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.
 

Detailed Description

template<class E, class N, class V>
class KDTreePartition< E, N, V >

Partitions the router's network wrt a k-d tree subdivision scheme.

The template parameters are:

Parameters
EThe edge class to use (MSEdge/ROEdge)
NThe node class to use (MSJunction/RONode)
VThe vehicle class to use (MSVehicle/ROVehicle)

Definition at line 86 of file KDTreePartition.h.

Member Enumeration Documentation

◆ Axis

template<class E , class N , class V >
enum class KDTreePartition::Axis
strong

Enum type for cell axis.

Enumerator

Definition at line 89 of file KDTreePartition.h.

Constructor & Destructor Documentation

◆ KDTreePartition()

template<class E , class N , class V >
KDTreePartition< E, N, V >::KDTreePartition ( int  numberOfLevels,
const std::vector< E * > &  edges,
const bool  havePermissions,
const bool  haveRestrictions 
)

Constructor.

Parameters
[in]numberOfLevelsThe number of levels
[in]edgesThe container with all edges of the network
[in]havePermissionsThe boolean flag indicating whether edge permissions need to be considered or not
[in]haveRestrictionsThe boolean flag indicating whether edge restrictions need to be considered or not

Definition at line 598 of file KDTreePartition.h.

◆ ~KDTreePartition()

Member Function Documentation

◆ cell()

template<class E , class N , class V >
const KDTreePartition< E, N, V >::Cell * KDTreePartition< E, N, V >::cell ( int  number) const

Returns the cell with the given number.

Note
Returns nullptr, if no such cell exists
Parameters
[in]numberThe cell number
Returns
The cell with the given number

Definition at line 686 of file KDTreePartition.h.

Referenced by KDTreePartition< E, N, V >::searchNode().

Here is the caller graph for this function:

◆ cellNumbers()

template<class E , class N , class V >
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.

Parameters
[in]nodeThe node
Returns
The numbers of the cells which the given node is situated in

Definition at line 697 of file KDTreePartition.h.

◆ cellNumbersAux()

template<class E , class N , class V >
void KDTreePartition< E, N, V >::cellNumbersAux ( const N *  node,
const Cell cell,
int  level,
std::vector< int > *  nodeCellNumbers 
) const
private

◆ flip()

template<class E , class N , class V >
static Axis KDTreePartition< E, N, V >::flip ( Axis  axis)
inlinestatic

Returns the conjugated 2D axis.

Note
X->Y / Y->X
Parameters
[in]axisThe axis
Returns
The conjugated 2D 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().

Here is the caller graph for this function:

◆ getCells()

template<class E , class N , class V >
const std::vector< const Cell * > & KDTreePartition< E, N, V >::getCells ( )
inline

Returns all cells.

Definition at line 502 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::myCells.

◆ getCellsAtLevel()

template<class E , class N , class V >
const std::vector< const Cell * > & KDTreePartition< E, N, V >::getCellsAtLevel ( int  level) const
inline

Returns all cells of a level.

Definition at line 512 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::myLevelCells.

◆ getNumberOfLevels()

template<class E , class N , class V >
int KDTreePartition< E, N, V >::getNumberOfLevels ( ) const
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.

◆ getRoot()

template<class E , class N , class V >
const Cell * KDTreePartition< E, N, V >::getRoot ( ) const
inline

Returns the root of the k-d tree.

Definition at line 498 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::myRoot.

◆ init()

template<class E , class N , class V >
void KDTreePartition< E, N, V >::init ( const V *const  vehicle)

Initialize the k-d tree wrt to the given vehicle's permissions.

Parameters
[in]vehicleThe vehicle

Definition at line 611 of file KDTreePartition.h.

Referenced by computeRoutes(), and KDTreePartition< E, N, V >::reset().

Here is the caller graph for this function:

◆ isClean()

template<class E , class N , class V >
bool KDTreePartition< E, N, V >::isClean ( )
inline

Returns true iff the k-d tree is uninitialized.

Definition at line 554 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::myAmClean.

◆ numberOfArcFlags()

template<class E , class N , class V >
int KDTreePartition< E, N, V >::numberOfArcFlags ( ) const
inline

Returns the number of arc flags required in a multi-level approach.

Note
E.g.: number of levels := 3 -> 2 + 2 = 4 bits are required
No flag(s) for root level 0; each non-leaf cell has two subcells
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.

◆ numberOfCells()

template<class E , class N , class V >
size_t KDTreePartition< E, N, V >::numberOfCells ( ) const
inline

Returns the number of cells at all levels.

Returns
The number of cells at all levels

Definition at line 544 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::myNumberOfLevels.

◆ numberOfRegions()

template<class E , class N , class V >
size_t KDTreePartition< E, N, V >::numberOfRegions ( ) const
inline

Returns the number of regions, i.e. the number of cells at the shallowest (bottom/leaf) level.

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.

◆ reset()

template<class E , class N , class V >
void KDTreePartition< E, N, V >::reset ( const V *const  vehicle)
inline

Delete the k-d tree, and create a new one param[in] vehicle The vehicle.

Note
Recreated wrt the network given at construction and the given edge

Definition at line 493 of file KDTreePartition.h.

References KDTreePartition< E, N, V >::init(), and KDTreePartition< E, N, V >::myRoot.

◆ searchNode()

template<class E , class N , class V >
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)

Note
Uses the position of the node and the divisional structure of the k-d tree for the search.
O(log n) where n = number of cells
Parameters
[in]nodeThe node
Returns
The bottom cell containing the node, or nullptr if the node could not be found

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.

Field Documentation

◆ myAmClean

template<class E , class N , class V >
bool KDTreePartition< E, N, V >::myAmClean
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().

◆ myCells

template<class E , class N , class V >
std::vector<const Cell*> KDTreePartition< E, N, V >::myCells
private

◆ myEdges

template<class E , class N , class V >
const std::vector<E*>& KDTreePartition< E, N, V >::myEdges
private

The reference to a constant container with pointers to edges.

Definition at line 578 of file KDTreePartition.h.

◆ myHavePermissions

template<class E , class N , class V >
const bool KDTreePartition< E, N, V >::myHavePermissions
private

The boolean flag indicating whether edge permissions need to be considered or not.

Definition at line 586 of file KDTreePartition.h.

◆ myHaveRestrictions

template<class E , class N , class V >
const bool KDTreePartition< E, N, V >::myHaveRestrictions
private

The boolean flag indicating whether edge restrictions need to be considered or not.

Definition at line 588 of file KDTreePartition.h.

◆ myLevelCells

template<class E , class N , class V >
std::vector<std::vector<const Cell*> > KDTreePartition< E, N, V >::myLevelCells
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().

◆ myNumberOfLevels

◆ myRoot

template<class E , class N , class V >
const Cell* KDTreePartition< E, N, V >::myRoot
private

◆ mySortedNodes


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