All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Public Attributes | Friends | List of all members
NetworKit::QuadNode< T, poincare > Class Template Reference

#include <QuadNode.h>

Public Member Functions

 QuadNode ()
 
 QuadNode (double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity=1000, bool splitTheoretical=false, double alpha=1, double balance=0.5)
 Construct a QuadNode for polar coordinates. More...
 
void split ()
 
void addContent (T input, double angle, double R)
 Add a point at polar coordinates (angle, R) with content input. More...
 
bool removeContent (T input, double angle, double R)
 Remove content at polar coordinates (angle, R). More...
 
bool outOfReach (Point2D< double > query, double radius) const
 Check whether the region managed by this node lies outside of an Euclidean circle. More...
 
bool outOfReach (double angle_c, double r_c, double radius) const
 Check whether the region managed by this node lies outside of an Euclidean circle. More...
 
std::pair< double, double > hyperbolicDistances (double phi, double r) const
 
bool responsible (double angle, double r) const
 Does the point at (angle, r) fall inside the region managed by this QuadNode? More...
 
std::vector< T > getElements () const
 Get all Elements in this QuadNode or a descendant of it. More...
 
void getCoordinates (vector< double > &anglesContainer, vector< double > &radiiContainer) const
 
QuadNode< T > & getAppropriateLeaf (double angle, double r)
 Don't use this! Code is still in here for a unit test. More...
 
void getElementsInEuclideanCircle (Point2D< double > center, double radius, vector< T > &result, double minAngle=0, double maxAngle=2 *M_PI, double lowR=0, double highR=1) const
 Main query method, get points lying in a Euclidean circle around the center point. More...
 
count getElementsProbabilistically (Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > &result) const
 
void maybeGetKthElement (double upperBound, Point2D< double > euQuery, std::function< double(double)> prob, index k, vector< T > &circleDenizens) const
 
void trim ()
 Shrink all vectors in this subtree to fit the content. More...
 
count size () const
 Number of points lying in the region managed by this QuadNode. More...
 
void recount ()
 
count height () const
 Height of subtree hanging from this QuadNode. More...
 
count countLeaves () const
 Leaf cells in the subtree hanging from this QuadNode. More...
 
double getLeftAngle () const
 
double getRightAngle () const
 
double getMinR () const
 
double getMaxR () const
 
index getID () const
 
index indexSubtree (index nextID)
 
index getCellID (double phi, double r) const
 
index getMaxIDInSubtree () const
 
count reindex (count offset)
 

Public Attributes

std::vector< QuadNodechildren
 

Friends

class QuadTreeGTest
 

Constructor & Destructor Documentation

template<class T, bool poincare = true>
NetworKit::QuadNode< T, poincare >::QuadNode ( )
inline
template<class T, bool poincare = true>
NetworKit::QuadNode< T, poincare >::QuadNode ( double  leftAngle,
double  minR,
double  rightAngle,
double  maxR,
unsigned  capacity = 1000,
bool  splitTheoretical = false,
double  alpha = 1,
double  balance = 0.5 
)
inline

Construct a QuadNode for polar coordinates.

Parameters
leftAngleMinimal angular coordinate of region, in radians from 0 to 2
minRMinimal radial coordinate of region, between 0 and 1
rightAngleMaximal angular coordinate of region, in radians from 0 to 2
maxRMaximal radial coordinate of region, between 0 and 1
capacityNumber of points a leaf cell can store before splitting
minDiameterMinimal diameter of a quadtree node. If the node is already smaller, don't split even if over capacity. Default is 0
splitTheoreticalWhether to split in a theoretically optimal way or in a way to decrease measured running times
alphadispersion Parameter of the point distribution. Only has an effect if theoretical split is true
diagnosticsCount how many necessary and unnecessary comparisons happen in leaf cells? Will cause race condition and false sharing in parallel use

Member Function Documentation

template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::addContent ( input,
double  angle,
double  R 
)
inline

Add a point at polar coordinates (angle, R) with content input.

May split node if capacity is full

Parameters
inputarbitrary content, in our case an index
angleangular coordinate of point, between 0 and 2 pi.
Rradial coordinate of point, between 0 and 1.
template<class T, bool poincare = true>
count NetworKit::QuadNode< T, poincare >::countLeaves ( ) const
inline

Leaf cells in the subtree hanging from this QuadNode.

template<class T, bool poincare = true>
QuadNode<T>& NetworKit::QuadNode< T, poincare >::getAppropriateLeaf ( double  angle,
double  r 
)
inline

Don't use this! Code is still in here for a unit test.

Get copy of the leaf cell responsible for a point at (angle, r). Expensive because it copies the whole subtree, causes assertion failure if called with the wrong arguments

Parameters
angleAngular coordinate of point
rRadial coordinate of point
Returns
Copy of leaf cell containing point, or dummy cell not responsible for point
template<class T, bool poincare = true>
index NetworKit::QuadNode< T, poincare >::getCellID ( double  phi,
double  r 
) const
inline
template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::getCoordinates ( vector< double > &  anglesContainer,
vector< double > &  radiiContainer 
) const
inline
template<class T, bool poincare = true>
std::vector<T> NetworKit::QuadNode< T, poincare >::getElements ( ) const
inline

