SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SUMORTree Class Reference

A RT-tree for efficient storing of SUMO's GL-objects. More...

#include <SUMORTree.h>

Inheritance diagram for SUMORTree:
RTree< GUIGlObject *, GUIGlObject, float, 2, GUIVisualizationSettings > Boundary AbstractPoly LayeredRTree

Public Member Functions

void add (SUMOReal x, SUMOReal y)
 Makes the boundary include the given coordinate.
void add (const Position &p)
 Makes the boundary include the given coordinate.
void add (const Boundary &p)
 Makes the boundary include the given boundary.
void addAdditionalGLObject (GUIGlObject *o)
 Adds an additional object (detector/shape/trigger) for visualisation.
bool around (const Position &p, SUMOReal offset=0) const
 Returns whether the boundary contains the given coordinate.
bool crosses (const Position &p1, const Position &p2) const
 Returns whether the boundary crosses the given line.
void flipY ()
 flips ymin and ymax
Position getCenter () const
 Returns the center of the boundary.
SUMOReal getHeight () const
 Returns the height of the boundary.
SUMOReal getWidth () const
 Returns the width of the boudary.
Boundarygrow (SUMOReal by)
 extends the boundary by the given amount
void growHeight (SUMOReal by)
void growWidth (SUMOReal by)
virtual void Insert (const float a_min[2], const float a_max[2], GUIGlObject *a_dataId)
 Insert entry.
void moveby (SUMOReal x, SUMOReal y)
 Moves the boundary by the given amount.
bool overlapsWith (const AbstractPoly &poly, SUMOReal offset=0) const
 Returns whether the boundary overlaps with the given polygon.
bool partialWithin (const AbstractPoly &poly, SUMOReal offset=0) const
 Returns whether the boundary is partially within the given polygon.
virtual void Remove (const float a_min[2], const float a_max[2], GUIGlObject *a_dataId)
 Remove entry.
void removeAdditionalGLObject (GUIGlObject *o)
 Removes an additional object (detector/shape/trigger) from being visualised.
void reset ()
 Resets the boundary.
virtual int Search (const float a_min[2], const float a_max[2], const GUIVisualizationSettings &c)
 Find all within search rectangle.
void set (SUMOReal xmin, SUMOReal ymin, SUMOReal xmax, SUMOReal ymax)
 Sets the boundary to the given values.
 SUMORTree ()
 Constructor.
SUMOReal xmax () const
 Returns maximum x-coordinate.
SUMOReal xmin () const
 Returns minimum x-coordinate.
SUMOReal ymax () const
 Returns maximum y-coordinate.
SUMOReal ymin () const
 Returns minimum y-coordinate.
virtual ~SUMORTree ()
 Destructor.

Protected Attributes

MFXMutex myLock
 A mutex avoiding parallel change and traversal of the tree.

Private Types

enum  
typedef void(GUIGlObject::* Operation )(const GUIVisualizationSettings &) const

Private Member Functions

bool AddBranch (Branch *a_branch, Node *a_node, Node **a_newNode)
ListNode * AllocListNode ()
Node * AllocNode ()
float CalcRectVolume (Rect *a_rect)
void ChoosePartition (PartitionVars *a_parVars, int a_minFill)
void Classify (int a_index, int a_group, PartitionVars *a_parVars)
Rect CombineRect (Rect *a_rectA, Rect *a_rectB)
int Count ()
 Count the data elements in this container. This is slow as no internal counter is maintained.
void CountRec (Node *a_node, int &a_count)
void DisconnectBranch (Node *a_node, int a_index)
void FreeListNode (ListNode *a_listNode)
void FreeNode (Node *a_node)
GUIGlObject *& GetAt (Iterator &a_it)
 Get object at iterator position.
void GetBranches (Node *a_node, Branch *a_branch, PartitionVars *a_parVars)
void GetFirst (Iterator &a_it)
 Get 'first' for iteration.
void GetNext (Iterator &a_it)
 Get Next for iteration.
void InitNode (Node *a_node)
void InitParVars (PartitionVars *a_parVars, int a_maxRects, int a_minFill)
void InitRect (Rect *a_rect)
virtual void Insert (const floata_min[NUMDIMS], const floata_max[NUMDIMS], const GUIGlObject *&a_dataId)
bool InsertRect (Rect *a_rect, const GUIGlObject *&a_id, Node **a_root, int a_level)
bool InsertRectRec (Rect *a_rect, const GUIGlObject *&a_id, Node *a_node, Node **a_newNode, int a_level)
bool IsNull (Iterator &a_it)
 Is iterator NULL, or at end?
