NetworKit::QuadNodePolarEuclid< T > Class Template Reference

`#include <QuadNodePolarEuclid.h>`

## Public Member Functions

QuadNodePolarEuclid (double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity=1000, bool splitTheoretical=false, 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 > EuclideanDistances (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

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)

## Constructor & Destructor Documentation

template<class T>
inline
template<class T>
 NetworKit::QuadNodePolarEuclid< T >::QuadNodePolarEuclid ( double leftAngle, double minR, double rightAngle, double maxR, unsigned capacity = `1000`, bool splitTheoretical = `false`, double balance = `0.5` )
inline

Construct a QuadNode for polar coordinates.

Parameters
 leftAngle Minimal angular coordinate of region, in radians from 0 to 2 rightAngle Maximal angular coordinate of region, in radians from 0 to 2 minR Minimal radial coordinate of region, between 0 and 1 maxR Maximal radial coordinate of region, between 0 and 1 capacity Number of points a leaf cell can store before splitting minDiameter Minimal diameter of a quadtree node. If the node is already smaller, don't split even if over capacity. Default is 0 splitTheoretical Whether to split in a theoretically optimal way or in a way to decrease measured running times alpha dispersion Parameter of the point distribution. Only has an effect if theoretical split is true diagnostics Count 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>
 void NetworKit::QuadNodePolarEuclid< T >::addContent ( T 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
 input arbitrary content, in our case an index angle angular coordinate of point, between 0 and 2 pi. R radial coordinate of point, between 0 and 1.
template<class T>
 count NetworKit::QuadNodePolarEuclid< T >::countLeaves ( ) const
inline

Leaf cells in the subtree hanging from this QuadNode.

template<class T>
 std::pair NetworKit::QuadNodePolarEuclid< T >::EuclideanDistances ( double phi, double r ) const
inline
Parameters
 phi Angular coordinate of query point r_h radial coordinate of query point

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

angular boundaries

corners

template<class T>
 index NetworKit::QuadNodePolarEuclid< T >::getCellID ( double phi, double r ) const
inline
template<class T>
 void NetworKit::QuadNodePolarEuclid< T >::getCoordinates ( vector< double > & anglesContainer, vector< double > & radiiContainer ) const
inline
template<class T>
 std::vector NetworKit::QuadNodePolarEuclid< T >::getElements ( ) const
inline

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

Returns
vector of content type T
template<class T>
 void NetworKit::QuadNodePolarEuclid< T >::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
 center Center of the query circle radius Radius of the query circle result Reference to the vector where the results will be stored minAngle Optional value for the minimum angular coordinate of the query region maxAngle Optional value for the maximum angular coordinate of the query region lowR Optional value for the minimum radial coordinate of the query region highR Optional value for the maximum radial coordinate of the query region
template<class T>
 count NetworKit::QuadNodePolarEuclid< T >::getElementsProbabilistically ( Point2D< double > euQuery, std::function< double(double)> prob, bool suppressLeft, vector< T > & result ) const
inline
template<class T>
 index NetworKit::QuadNodePolarEuclid< T >::getID ( ) const
inline
template<class T>
 double NetworKit::QuadNodePolarEuclid< T >::getLeftAngle ( ) const
inline
template<class T>
 index NetworKit::QuadNodePolarEuclid< T >::getMaxIDInSubtree ( ) const
inline
template<class T>
 double NetworKit::QuadNodePolarEuclid< T >::getMaxR ( ) const
inline
template<class T>
 double NetworKit::QuadNodePolarEuclid< T >::getMinR ( ) const
inline
template<class T>
 double NetworKit::QuadNodePolarEuclid< T >::getRightAngle ( ) const
inline
template<class T>
 count NetworKit::QuadNodePolarEuclid< T >::height ( ) const
inline

Height of subtree hanging from this QuadNode.

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

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

Parameters
 query Center of the Euclidean query circle, given in Cartesian coordinates radius Radius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T>
 bool NetworKit::QuadNodePolarEuclid< T >::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_c Angular coordinate of the Euclidean query circle's center r_c Radial coordinate of the Euclidean query circle's center radius Radius of the Euclidean query circle
Returns
True if the region managed by this node lies completely outside of the circle
template<class T>
 void NetworKit::QuadNodePolarEuclid< T >::recount ( )
inline
template<class T>
 count NetworKit::QuadNodePolarEuclid< T >::reindex ( count offset )
inline
template<class T>
 bool NetworKit::QuadNodePolarEuclid< T >::removeContent ( T input, double angle, double R )
inline

Remove content at polar coordinates (angle, R).

May cause coarsening of the quadtree

Parameters
 input Content to be removed angle Angular coordinate R Radial coordinate
Returns
True if content was found and removed, false otherwise
template<class T>
 bool NetworKit::QuadNodePolarEuclid< T >::responsible ( double angle, double r ) const
inline

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

Parameters
 angle Angular coordinate of input point r Radial coordinate of input points
Returns
True if input point lies within the region of this QuadNode
template<class T>
 count NetworKit::QuadNodePolarEuclid< T >::size ( ) const
inline

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

template<class T>
 void NetworKit::QuadNodePolarEuclid< T >::split ( )
inline
template<class T>
 void NetworKit::QuadNodePolarEuclid< T >::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>
friend

## Member Data Documentation

template<class T>