NetworKit::QuadNodeCartesianEuclid< T > Class Template Reference

`#include <QuadNodeCartesianEuclid.h>`

## Public Member Functions

QuadNodeCartesianEuclid (Point< double > lower=Point< double >({0.0, 0.0}), Point< double > upper=Point< double >({1.0, 1.0}), unsigned capacity=1000, bool splitTheoretical=false)
Construct a QuadNode for polar coordinates. More...

void split ()

void addContent (T input, Point< double > pos)
Add a point at polar coordinates (angle, R) with content input. More...

bool removeContent (T input, Point< double > pos)
Remove content at coordinate pos. More...

bool outOfReach (Point< double > query, double radius) const
Check whether the region managed by this node lies outside of an Euclidean circle. More...

std::pair< double, double > EuclideanDistances (Point< double > query) const

bool responsible (Point< double > pos) 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< Point< double > > &pointContainer) const

void getElementsInEuclideanCircle (Point< double > center, double radius, vector< T > &result) const
Main query method, get points lying in a Euclidean circle around the center point. More...

count getElementsProbabilistically (Point< double > euQuery, std::function< double(double)> prob, vector< T > &result) const

void maybeGetKthElement (double upperBound, Point< 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...

index getID () const

index indexSubtree (index nextID)

index getCellID (Point< double > pos) const

index getMaxIDInSubtree () const

count reindex (count offset)

std::vector
children

## Constructor & Destructor Documentation

template<class T>
 NetworKit::QuadNodeCartesianEuclid< T >::QuadNodeCartesianEuclid ( Point< double > lower = `Point({0.0, 0.0})`, Point< double > upper = `Point({1.0, 1.0})`, unsigned capacity = `1000`, bool splitTheoretical = `false` )
inline

Construct a QuadNode for polar coordinates.

Parameters
 lower Minimal coordinates of region upper Maximal coordinates of region (excluded) capacity Number of points a leaf cell can store before splitting splitTheoretical Whether to split in a theoretically optimal way or in a way to decrease measured running times

## Member Function Documentation

template<class T>
 void NetworKit::QuadNodeCartesianEuclid< T >::addContent ( T input, Point< double > pos )
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::QuadNodeCartesianEuclid< T >::countLeaves ( ) const
inline

Leaf cells in the subtree hanging from this QuadNode.

template<class T>
 std::pair NetworKit::QuadNodeCartesianEuclid< T >::EuclideanDistances ( Point< double > query ) const
inline
Parameters
 query Position of the 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.

template<class T>
 index NetworKit::QuadNodeCartesianEuclid< T >::getCellID ( Point< double > pos ) const
inline
template<class T>
 void NetworKit::QuadNodeCartesianEuclid< T >::getCoordinates ( vector< Point< double > > & pointContainer ) const
inline
template<class T>
 std::vector NetworKit::QuadNodeCartesianEuclid< 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::QuadNodeCartesianEuclid< T >::getElementsInEuclideanCircle ( Point< double > center, double radius, vector< T > & result ) 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. (Maybe not necessary due to copy elisison)

Safe to call in parallel.

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::QuadNodeCartesianEuclid< T >::getElementsProbabilistically ( Point< double > euQuery, std::function< double(double)> prob, vector< T > & result ) const
inline
template<class T>
 index NetworKit::QuadNodeCartesianEuclid< T >::getID ( ) const
inline
template<class T>
 index NetworKit::QuadNodeCartesianEuclid< T >::getMaxIDInSubtree ( ) const
inline
template<class T>
 count NetworKit::QuadNodeCartesianEuclid< T >::height ( ) const
inline

Height of subtree hanging from this QuadNode.

template<class T>
 index NetworKit::QuadNodeCartesianEuclid< T >::indexSubtree ( index nextID )
inline
template<class T>
 void NetworKit::QuadNodeCartesianEuclid< T >::maybeGetKthElement ( double upperBound, Point< double > euQuery, std::function< double(double)> prob, index k, vector< T > & circleDenizens ) const
inline
template<class T>
 bool NetworKit::QuadNodeCartesianEuclid< T >::outOfReach ( Point< 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>
 void NetworKit::QuadNodeCartesianEuclid< T >::recount ( )
inline
template<class T>
 count NetworKit::QuadNodeCartesianEuclid< T >::reindex ( count offset )
inline
template<class T>
 bool NetworKit::QuadNodeCartesianEuclid< T >::removeContent ( T input, Point< double > pos )
inline

Remove content at coordinate pos.

May cause coarsening of the quadtree

Parameters
 input Content to be removed pos Coordinate of content
Returns
True if content was found and removed, false otherwise
template<class T>
 bool NetworKit::QuadNodeCartesianEuclid< T >::responsible ( Point< double > pos ) 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::QuadNodeCartesianEuclid< T >::size ( ) const
inline

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

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