void LoadNodes (Node *a_nodeA, Node *a_nodeB, PartitionVars *a_parVars)
Rect NodeCover (Node *a_node)
bool Overlap (Rect *a_rectA, Rect *a_rectB)
int PickBranch (Rect *a_rect, Node *a_node)
void PickSeeds (PartitionVars *a_parVars)
float RectSphericalVolume (Rect *a_rect)
float RectVolume (Rect *a_rect)
void ReInsert (Node *a_node, ListNode **a_listNode)
virtual void Remove (const floata_min[NUMDIMS], const floata_max[NUMDIMS], const GUIGlObject *&a_dataId)
void RemoveAll ()
 DK 15.10.2008 - end.
void RemoveAllRec (Node *a_node)
bool RemoveRect (Rect *a_rect, const GUIGlObject *&a_id, Node **a_root)
bool RemoveRectRec (Rect *a_rect, const GUIGlObject *&a_id, Node *a_node, ListNode **a_listNode)
void Reset ()
virtual int Search (const floata_min[NUMDIMS], const floata_max[NUMDIMS], const GUIVisualizationSettings &c)
 DK 15.10.2008 - begin.
bool Search (Node *a_node, Rect *a_rect, int &a_foundCount, const GUIVisualizationSettings &c)
void SplitNode (Node *a_node, Branch *a_branch, Node **a_newNode)

Private Attributes

Node * m_root
 Root of tree.
float m_unitSphereVolume
 Unit sphere constant for required number of dimensions.
Operation myOperation

Detailed Description

A RT-tree for efficient storing of SUMO's GL-objects.

This class specialises the used RT-tree implementation from "rttree.h" and extends it by a mutex for avoiding parallel change and traversal of the tree.

Definition at line 61 of file SUMORTree.h.

Member Typedef Documentation

typedef void(GUIGlObject ::* RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Operation)(const GUIVisualizationSettings &) const
inherited

Definition at line 79 of file RTree.h.

Member Enumeration Documentation

anonymous enum
inherited

Definition at line 71 of file RTree.h.

Constructor & Destructor Documentation

SUMORTree::SUMORTree ( )
inline

Constructor.

Definition at line 65 of file SUMORTree.h.

Referenced by LayeredRTree::LayeredRTree().

virtual SUMORTree::~SUMORTree ( )
inlinevirtual

Destructor.

Definition at line 71 of file SUMORTree.h.

Member Function Documentation

void Boundary::add ( SUMOReal  x,
SUMOReal  y 
)
inherited
void Boundary::add ( const Position p)
inherited

Makes the boundary include the given coordinate.

Definition at line 93 of file Boundary.cpp.

References Boundary::add(), Position::x(), and Position::y().

void Boundary::add ( const Boundary p)
inherited

Makes the boundary include the given boundary.

Definition at line 99 of file Boundary.cpp.

References Boundary::add(), Boundary::xmax(), Boundary::xmin(), Boundary::ymax(), and Boundary::ymin().

void SUMORTree::addAdditionalGLObject ( GUIGlObject o)
inline
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::AddBranch ( Branch *  a_branch,
Node *  a_node,
Node **  a_newNode 
)
protectedinherited
ListNode* RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::AllocListNode ( )
protectedinherited
Node* RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::AllocNode ( )
protectedinherited
bool Boundary::around ( const Position p,
SUMOReal  offset = 0 
) const
virtualinherited

Returns whether the boundary contains the given coordinate.

Implements AbstractPoly.

Definition at line 148 of file Boundary.cpp.

References Boundary::myXmax, Boundary::myXmin, Boundary::myYmax, Boundary::myYmin, Position::x(), and Position::y().

Referenced by NIVissimConnectionCluster::around(), PCPolyContainer::insert(), and NIVissimConnectionCluster::recheckEdges().

float RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::CalcRectVolume ( Rect *  a_rect)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::ChoosePartition ( PartitionVars *  a_parVars,
int  a_minFill 
)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Classify ( int  a_index,
int  a_group,
PartitionVars *  a_parVars 
)
protectedinherited
Rect RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::CombineRect ( Rect *  a_rectA,
Rect *  a_rectB 
)
protectedinherited
int RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Count ( )
inherited

