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

#include <KDTreePartition.h>

Collaboration diagram for KDTreePartition< E, N, V >:

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.

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

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.

Member Enumeration Documentation

◆ Axis

template<class E , class N , class V >

enum class KDTreePartition::Axis

strong

Enum type for cell axis.

Enumerator
X
Y

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]	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.

◆ ~KDTreePartition()

template<class E , class N , class V >

KDTreePartition< E, N, V >::~KDTreePartition ( )

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.

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] number The 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] node The 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

Helper method for cellNumbers().

Parameters

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().

◆ 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] axis The 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] vehicle The 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] node The 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

The cells.

Definition at line 582 of file KDTreePartition.h.

Referenced by KDTreePartition< E, N, V >::getCells(), and KDTreePartition< E, N, V >::~KDTreePartition().

◆ 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

template<class E , class N , class V >

const int KDTreePartition< E, N, V >::myNumberOfLevels

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().

◆ myRoot

template<class E , class N , class V >

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

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().

◆ mySortedNodes

template<class E , class N , class V >

std::vector<const N*> KDTreePartition< E, N, V >::mySortedNodes

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().

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

KDTreePartition.h

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Axis

Constructor & Destructor Documentation

◆ KDTreePartition()

◆ ~KDTreePartition()

Member Function Documentation

◆ cell()

◆ cellNumbers()

◆ cellNumbersAux()

◆ flip()

◆ getCells()

◆ getCellsAtLevel()

◆ getNumberOfLevels()

◆ getRoot()

◆ init()

◆ isClean()

◆ numberOfArcFlags()

◆ numberOfCells()

◆ numberOfRegions()

◆ reset()

◆ searchNode()

Field Documentation

◆ myAmClean

◆ myCells

◆ myEdges

◆ myHavePermissions

◆ myHaveRestrictions

◆ myLevelCells

◆ myNumberOfLevels

◆ myRoot

◆ mySortedNodes