Get all Elements in this QuadNode or a descendant of it.

Returns
vector of content type T
template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::getElementsInEuclideanCircle ( Point2D< double >  center,
double  radius,
vector< T > &  result,
double  minAngle = 0,
double  maxAngle = 2*M_PI,
double  lowR = 0,
double  highR = 1 
) const
inline

Main query method, get points lying in a Euclidean circle around the center point.

Optional limits can be given to get a different result or to reduce unnecessary comparisons

Elements are pushed onto a vector which is a required argument. This is done to reduce copying

Safe to call in parallel if diagnostics are disabled

Parameters
centerCenter of the query circle
radiusRadius of the query circle
resultReference to the vector where the results will be stored
minAngleOptional value for the minimum angular coordinate of the query region
maxAngleOptional value for the maximum angular coordinate of the query region
lowROptional value for the minimum radial coordinate of the query region
highROptional value for the maximum radial coordinate of the query region
template<class T, bool poincare = true>
count NetworKit::QuadNode< T, poincare >::getElementsProbabilistically ( Point2D< double >  euQuery,
std::function< double(double)>  prob,
bool  suppressLeft,
vector< T > &  result 
) const
inline
template<class T, bool poincare = true>
index NetworKit::QuadNode< T, poincare >::getID ( ) const
inline
template<class T, bool poincare = true>
double NetworKit::QuadNode< T, poincare >::getLeftAngle ( ) const
inline
template<class T, bool poincare = true>
index NetworKit::QuadNode< T, poincare >::getMaxIDInSubtree ( ) const
inline
template<class T, bool poincare = true>
double NetworKit::QuadNode< T, poincare >::getMaxR ( ) const
inline
template<class T, bool poincare = true>
double NetworKit::QuadNode< T, poincare >::getMinR ( ) const
inline
template<class T, bool poincare = true>
double NetworKit::QuadNode< T, poincare >::getRightAngle ( ) const
inline
template<class T, bool poincare = true>
count NetworKit::QuadNode< T, poincare >::height ( ) const
inline

Height of subtree hanging from this QuadNode.

template<class T, bool poincare = true>
std::pair<double, double> NetworKit::QuadNode< T, poincare >::hyperbolicDistances ( double  phi,
double  r 
) const
inline
Parameters
phiAngular coordinate of query point
r_hradial coordinate of query point in poincare disk

If the query point is not within the quadnode, the distance minimum is on the border. Need to check whether extremum is between corners:

cosh is a function from [0,) to [1, ) Variables thus need

template<class T, bool poincare = true>
index NetworKit::QuadNode< T, poincare >::indexSubtree ( index  nextID)
inline
template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::maybeGetKthElement ( double  upperBound,
Point2D< double >  euQuery,
std::function< double(double)>  prob,
index  k,
vector< T > &  circleDenizens 
) const
inline
template<class T, bool poincare = true>
bool NetworKit::QuadNode< T, poincare >::outOfReach ( Point2D< double >  query,
double  radius 
) const
inline

Check whether the region managed by this node lies outside of an Euclidean circle.

Parameters
queryCenter of the Euclidean query circle, given in Cartesian coordinates
radiusRadius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T, bool poincare = true>
bool NetworKit::QuadNode< T, poincare >::outOfReach ( double  angle_c,
double  r_c,
double  radius 
) const
inline

Check whether the region managed by this node lies outside of an Euclidean circle.

Functionality is the same as in the method above, but it takes polar coordinates instead of Cartesian ones

Parameters
angle_cAngular coordinate of the Euclidean query circle's center
r_cRadial coordinate of the Euclidean query circle's center
radiusRadius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::recount ( )
inline
template<class T, bool poincare = true>
count NetworKit::QuadNode< T, poincare >::reindex ( count  offset)
inline
template<class T, bool poincare = true>
bool NetworKit::QuadNode< T, poincare >::removeContent ( input,
double  angle,
double  R 
)
inline

Remove content at polar coordinates (angle, R).

May cause coarsening of the quadtree

Parameters
inputContent to be removed
angleAngular coordinate
RRadial coordinate
Returns
True if content was found and removed, false otherwise
template<class T, bool poincare = true>
bool NetworKit::QuadNode< T, poincare >::responsible ( double  angle,
double  r 
) const
inline

Does the point at (angle, r) fall inside the region managed by this QuadNode?

Parameters
angleAngular coordinate of input point
rRadial coordinate of input points
Returns
True if input point lies within the region of this QuadNode
template<class T, bool poincare = true>
count NetworKit::QuadNode< T, poincare >::size ( ) const
inline

Number of points lying in the region managed by this QuadNode.

template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::split ( )
inline

we want to make sure the space is evenly divided to obtain a balanced tree Simply halving the radius will cause a larger space for the outer Quadnode, resulting in an unbalanced tree

template<class T, bool poincare = true>
void NetworKit::QuadNode< T, poincare >::trim ( )
inline

Shrink all vectors in this subtree to fit the content.

Call after quadtree construction is complete, causes better memory usage and cache efficiency

Friends And Related Function Documentation

template<class T, bool poincare = true>
friend class QuadTreeGTest
friend

Member Data Documentation

template<class T, bool poincare = true>
std::vector<QuadNode> NetworKit::QuadNode< T, poincare >::children

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