Count the data elements in this container. This is slow as no internal counter is maintained.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::CountRec ( Node *  a_node,
int a_count 
)
protectedinherited
bool Boundary::crosses ( const Position p1,
const Position p2 
) const
virtualinherited

Returns whether the boundary crosses the given line.

Implements AbstractPoly.

Definition at line 177 of file Boundary.cpp.

References GeomHelper::intersects(), Boundary::myXmax, Boundary::myXmin, Boundary::myYmax, and Boundary::myYmin.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::DisconnectBranch ( Node *  a_node,
int  a_index 
)
protectedinherited
void Boundary::flipY ( )
inherited

flips ymin and ymax

Definition at line 222 of file Boundary.cpp.

References Boundary::myYmax, Boundary::myYmin, and SUMOReal.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::FreeListNode ( ListNode *  a_listNode)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::FreeNode ( Node *  a_node)
protectedinherited
GUIGlObject * & RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::GetAt ( Iterator &  a_it)
inlineinherited

Get object at iterator position.

Definition at line 263 of file RTree.h.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::GetBranches ( Node *  a_node,
Branch *  a_branch,
PartitionVars *  a_parVars 
)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::GetFirst ( Iterator &  a_it)
inlineinherited

Get 'first' for iteration.

Definition at line 246 of file RTree.h.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::GetNext ( Iterator &  a_it)
inlineinherited

Get Next for iteration.

Definition at line 257 of file RTree.h.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::InitNode ( Node *  a_node)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::InitParVars ( PartitionVars *  a_parVars,
int  a_maxRects,
int  a_minFill 
)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::InitRect ( Rect *  a_rect)
protectedinherited
virtual void SUMORTree::Insert ( const float  a_min[2],
const float  a_max[2],
GUIGlObject a_dataId 
)
inlinevirtual

Insert entry.

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
See Also
RTree::Insert

Reimplemented in LayeredRTree.

Definition at line 81 of file SUMORTree.h.

References myLock.

Referenced by addAdditionalGLObject().

virtual void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Insert ( const float  a_min[NUMDIMS],
const float  a_max[NUMDIMS],
const GUIGlObject * &  a_dataId 
)
virtualinherited

Insert entry

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::InsertRect ( Rect *  a_rect,
const GUIGlObject * &  a_id,
Node **  a_root,
int  a_level 
)
protectedinherited
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::InsertRectRec ( Rect *  a_rect,
const GUIGlObject * &  a_id,
Node *  a_node,
Node **  a_newNode,
int  a_level 
)
protectedinherited
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::IsNull ( Iterator &  a_it)
inlineinherited

Is iterator NULL, or at end?

Definition at line 260 of file RTree.h.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::LoadNodes ( Node *  a_nodeA,
Node *  a_nodeB,
PartitionVars *  a_parVars 
)
protectedinherited
void Boundary::moveby ( SUMOReal  x,
SUMOReal  y 
)
inherited
Rect RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::NodeCover ( Node *  a_node)
protectedinherited
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Overlap ( Rect *  a_rectA,
Rect *  a_rectB 
)
protectedinherited
bool Boundary::overlapsWith ( const AbstractPoly poly,
SUMOReal  offset = 0 
) const
virtualinherited
bool Boundary::partialWithin ( const AbstractPoly poly,
SUMOReal  offset = 0 
) const
virtualinherited

Returns whether the boundary is partially within the given polygon.

Implements AbstractPoly.

Definition at line 190 of file Boundary.cpp.

References AbstractPoly::around(), Boundary::myXmax, Boundary::myXmin, Boundary::myYmax, and Boundary::myYmin.

Referenced by PCPolyContainer::insert(), and Boundary::overlapsWith().

int RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::PickBranch ( Rect *  a_rect,
Node *  a_node 
)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::PickSeeds ( PartitionVars *  a_parVars)
protectedinherited
float RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RectSphericalVolume ( Rect *  a_rect)
protectedinherited
float RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RectVolume ( Rect *  a_rect)
protectedinherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::ReInsert ( Node *  a_node,
ListNode **  a_listNode 
)
protectedinherited
virtual void SUMORTree::Remove ( const float  a_min[2],
const float  a_max[2],
GUIGlObject a_dataId 
)
inlinevirtual

Remove entry.

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
See Also
RTree::Remove

Reimplemented in LayeredRTree.

Definition at line 93 of file SUMORTree.h.

References myLock.

Referenced by removeAdditionalGLObject().

virtual void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Remove ( const float  a_min[NUMDIMS],
const float  a_max[NUMDIMS],
const GUIGlObject * &  a_dataId 
)
virtualinherited

Remove entry

Parameters
a_minMin of bounding rect
a_maxMax of bounding rect
a_dataIdPositive Id of data. Maybe zero, but negative numbers not allowed.
void SUMORTree::removeAdditionalGLObject ( GUIGlObject o)
inline

Removes an additional object (detector/shape/trigger) from being visualised.

Parameters
[in]oThe object to remove

Definition at line 128 of file SUMORTree.h.

References GUIGlObject::getCenteringBoundary(), Remove(), Boundary::xmax(), Boundary::xmin(), Boundary::ymax(), and Boundary::ymin().

Referenced by GUIShapeContainer::movePOI(), GUIShapeContainer::removePOI(), GUIShapeContainer::removePolygon(), and GUIShapeContainer::reshapePolygon().

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RemoveAll ( )
inherited

DK 15.10.2008 - end.

Remove all entries from tree

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RemoveAllRec ( Node *  a_node)
protectedinherited
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RemoveRect ( Rect *  a_rect,
const GUIGlObject * &  a_id,
Node **  a_root 
)
protectedinherited
bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::RemoveRectRec ( Rect *  a_rect,
const GUIGlObject * &  a_id,
Node *  a_node,
ListNode **  a_listNode 
)
protectedinherited
void Boundary::reset ( )
inherited

Resets the boundary.

Definition at line 66 of file Boundary.cpp.

References Boundary::myWasInitialised, Boundary::myXmax, Boundary::myXmin, Boundary::myYmax, and Boundary::myYmin.

void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Reset ( )
protectedinherited
virtual int RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Search ( const float  a_min[NUMDIMS],
const float  a_max[NUMDIMS],
const GUIVisualizationSettings c 
)
virtualinherited

DK 15.10.2008 - begin.

Find all within search rectangle

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_searchResultSearch result array. Caller should set grow size. Function will reset, not append to array.
a_resultCallbackCallback function to return result. Callback should return 'true' to continue searching
a_contextUser context to pass as parameter to a_resultCallback
Returns
Returns the number of entries found
virtual int SUMORTree::Search ( const float  a_min[2],
const float  a_max[2],
const GUIVisualizationSettings c 
)
inlinevirtual

Find all within search rectangle.

Parameters
a_minMin of search bounding rect
a_maxMax of search bounding rect
a_searchResultSearch result array. Caller should set grow size. Function will reset, not append to array.
a_resultCallbackCallback function to return result. Callback should return 'true' to continue searching
a_contextUser context to pass as parameter to a_resultCallback
Returns
Returns the number of entries found
See Also
RTree::Search

Reimplemented in LayeredRTree.

Definition at line 108 of file SUMORTree.h.

References myLock.

Referenced by GUIViewTraffic::doPaintGL(), and GUISUMOAbstractView::makeSnapshot().

bool RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::Search ( Node *  a_node,
Rect *  a_rect,
int a_foundCount,
const GUIVisualizationSettings c 
)
protectedinherited
void Boundary::set ( SUMOReal  xmin,
SUMOReal  ymin,
SUMOReal  xmax,
SUMOReal  ymax 
)
inherited
void RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::SplitNode ( Node *  a_node,
Branch *  a_branch,
Node **  a_newNode 
)
protectedinherited

Field Documentation

Node* RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::m_root
protectedinherited

Root of tree.

Definition at line 359 of file RTree.h.

float RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::m_unitSphereVolume
protectedinherited

Unit sphere constant for required number of dimensions.

Definition at line 360 of file RTree.h.

MFXMutex SUMORTree::myLock
protected

A mutex avoiding parallel change and traversal of the tree.

Definition at line 138 of file SUMORTree.h.

Referenced by Insert(), Remove(), and Search().

Operation RTree< GUIGlObject * , GUIGlObject , float , NUMDIMS, GUIVisualizationSettings , float , 8 , 8 / 2 >::myOperation
protectedinherited

Definition at line 361 of file RTree.h.


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